Design and Implementation of a Hardware Accelerator for Handshake Join on FPGA

摘要

連続的に流入するデータ(データストリーム)を処理するデータストリーム管理システム(Data Stream Management System, DSMS)の主要演算の一つにウィンドウジョインがある．ストリームデータ処理ではリアルタイム性が重視されるため，ウィンドウジョインのDSMSへの演算負荷が大きいことが問題となる．この課題の解決法として，ウィンドウジョイン・アルゴリズムの一つであるハンドシェイクジョインを専用ハードウェアとしてFPGA　(Field-Programmable Gate Array)上に実現する手法を提案する．一般的に，処理性能向上にはハードウェア化が有効な方法であるが，高い演算性能を達成するためには処理を並列的に行う必要がある．しかし，本来ウィンドウジョインは逐次的な処理であるため，ウィンドウジョインをハードウェア化してアクセラレーションするには，いかにして並列的な処理を導入するかが重要になる．ハンドシェイクジョインは，並列処理を念頭に考案されたアルゴリズムであるため，専用ハードウェアとして実装できれば高い処理性能が期待できる．しかし，先行研究ではハードウェア化する際の問題点が明らかにされていない．本論文では，ハンドシェイクジョインを専用ハードウェアとして実装する際の問題点を明らかにし，解決することにより，高い並列度を実現する．提案手法を用いることにより，二つのデータストリームに対して結合キーの比較処理を並列実行することが可能となる．このとき，分散して出力されるデータ(出力タプル)を集約(マージ)する機構が必要となる．ハンドシェイクジョインでは，ツリー型のマージネットワークにより出力タプルを集約する．しかし，ツリー型のネットワークでは，マージネットワークがシステム全体のパフォーマンスのボトルネックとなる問題が生じるため，提案するアダプティブ・マージネットワークによりその問題の軽減が可能であることを示す．また，ハンドシェイクジョインでは結合キーの比較処理を並列的に行い，結果が出力される．そのため，出力タプルが同時多発的に生成される場合があり，出力タプルの数が瞬間的に内部のバッファサイズを超えてしまいオーバーフローを起こすという問題が生じる．提案手法では，この問題に対してアドミッション制御機構を導入することで， バッファ・オーバーフロー(出力タプルの欠落)の回避が可能となることを示す．