スティルハウスの書庫の書庫

はてなダイアリーで書いてた「スティルハウスの書庫」を移転してきました。

文字通り「ネットワークがコンピューター」な金融HFTでのFPGAの使われ方

ここのところ重度のFPGA中二病にかかってしまい、冬休み中もDE0ざんまいな日々。気になっていた金融のHFT(high frequency trading:大手投資銀行等がμ秒単位の超高速で株式等を売り買いしてる恐ろしい市場)におけるFPGA利用状況について、HFT Reviewにこってりしたレポート(HFT業界のベンダー各社にインタビューしたもの)が載っていたので、勢い余って面白かった部分を超訳してしまった。

元ネタはこちら:

FPGA導入のはじまり:レイテンシのコントロール

そもそも、なぜ金融HFT分野でここ2年ほどの間にFPGAが急速に広まったのか? どんな用途から使われ始めたのか? その背景や歴史について。

Traditionally, we started out with FPGA on the NIC card a great place for putting logic such as market data feed parsing.
  • もともとは、NICに搭載されたFPGA上にアプリケーションロジックを載せ、マーケットデータのフィードのパースなどを行うところから始まった。
The first area is around low-latency connectivity for inbound and outbound data, where all network connections are possible candidates for an FPGA-enabled Network Interface Card (NIC) to give that extra latency boost. Such a card might be using the FPGA to run a TCP Offload Engine for example, which can both free up CPU cycles and reduce PCI traffic.

Other areas where FPGAs are starting to make a significant impact are market data feed handling, pre-trade risk controls and other processes where firms need to be able to take in data then run calculations or simulations on that data in-line at high speed. Applications are now increasing as people get more comfortable with the technology and firms are looking at pure acceleration of tasks that they would previously have done using CPUs or General Purpose GPUs.
  • FPGA搭載NICによるTCPオフロードエンジンTCPスタック処理をNIC側で実行しCPUやPCIバスの負荷を下げる)のようなネットワーク接続の低遅延化が、FPGA利用のはじまり。
  • もうひとつの用途は、マーケットデータのフィードハンドリングやリスク分析における各種演算やシミュレーションを実時間で実行する用途。
Most of them are doing some variation of ticker plant”, responds Durwood. “Some are just looking at a handful of stocks and absolutely hot-rodding those, others are trying to convert a 150-deep book into automated trading. It’s still at the immature phase where different people are trying different approaches and taking risks.”

Taking care of tasks like parsing, filtering, normalisation and session management is where FPGAs can add a real advantage, so market data delivery and distribution is ripe for this technology. 
  • FPGA利用事例の大半では、ticker plant(マーケットデータを投資家や各システムにリアルタイムかつ低遅延に配信する基盤)かそれに類する基盤の構築に利用している。また、複数の株価を監視してhot-rodding(?)したり、150-deep(?)のトレーディング・ブックを元に自動取引を実装しようとしているファームもある。
  • データのパースやフィルタリング、ノーマライズ、セッション管理などFPGAの得意とするところ。マーケットデータの配信はFPGAにいまもっとも適している用途だ。
Many times, Market Data Managers implement direct feeds in a 1:1 pairing with the most demanding clients.  But the explosion of low latency needs makes the 1:1 pairing of feeds and clients untenable. Most enterprises need to simultaneously feed dozens (even hundreds) of servers including: surveillance risk systems, historical tick databases and back up servers.  On top of all of this, they continue to experience ‘bursty markets’, a trend that is expected to continue with the increasing number of automated trading programs.

Recently, Market Data managers threw more CPUs at the problem.  They constructed multi-threaded programs, and tried to off load the CPUs.   But now, there is a type of recapitulation happening in the market.  The market is turning to new architectures, such as pure FPGA architectures to re-invent the market data infrastructure.  The FPGA architectures of tomorrow offer a highly parallelized approach to processing market data. This enables a deterministic latency infrastructure.  

Deterministic latency, (keeping the same speeds regardless of data rates, number of venues or distribution points) is the new goal for Market Data Managers.  And it gives the Market Data Managers the ability to offer guaranteed service levels to their users.   Most importantly, the new FPGA architectures gives the algo trader a dependable ultra-low latency reaction time to changing market signals, under all market conditions.
  • これまでマーケットデータマネージャ(投資銀行や証券会社においてticker plantの構築を担当する部門?)は、大手投資家との間で1:1のネットワーク接続を行い、マーケットデータフィードを提供してきた。しかし(HFTの普及により)低遅延性が必須となったおかげで、1:1の接続は難しくなった。多くの投資家は、リスク分析システムや、時価履歴データベース、バックアップサーバーなど、時には数百台のサーバーを保有しており、それらに同時にマーケットデータを配信しなければならない。加えて、自動取引プログラムの増加によって、マーケットの動きのバースト性も高まりつつある。
  • つい最近まで、マーケットデータマネージャは、より多くのプロセッサをサーバーに搭載することで、この問題に対処しようとしてきた。例えばマルチスレッド・プログラミングによりCPU間で負荷分散する手法などである。しかしいま、ひとつの進化が起きている。FPGAのみをベースとするアーキテクチャによって、マーケットデータ配信のインフラを構築し直す動きである。FPGAの高度な並列性によって、マーケットデータの配信にともなうレイテンシの決定性を確保可能になる。
  • レイテンシの決定性とは、データの転送速度や配信先の数などによらず、データの遅延を一定以下に保証できる性質である。レイテンシの決定性は、顧客へのサービスレベルを保証する手段となるため、マーケットデータマネージャにとって現在もっとも重要な指標となっている。加えて、FPGAの利用によって、マーケットがどのような状況にあろうとも絶え間なく動くマーケットシグナルに応じて超低遅延で対応できる手段をトレーダーに提供することができる。

ここで示されてるように、HFTにおけるFPGA導入の動機はかなり特殊だ。この分野の情報を見ているとマイクロ秒や数百ナノ秒といったオーダーの数値がよく出てきており、もはやハードリアルタイム制御の世界である。こうなると既存のCPUやその上で動く一般的なOSではレイテンシの確実な予測が難しい。例えばマーケットが瞬間的に激しく動いてOS負荷が上昇し、オーダーを出すのが数ms遅れてしまった...では済まされない。実際に、マーケットデータ配信の数msの遅れによってNYSEが4億円の罰金を課せられたりしている。

こうした特殊環境のなかで培われたFPGA技術であるため、それがそのまま一般の用途(例えばWebやビッグデータ)にもすぐ広がるとは思えない。ただ、長期的にはFPGAコモディティ化によって一般用途でのFPGA導入のハードルがぐんと下がりつつあり、あるポイントでクリティカルマスに達するんじゃないかな〜と思ったり。

金融HFTにおけるFPGA利用の現状

つづいて、HFTファームがいま直面しているFPGA利用の課題について。

“There are maybe 25-30 end-user firms around the world that are fully capable of developing complete high performance applications in FPGA today”
  • (金融HFTの)高性能アプリをFPGAでフルに開発できるベンダーは25〜30社存在する。
Working with order and trade data brings additional complexities in development and testing however, because the order can go through so many state transitions.

Despite such complexities, FPGAs are now being used in FIX engines, rules engines, and even full-blown execution management systems. Ferdinando La Posta, Co-Founder of trading solutions vendor GATELab, explains his firm’s approach.
  • オーダーや取引データの処理となると、たくさんの状態遷移の取り扱いが必要となり、開発やテストの複雑さが増す。
  • そうした難しさはあるものの、FPGAFIXプロトコル(金融取引の標準プロトコル)エンジンやルールエンジン、さらには執行管理システム全体の実装までに利用され始めている。
“Firms realise they can buy FPGA-based solutions from vendors who have done the straightforward stuff like TCP offload, FIX/FAST translation, feed handling and so on,” says Keene. “But HFT firms also realise that the only way to gain an advantage now is to come up with better, more clever, more efficient, more productive and more profitable algorithms. That’s going to be their differentiator, but not many HFT firms have had much success putting their own trading algorithms onto FPGAs.
  • TCPオフロードやFIX/FASTプロトコル変換、フィードハンドリングといった簡単な処理を扱うFPGAソリューションであれば、いまやベンダーからすぐに購入できる。
  • 現在のFPGA活用の焦点は、より賢く効率的で、生産性と収益性の高いアルゴリズムFPGAで実装できるか。それこそが差別化要因だが、自社のトレーディングアルゴリズムFPGAに載せることに成功したファームはあまり多くはない。
Yes, you had ANDs, ORs and other arithmetic operators, but trying to build up logical or algorithmic expressions using individual components can end up being quite weighty and not really optimised. So to do anything clever like standard deviation, you were basically on your own and had to develop it yourself.”
  • FPGAでは、ANDやOR、その他の(簡単な)数値演算などの演算は簡単に記述できる。しかし、個々のコンポーネントを組み合わせて数式や論理式を構成しようとすると、すぐに規模が大きくなって、そのままでは(レイテンシの)最適化もなされていない。よって、標準偏差みたいなちょっと高度な演算を行うには、基本すべて自分で回路を組んで最適化していく必要がある。
But all of this means that there is now a growing demand in the financial markets for programmers and engineers who can work directly in VHDL and Verilog.

“Nobody knows how to write parallel code except the HPC guys,” asserts Keene. “A programmer writing an application to do financial transactions is unlikely to know how to write parallel code. FPGAs are still the realm of the electrical engineer as opposed to the computer science engineer. And those guys have now discovered that what they know is really valuable, so they’re charging an arm and a leg for it.”
  • 金融分野では今後もVHDLVerilogを直接書けるプログラマーのニーズが増え続ける? HPC分野のエンジニアじゃない限り、大規模並列なコードの書き方を知っている人はほとんどいない。金融取引のアプリを書いてたプログラマーは、FPGAの並列性を引き出すコードの書き方を知らないFPGAは未だに電子回路設計の世界であって、コンピューターサイエンスの世界ではない。そこにすごい価値があると知って、(回路を書けるエンジニアは)自分のスキルを高値で売りつけている。

FPGAはCPUではないので、ちょっと複雑なことをしようとするとすぐカベに突き当たる。現状ではHFTファーム各社はそのカベをいかにして超えられるか競っている状況のようだ。また、次に出てくる高級言語による高位合成はまだ普及しておらず、低レベルなハードウェア記述言語であるHDLをガリガリ書いて最適化できるデジタル回路設計者がモテモテな様子が伺える。

CやHaskell、データフロー言語による高位合成

金融以外のFPGA界隈で面白い話題のひとつは、高位合成だ。つまり、低レベルなHDLを地味に書いていくのではなく、C言語でフツーに書いたコードからHDLの順序回路や組み合わせ回路を合成するアプローチである。しかしHFT分野ではあんまり普及してないみたい。

“At one extreme, you give someone a low-level language, you give them all the detail they need, the data sheets, the specifications, an oscilloscope and a layout tool, so that they can build a board and develop it from there. At the other end of the spectrum is the claim that you can take a serial process, written in C for example, and somehow magically turn it into something that can run in a massively parallel way, which is what you need to do to put it on the chip.
  • FPGA開発のアプローチのひとつとして、HDLのような)低レベルの言語を使い、細かいところの作りこみをはじめ、データシートや仕様書、オシロ、チップのレイアウトツールなどを用いてボードの開発まで行なう(伝統的な)アプローチがある。
  • もう一方のアプローチとしては、C言語などの手続き型の高級言語を用いて、どうにかしてそこから高い並列性を引き出してFPGA上で動作させるという手法がある(高級言語による高位合成)。
“In the ASIC prototyping world, there have been attempts to get from C to gates for many years. And there have been any number of companies founded and failed on the basis of their C-to-gates technology, because it just doesn’t work out. From our point of view, as FPGA guys, we don’t understand how you can even begin to minimise latency in terms of clock cycles without designing as close down to the actual logic as possible. There are companies claiming you can do it in C or even in MATLAB, but we don’t agree,” he says.
  • ASICプロトタイピングの世界では、C言語からゲートレベルへの合成の手法が長年に渡って検討されてきた。Cベースの高位合成のベンダーがいくつも現れては、うまく行かずに消えていった。いまのFPGAに求められているのは低遅延性であることを考えても、ゲートレベルで設計せずにレイテンシを最適化できるとは考えにくい。CやMATLABで記述したコードをFPGAに落とせるといった主張には同意できない。

レイテンシや並列性の最適化が命のHFTでは、Cから生成したHDLでFPGAを使うなんて、もってのほからしい。あまり高位合成について知らないけど、Cで普通に書けば、そこから高度に並列化されたHDLが生成されるとは想像しにくい。たぶん順序回路だらけになるんだろうな。もっとも、コモディティ化したFPGAを用いる一般用途では高位合成の利用が主流になるんじゃないかな、と思う。なにせ高級言語デバッグラクだし。。

一方で、Cのような手続き型言語ではなく、データフロー言語や関数型言語を使って高位合成しようというアプローチもある。

“At Maxeler we take a very different approach. You shouldn't be thinking in terms of sequential C++ code, but instead think about the flow of data through your algorithm, which at the end of the day is all that matters. MaxCompiler does all the heavy lifting for you, like making sure the data is in the right place at the right time, and presents the programmer with a high level abstraction of the dataflow that is easy to conceptualise. Because of this you spend your time designing great algorithms rather than getting your hands dirty with all the messy details.” claims Spooner.
  • Maxelerでは、これらいずれとも違うアプローチをとっている。結局のところ、重要なのは欲しいアルゴリズムに基づいてデータの流れを定義することであって、必ずしもそれをC++のような手続き型言語を使って実装する必要はない。MaxCompilerでは、理解しやすく抽象度の高いデータフローをプログラマーが表現できる環境を提供し、かつデータが正しいタイミングで正しい場所に流れることをプログラマーに代わって管理する。(HDLのように)細かく面倒な詳細を記述する必要はなく、より多くの時間をアルゴリズムの設計に使える。

データフロー厨な俺はこういうの反応してしまうなぁ。。一方、Parallel ScientificというベンダーではHaskell FPGAコンパイラというものも作っている。

GPGPUFPGAの違い

ところで、FPGAのライバルであるGPGPUは使われてないの?

“GPUs have a stronghold in the parallel processing of graphics, but where they fall down is that they don’t help you with latency at all,” explains Spooner. “While they have a massive amount of parallelism, it’s coarse-grain parallelism, it’s not pipeline parallelism.”
 
“If you’ve got one message, you can only process it in one core. So it doesn’t matter how many different cores you have, it’s only in one of them. Which means that GPUs give you a throughput play rather than a latency play. If you want to reduce latency, you need fine-grain parallelism,” says Spooner. "At Maxeler we use Dataflow engines (DFEs), which provide the same fine grain parallelism, but are ready-to-compute rather than just blank chips.”

Another problem with GPUs is that they tend to be more prone to failures and errors in calculations. So although they can work well for certain parallel computing tasks like Monte Carlo simulations, they are unable to deliver the level of determinism offered by FPGAs.
  • GPUはグラフィクスの並列処理には強いが、低遅延の実現には向いていない。並列度は高いが、それは粒度の粗い並列度であって、パイプラインレベルの並列度ではない
  • 例えばGPUでは、ひとつのメッセージを受け取ったとき、それを1つのコアでしか処理できない。コアがいくつあっても意味がない。つまりGPUはレイテンシよりもスループットを重視した設計になっている。低遅延が必要なら、より細粒度の並列性が必要だ。そこでMaxelerでは、そうした細粒度の並列性をゼロから設計するのではなく、すぐに計算に使えるデータフローエンジン(DFE)を用いて実現している。
  • GPUのもうひとつも問題点は、演算中のエラーや障害に弱いところ。そのせいで、モンテカルロシミュレーションのような並列演算には向いてるものの、FPGAのようなレベルの(レイテンシの)決定性は実現できない。

インテルの主張

このレポートではインテルへのインタビューも掲載されてる。今のところインテルは、FPGAでもGPGPUでもなくCPUを使え!ってスタンスであることがよく分かる(社内じゃ研究してるだろうけど…)。

FPGA-based feed handlers are very common, but when people want to do more, they end up sending the data to a CPU socket. There were visions at one time about doing a lot of the calculation on the FPGA, but programming FPGAs are fairly challenging. It’s certainly not as easy as performant code with higher level languages.
 
We found that people started looking at using Cuda as an alternative for the math side of things, but this too can be a more challenging development environment. So, people take applications that were targeted at an FPGA for math, and attempt to run those computations on GPGPUs. But then they were losing the benefit of doing everything on the FPGA card and sending out the data as quickly as though that is possible, because once you leave the card, you incur a latency hit going across the bus.
 
Fragmentation of the code base is a bad thing, and this type of GPU + FPGA + CPU solution makes it worse.
  • FPGAベースのフィードハンドラはとても広く利用されているが、それ以上のことをやろうとすると、CPUにデータを送ることになる。かつてはFPGA上でさまざまな演算を行うという構想もあったが、FPGAのプログラミングは簡単ではない。高レベル言語のような生産性の高いコードに比べると難易度が高い。
  • FPGA上での数値演算をCUDAで記述する試みもあったが、これも開発環境に難点がある。そこで、FPGA向けに書いた数値演算アプリをGPGPUで動かそうとする人もいたが、すると「すべてをFPGAカード上で処理する」というメリットが失われ、カード外部とのデータのやり取りでレイテンシが発生してしまう。
  • GPU + FPGA + CPUを組み合わせるソリューションは、コードベースの分断をまねくダメなソリューションだ。

FPGA搭載アプリケーションスイッチの登場

金融HFTのFPGA界隈でのいまもっとも熱い話題は、FPGA搭載のアプリケーションスイッチ、具体的にはArista 7124FXの登場である。アプリケーションスイッチとはつまりレイヤ7スイッチのことで、ロードバランサーのようにアプリケーションレイヤの情報(URIとかクエリパラメータとかクッキーとか)を見てスイッチングしたりするネットワーク機器を指す。

With the announcement of the 7124FX switch from Arista, it’s now possible to put logic on a switch.  Of course, all data needs to cross a switch when it enters or leaves your cabinet, or travels inter-server in a co-lo location.  Some applications can really benefit if you can perform actions on the data as it’s making that mandatory switch.  Anything that could benefit from data transformation (a good example is normalizing market data, or filtering down a feed) or inspection with/without manipulation (for example risk checking) is a great application for the switch. 

A simple example: “Send this buy order when the price of MSFT drops below 27.42”.  Imagine if you could program this into the switch: you could go from tick-to-trade in nanoseconds, without even fully entering your cabinet!  This is exciting stuff and it will be reality very soon!”
  • (2012年の)Arista 7124FX(FPGA搭載アプリケーションスイッチ)の登場によって、スイッチ上にアプリケーション・ロジックを載せることが可能になった。
  • スイッチは、コロケーション(データセンター)内のサーバーやラックを出入りするあらゆるデータが通り抜ける場所。そこでさまざまな処理を実行できることで多大なメリットが得られる用途も多い。例えばマーケットデータのノーマライズやフィルタリング、データ内容の監視や加工(リスクチェックなど)は、このスイッチに最適な利用例だ。
  • 例えば「MSFTが27.42以下に下がったら買いを入れる」といったロジックをスイッチに組み込める。マーケットデータがサーバーのラックに届く前に、ナノセカンドの単位で取引が可能になる。こんなスゴいことがもうすぐ実現可能になる。

FPGAを載せたアプリケーションスイッチ、もはやロードバランサーなんてつまらない仕事はしていない。株価がサーバーに届く前に勝手に株の売り買いしてる(なにそれこわい)。俺もちょっと前にIPスイッチみたいなFPGAサーバーがあれば面白いだろうなぁ〜と妄想してたら、このAristaのFPGAスイッチはまさしくそのまんまの製品だった。まぁ誰でも考えるか。しかもAristaはSunのアンディ・ベクトルシャイムが設立してて、やっぱりベイエリアのコアな投資家の嗅覚は半端ないなぁと感心するなど。





このFPGAスイッチについてはHFT Reviewの別のインタビュー記事でもう少し詳しく解説されてて、こちらもたいへん興味深い。

With the goal of accelerating transactions as they pass through the network, it was crucial for us to find a truly in-line solution; rather than simply attaching the FPGA as a client of the switching chipset, the processor sits directly in line with the traffic flow, leveraging both the high functionality of the FPGA and the more traditional network forwarding, multicasting and filtering capabilities that are inherent to the ASIC itself.

このスイッチは10GbEが24ポートあるので、つまりは240Gbpsで流れるトラフィックにon the flyでアプリロジックを適用できる(訂正:FPGAがつながってるのは8ポートだけでした)わけだ。なんだそれは。。

Once you’ve got the ability to do this processing directly within the network, you can provide services that are leveraged across the pool of servers. Feed-handling (normalisation, translation), line arbitration, and symbol based routing are some of the obvious network-centric applications.

シンボルベースのルーティング、つまり、株価情報が流れてきたら、その企業コードを見てパケットをルーティングって面白い。@kibayos さんも指摘の通り、もはやオーバーレイネットワークがIPネットワークを置き換えつつあるような。例えばこれをMapReduceのkeyにあてはめれば、鬼のような超高速でshufflingしてくれるスイッチが簡単につくれる(もっともデータ受け取り側に大量にSSD並べないとボトルネックになるだろうけど)。MRに限らず、テーブルのプライマリキーになりそうなあらゆるIDでシャッフルやジョインしてくれるスイッチ...こんなのがクラウドにずらりと並んでたら楽しそうだな!

そんなわけで、ネットワークがコンピューターだという名言が現実のものとなりつつあるなぁ、という金融HFTの現状であった。