FPGAでジョインやソート

ストリームやデータベースにおけるジョインやマージやソートのFPGA実装って、いまどこまで研究が進んでいるんだろう…と気になってて、その道の専門家である筑波大の川島さんに参考になるpaperをいくつか教えてもらった。これからゆっくり読む。

• How Soccer Players Would do Stream Joins
  • ストリームデータ同士を高速にwindow joinするhandshake joinという手法。これをベースに、三好さん＋オゲさん＋川島さんが世界最速のFPGA実装を作成されたとのこと。

• Sorting Networks on FPGAs
  • ハードウェアでソート！

• FPGAs: A New Point in the Database Design Space
  • FPGAでデータベースまわりの処理、あまり本文がないのでリンク集って感じ。

• FPGA: What’s in it for a Database?
  • こちらもFPGAでデータベースまわりをどう処理するか考えた短いpaper。Content-Addressable Memory（連想メモリ）のハード実装のあたり興味がある。

• FPMR: MapReduce Framework on FPGA - A Case Study of RankBoost Acceleration
  • FPGAで実装したMapReduce。全部オンメモリで処理なのか。。

ハードウェアアルゴリズム一般の書籍

ところで、SIMDやシストリックアレイなどのハードウェアアルゴリズムについては、この本がなかなかわかりやすい感じ（現在読み中）。CAMやデータフロープロセッサのあたりが興味深い。

• リコンフィギャラブルシステム

ストリーム処理一般

以下はFPGAとは直接関係ないけど最近気になるストリーム関連のリソースのメモ。川島さんには以前にストリーム処理の教科書も教えてもらったのだけど、これ高すぎて買うのを躊躇してるとこｗ

• Stream Data Processing: A Quality of Service Perspective

こっちはちょっと分野が違うけど、ストリームマイニングの本。こっちも高い割には俺が理解できるか自信がないｗ

• Knowledge Discovery from Data Streams

あと、Self-Adjusting Computingなる技法で1日かかるMapReduceを数分に短縮したというpaper（via @tanakhさん）

• Streaming Big Data with Self-Adjusting Computation

追記

こんなのあった！超並列機でRDBとソート！

• データパラレルマシンを用いた超並列関係データベース処理
• データパラレル超並列計算機における適応型ソートアルゴリズム