JP Morgan Chaseがデリバティブ専用スパコンをFPGAで作った話 #fpgax

金融系でFPGAというとHFTへの応用が知られてるけど、この事例はリアルタイムトレードの話ではない。金融業務で必要とされるバッチ処理やHPC（High Performance Computing）でもFPGAが本格的に使われ始めてるという話だ。

元ネタは、2011年にJP Morgan Chaseの人がスタンフォード大学で講演した内容。このビデオを見ていたらとっっっても面白かったので、 #fpgax 第3回で使う資料として要点を訳し、俺のコメントや補足を追加してみた。

http://www.youtube.com/watch?v=9NqX1ETADn0 （スライドはこちら）

なお、FPGAも金融も素人なので、勘違いや誤訳があるかもしれない。FPGAとは何かよく知らない人はこちらをどうぞ。

リーマン・ショック対策のスパコン開発

JP Morgan Chaseは、社債やモーゲージ（不動産を担保にした証券）など、膨大な量の有価証券を保有している。それも、例えばひとつの社債をリスクの高い部分と低い部分に切り離して、それをいくつか集めて新しい証券を作ったりするCDOだのCDSだのといった複雑なデリバティブは、いったいそれが現時点でどんなリスクを抱えているのか、刻々と変化する市場動向に応じてつねに再計算しておく必要がある。リーマン・ショックでもCDSのリスクの不透明さが市場を混乱させた要因となっていた。

これらのデリバティブは、リスクごとに切り分けられた「トランシェ」という単位で評価される。こんな式を使うらしい：

...俺にはよく分からないけど、まぁとにかく畳み込みのFFTが計算の中心とのこと。数学が得意な人はこのあたりを読むとわかるのだろう。

JP Morgan Chaseではこれまで、同社が保有するすべてのトランシェに対してこのリスク計算を実施するためにC++で書いたコードと大量のサーバーを用いていたが、計算量が多いため一回あたり8時間ほど要していた。その間にも、自分が持っている証券のリスクがどんどん変化してるかもしれない。もっと速く正確に、もっときめ細かく計算して、リーマン・ショックのようなリスクの不透明性による混乱の再発を避けたい。そこで同社は、Maxeler Technologiesと共同でリスク計算専用のFPGAサーバークラスタを作ることにした、といういきさつである。

ちなみにMaxelerは、SIMDやMIMDなどのコンピュータアーキテクチャの分類で有名なスタンフォード大学のFlynn教授が設立した会社で、金融分野や石油探索分野でのFPGA導入におけるリーディングベンダーだ。このプロジェクトにおけるFPGAサーバーの設計を担当したほか、その上で動くFPGA用OSやコンパイラ、解析ツールなどのコアなテクノロジーをひと通り提供している。プロジェクトへの貢献の大きさとその成功を受けて、JP Morganは後にMaxelerに資本参加までしている。

CPU vs. FPGA

ではなぜ普通のCPUを使わずにFPGAを使ったのか？

• 広いCPUチップの上でも、（リスク計算に必要とされる）数値演算を実行している部分はとても小さい。また、我々はとても深い演算パイプラインを実装したいのだが、CPUにはその能力がない。

たしかにCPUってダイの大半がキャッシュやら制御用に使われてて、実際の演算器に使われてるシリコンの面積ってとても小さい。CPUは実はあんまり計算してないのだ。その少ない演算器に大量の演算をさせるため、とっかえひっかえ高速にデータやプログラムを流しこむ必要があるから、データキャッシュや命令キャッシュにものすごく場所を取られる。

• CPUに比べ、FPGAの動作クロックはあまり速くない。ではなぜFPGAを選ぶのか。それは、FPGAを使うことで数100段といった非常に深い演算パイプラインと、とても細かい粒度での並列化によるストリーム・コンピューティングを実現できるからだ。これにより、CPUに比べ数100倍のスループットを得られるケースもある。

例えば下図のように、x^2 + xっていう式だけをひたすら大量に並列処理するためにたくさん演算器並べたい、と思っても、汎用性が求められるCPUにはそれができない。また、CPUは逐次処理は得意だけど、並列性はあまり高くない。せいぜい8コアとか16コアといった程度で、かつプロセスやスレッドといった粒度の大きい単位での並列性しか得られない。もしCPUで「256個のxについてx^2 + xを並列に計算する」としたら、いちいち256個のスレッド作って、各スレッド間でコンテキストスイッチするのに数10μSかかって、、なんて感じで並列化のオーバーヘッドが鬼のように高くなるので、普通はそんなことせずにループを書くしかない。

FPGAでは、上図のように自分の好きな演算器を書いて横に256個並べられる。演算のひとつひとつをすべて並列化できるという粒度の細かさだ。かつ、コンテキストスイッチやOSのオーバーヘッドがまったくないので、1クロック、つまり数ns〜数10nsですべての計算が終わってる。だから「数100倍のスループット」という表現も決して大げさじゃないのだ。

ストリーム・コンピューティング？

JP Morganの人はFPGA化のもうひとつのメリットとして「ストリーム・コンピューティング」という言葉を使っている。ちなみに、StormやDSMSやCEPなどのビッグデータ界隈でいうストリームと、HPCやGPU/FPGAまわりで言うストリームは、似てるけどちょっと時間／空間のスケールが違う。どちらも大量のデータを「いったんすべて貯めこんでから処理する」のではなく「流れてくるその場でどんどん処理」してスループットを上げるという手法だが、前者はミドルウェアやクラスタ規模の話で、後者はシステム内部の規模の話。

このFPGAによるストリーム・コンピューティングのメリットについては、Hisa Andoさんが書いたMaxelerの石油探査事例のFPGA技術解説で解説されている。

海底油田の探査では、母船からパルス音を発生させ、海底地層からの反射音を曳航する3万個ものマイクで捉える。船を移動させながらこれを10秒ごとに繰り返すので、結果として、1日にテラバイト級のデータが採取されるという。この反射波のデータを使って、得られた反射波と一致するような海底地層を計算で求める。この計算は膨大で、数1000枚のブレードサーバを使っても何日もかかる。Flynn教授は、このような計算をMonolithic Computationと呼んでいる。

拡大画像 001 | 【レポート】スタンフォード大学Flynn教授の特別講義 - FPGAで超高速計算…… | マイナビニュース via kwout

通常のプロセサでは、中間結果をメモリに書き出して、次の処理で読み込むというような処理があり、それに伴ってキャッシュミスなども発生する。しかし、FPGAベースのストリーム処理の場合は、原則、データの受け渡しは直接次の処理ステージに渡され、メモリを経由しない。タイミングを合わせるためにバッファ機能が必要になる場合もあるが、これはFPGAの内部メモリで対応する。このようにFPGA内でデータを受け渡してしまうので、キャッシュミスも発生しない。

拡大画像 003 | 【レポート】スタンフォード大学Flynn教授の特別講義 - FPGAで超高速計算…… | マイナビニュース via kwout

つまり、できるだけキャッシュメモリやメインメモリを介さずに、小さなバッファを挟んで演算器同士でデータをバケツリレーしてクロックごとに受け渡すことで、従来のCPUのようなノイマン型コンピュータにありがちなメモリボトルネックがなくなる、というメリットだ。汎用のCPUでは特定のアプリケーションを前提として演算器間をストリームでつないでおくことはできないが、アプリごとに回路を書き換えできるFPGAなら自由に設計できる。

ただ一方で、ストリーム化があまり効かない用途についてはこの手法の有効性は低くなる。例えば演算器間のバッファで収まらない大きな中間データが生じる用途では、それをメインメモリにまで持っていく必要がありそこがボトルネックになってしまう。はたしてFPGAはストリーム化や大規模並列化に向いたアプリケーションにのみ有効なのか？　それ以外のアプリケーションではCPUに対して勝ち目はあるのか？　については議論が必要だろう。

また、ストリーム・コンピューティングや大規模並列演算といえばGPUの得意分野だ。なぜJP MorganはGPUを使わずにFPGAを使ったのだろうか。

• GPUとの比較：GPUとFPGAそれぞれを用いて試作し、比較した。その結果、どちらにも向き不向きがあることが明らかになった。例えば、トランシェ評価にはFPGAが適し、デフォルト／サバイバルカーブの生成にはGPUが向いている。前者についてはFPGAの方が15倍ほど高速であったため、FPGAを採用した。

GPUはあらかじめアーキテクチャが固定されているため、それにうまくハマる演算ならFPGAより速いし集積度も高い。一方で、HPC分野ではGPUにうまくはまらない用途も少なくないと聞くし、そうした用途ではゼロから自由にアーキを設計できるFPGAに軍配が上がる。既成の高品質なクルマを買うか、ちょっと高いけどクルマの工場を買って自分好みのクルマを作るか、の選択のようなものである。一概にどっちが優れているとは言い難いので、CPU、GPU、FPGAを適材適所で両方使い分けられるのがベストだろう。ちなみにJP Morganでは、GPUとFPGAそれぞれのサーバー・クラスタを併用している。

データセンターの効率を左右する「電力性能比」

そしてJP MorganがFPGAを選んだ決定的な要因のひとつは、消費電力の低さだ。

• JP Morganが運用する計算サーバーにおいて最も重要な要件の一つが電力消費。データセンターのスペースが足りなくなることはないが、電源容量はつねに不足しがち。そのため、サーバーを選択する上では電力性能比がとても重要な指標となる。

FPGAは動作周波数が数100MHzとCPUより一桁くらい低く、そのおかげで消費電力もぐんと少ない。サーバー数台規模ならあまり気にするほどの差ではないけど、それがデータセンター規模にまで積み重なると格段の差異が生じる。そして、一般的なデータセンターの電力容量は数MW程度が上限。どうも変電設備の制約でそれ以上は上げにくいらしい。その限られた電力でどれだけの情報処理をこなせるかは、JP Morganに限らずクラウド規模のデータセンターを運用する企業にとって共通の課題だ。例えば、HP LabsとFacebookとARMが数か月前に発表したmemcachedのFPGA実装に関する論文でも、FPGAの電力性能比の高さが重要なモチベーションとなっている。

FPGAでつくったスパコンで134倍速くなった

では、FPGAでつくったスパコンとは、具体的にはどのようなハードウェア構成で、どの程度のパフォーマンスを達成できたのだろうか。

• FPGA2個と48GBメモリを搭載したFPGAサーバーを40ノード並べた構成のシステムを構築。この規模になるとスーパーコンピューターと言っていいだろう。
• これまで全社規模のポートフォリオ評価に8時間ほどかかっていたが、40ノードのFPGAサーバーによって238秒にまで短縮された。CPU単体とFPGA単体で比べると134倍の高速化となった。
• CPU上では計算量的に実施できなかった複雑な組み合わせのシナリオも計算可能になり、ポートフォリオのリスクについてより深い洞察が得られるようになった。

8時間から4分へ。FPGA速っ。というか、従来のソフトウェア実装ではCPUやOSのボトルネックがそれくらい大きかったということでもある。

C++コードからFPGAへ落とすプロセス

この事例のとても面白いところは、JP Morganがどのようなプロセスを経て既存のリスク計算処理をFPGA化していったのか、苦労話も含めて紹介されている点だ。

• 元のC++コードの解析に始まり、コードの変換、カーネルへの分割、そしてFPGAでの実装、この４つのプロセスを実施し、その結果を踏まえて何度かのイテレーションを実施する。このFPGA化は通常３か月程度で完了する。

最初は既存コードの解析から始まる。従来のシステムにおけるトランシェのリスク評価は、おおざっぱには以下のようなC++コードで計算されていた。

このMaxelerのツールMaxPartonを利用して、既存のC++コードを分析する。

• コードのコントロールフローやデータフロー、依存関係を解析、および実行時間とメモリ消費のプロファイリングを実施。これにより、コードのどの部分がホットスポットなのか、それらがデータを移動してるのか計算してるのか等を明らかにする。

この解析の結果、FPGAに落とすべき「重い部分」が洗い出される。

• CDOトランシェの評価アルゴリズムにおいて重いのは２つの演算ループである。1) コピュラを用いたconditional survival probabilitiesの算出、2) 畳み込みを用いたprobability of loss distributionの算出。
• クオンツが書いた元のC++コードはオブジェクトやテンプレートを多用した複雑なものだが、C++のこれらの機能の多用も、CPU上での演算が遅い原因の一つであった。
• このアルゴリズムに対してMaxPartonによる分析を実施した結果、処理時間の23%がコピュラの計算に、75%が畳み込みに費やされていることが分かった。

コピュラ（copula）ってよく分からないけど、統計で使う関数らしい。このコピュラと畳み込みのFFTが計算の大半を占めている。

ちなみにここで出てくるクオンツとは、金融工学を駆使してデリバティブを設計したり、そのあたりを自分でC++で書いたりできるrocket scientistな人たちだ。給料良さそうだなーっ。。

JP Morganのクオンツが書くC++コードはかなりOOPっぽいコードらしく、そのオーバーヘッドも大きいと指摘している。まあ、コピュラだの複雑な統計的概念がいっぱい出てくるコードなら、どんどん抽象化したくなるよね。上に示したC++コードは、もとの複雑なOOP的コードをCっぽく平らに書きなおしたものだ。

時間軸から空間軸への展開

以上のような分析によって明らかになった重い処理、例えば畳み込み積分の部分などを中心にFPGAで設計していく。

• convoluter（畳み込み積分器）の設計。ここで重要な点は、ループの中で時間軸に並べられていた演算を、空間軸（つまりFPGA上に並べた多数の演算器）に展開している点。
• クオンツは普通、「この時点から始まってこの時点で終わる」といった時間軸にそってコードを書きがちだが、それを空間の並列性に置き換えて設計するという発想の転換に慣れさせるのが難しかった。

時間軸から空間軸への展開、これがFPGAの大きなパラダイム・シフトのひとつで、ソフトウェア・プログラマーにはこれまでなかった発想が求められる。簡単に言うと、ループを回さず演算器を並べろってことだ。GPUのプログラミングもこれに近いけど、自分の好きなように演算器を設計してどんどん深いパイプラインを組んだりストリームを構成できるという自由度の高さが大きく異なる。

「カーネル」間をストリームでつないでいく

こうしてハードウェアとして設計されたコピュラやconvoluterなどの演算器は、FPGA上では「カーネル」と呼ばれる単位で配置され、それらのカーネル間をつなぐデータストリームをソフトウェアで記述する。

• C++で記述された以前の計算モデルを元に、FPGA上にCopulaã‚„Convolutor等の「カーネル」を構成。
• FPGA上のカーネルに流すデータストリームを管理するAPIã‚’MaxelerOS上に作成。

カーネル間をつなぐデータストリームの帯域やどのメモリを使うのかといった判断もこの時点で行う。

• 分析で明らかになった必要なデータの量と帯域に合わせて、システムのリソースを割り当てる。数MB程度の量のデータならFPGAのBRAMを使い、24GB以下ならDDRメモリ、それ以上ならホストメモリ。また、数TB/sの帯域が必要ならBRAM、数10GB/sならDDR、数GB/sならPCIeバス、など。
• この結果を元に、個々の演算をCPUに置くのかFPGAに置くのか決定される。
• FPGA上に実装した場合の演算精度、レイテンシ、およびスループットも、実装前の分析段階で見積もる。

すると、例えば上述のC++コードは以下のようなJavaコードに置き換えられる。

ループを回して演算してたコードを、FPGA上の演算器の間をつなぐストリームを定義するコードに置き換えていくわけだ。また、「このあたりは帯域たっぷりほしいからPCIeバスを4本使っとこう」みたいなハード設計までJavaで書けちゃうのがたいへん愉快である。このあたりはMaxelerのMaxCompilerによる高位合成（高級言語からデジタル回路を生成する技術）の能力に依るところが大きい。

パイプライン化でパフォーマンスを追い込む

そして開発フェーズの後半では、パフォーマンスの追い込みに入る。個々のカーネルをできるだけ深くパイプライン化していくことで、スループットを引き上げていく作業だ。

• カーネルの基本設計がまとまったら、続いては各カーネルについて100段におよぶ深いパイプラインをFPGA上で構成する。パイプライン化によって、個々の演算のレイテンシは伸びるが、スループットは大幅に伸びる。
• 最終的には、コピュラおよびconvoluterのカーネルを1つのFPGAチップ上で100段のパイプラインで構成。

この段階になるとかなりハードウェア設計の職人技が要求される。回路上のどの部分がクリティカル・パスになっているかをナノセカンド単位で追っていったり、その部分をパイプラインに分解してクロック周波数を詰めていったり、といった技能が必要なので、さすがにこれはハードウェア・エンジニアじゃないと難しいはず。

浮動小数点演算の最適化

GPUと比べたFPGAの弱点として時折指摘されるのが浮動小数点演算だ。FPGA上でdoubleを扱う演算器を記述すると場所を取るしクロック数もたくさん使ってしまうので、なるべくならdoubleを使わずに済ませたい。しかし金融のリスク計算に使うとなると計算精度を慎重に考慮する必要がある。

• MaxCompilerでは、IEEE754準拠の単精度・倍精度演算をサポートする。また要件に合わせて指数部と仮数部の精度をビットストリームごとに指定することも可能。すべての演算に倍精度が必要なわけではないので、この機能は大変便利。精度を落とすほどパフォーマンスが向上しFPGA上のリソース消費も抑えられる。最大で20%の速度向上が可能で、精度がある程度低くてもスピードを優先するようなビットストリームに用いている。
• 元のC++コードでは多くの変数がdoubleで定義されているが、倍精度が不要な部分については精度を落としていく。この点をクオンツに納得させるのがとても面倒。クオンツにはすべてを倍精度で計算しないと気が済まない人も多い。一方で、「最終的はセント単位で正しい結果をすばやく出せればいいのだ」という考えのエンジニアも多い。この両者のせめぎあいになる。
• 重要な点は、どの程度の時間をかければどの程度の精度が得られるかのトレードオフを知ること。

要件的なトレードオフだけではなく、クオンツとの文化的衝突が難しい点であったという話がとても面白い。また、さほど気にせずdoubleを富豪的に使えるソフトウェア実装とは異なり、ナノセカンド単位での速度向上が焦点となるFPGA開発ではそのコストと精度のトレードオフを意識する必要が生じる。

FPGA開発はまだ難しい

最後に、FPGA開発の課題と今後についてまとめ。

• FPGA上での同様の設計や最適化を行った研究等は存在していたが、業界でも最大規模の取引を扱う商用サービスのプロダクション環境でこれを実現するのは容易なことではなかった。

大規模なプロダクション環境でのFPGAの投入はJP Morganにとって苦労も多かったらしい。また、CPUやGPUによる開発とはまったく異なるスキルと経験が要求されるため、自社単独での開発は難しく、JP Morganの事例でもMaxelerのツールやエンジニアの能力に大きく依存している様子が伺える。Hisa Andoさんの前述の記事でも、FPGA開発のコストについて以下のように指摘されてる。

このような最適化されたストリーム処理をFPGAに実装するのは簡単ではない。Maxelerでは、通常、2人の専門家がペアで仕事をし、FPGA実装のプロトタイプを作ってデモを行うまでに3カ月、その後、納入する製品レベルに仕上げるのにさらに3カ月程度かかり、全体では1人年程度を必要とするという。＜中略＞このようにFPGAの開発には1人年程度の工数がかかるので、コア処理部がストリーム的に処理でき、かつ、年間を通じて処理時間の長いMonolithicな巨大計算でないとペイしないが、このような条件を満足するケースでは汎用CPUを使用するのに比べて大幅な高速化と低電力化を実現できる手法である。

つまり現状では、JP Morganのように大規模なHPC事例でないとMaxelerのエンジニアを雇ったりツールを買ったりするようなコストはペイしなさそうである。

CPU＋FPGAのSoCでいろいろ変わる

とはいえ、この状況はここ2〜3年で大きく変わると思う。FPGAのコストダウンと高集積化はかなりの勢いで進んでいて、一般的なCPUやサーバーにも普通にFPGAが載りつつあり、FPGA導入のハードルがぐんと低くなってきたからだ。例えばIBMはPOWER8で外部FPGAとCPUとのキャッシュ連携を可能にする機能を載せてきているし、HPも次世代サーバーのHP MoonshotでFPGAカードをサポートする。さらには、ARMコアとFPGAをひとつのチップに混載した、いわゆるSoC（System On Chip）であるXilinx Zynqã‚„Altera SoCを搭載したLinux組み込みボードが最近になっていろいろ出回り始めていて、安いものは2万円ほどで買えるようになった。こうしたSoCの登場で、ソフトウェア・エンジニアにとっては一段とFPGA導入がやりやすくなる。

Zynqでは、ARMとFPGA間でL2キャッシュを共有してて、GPUと同じようにFPGAã‚’ARMのコプロセッサとして使える。ARM上のLinuxで動くアプリからFPGAに載せた機能をAPIコールで呼び出せる。よって、すべての機能をFPGA上でゼロから開発するのではなく、既存のソフトウェアの一部分のみFPGA化してアクセラレーションする、といった段階的な導入が可能だ。Xilinxが出しているサンプルには、OpenCVアプリの画像処理部分をFPGA化してケタ違いに高速化というのもある。また画像処理やHPC応用に限らず、例えばZynqのFPGAはGbEにも直結できるから、最近の学会発表で流行ってるFPGAで実装した鬼速のmemcachedのようなネットワークアプリや大規模データ処理アプリも、以前に比べて実装しやすいはずだ。いつかはやってみたい！

あとはMaxelerのMaxCompiler（たぶんすごく高い）やXilinxのVivado HLS（50万円）のような高機能の高位合成ツールが安く、できれば無償で提供されれば、ソフトウェア・エンジニアにとってのFPGA開発のハードルはさらに低くなり、応用範囲も広がるはず。そんな日が来ることを期待しつつ、いまのうちにFPGAの練習をしておかねば、、と思ったのであった。