WEKO3
アイテム
Design and Implementation of a Hardware Accelerator for Handshake Join on FPGA
https://uec.repo.nii.ac.jp/records/2097
https://uec.repo.nii.ac.jp/records/2097e7c04100-2785-455b-a466-4033a62c50c2
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2012-09-28 | |||||
タイトル | ||||||
タイトル | Design and Implementation of a Hardware Accelerator for Handshake Join on FPGA | |||||
言語 | en | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
著者 |
オゲ, ヤースィン
× オゲ, ヤースィン |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | 連続的に流入するデータ(データストリーム)を処理するデータストリーム管理システム(Data Stream Management System, DSMS)の主要演算の一つにウィンドウジョインがある.ストリームデータ処理ではリアルタイム性が重視されるため,ウィンドウジョインのDSMSへの演算負荷が大きいことが問題となる.この課題の解決法として,ウィンドウジョイン・アルゴリズムの一つであるハンドシェイクジョインを専用ハードウェアとしてFPGA (Field-Programmable Gate Array)上に実現する手法を提案する.一般的に,処理性能向上にはハードウェア化が有効な方法であるが,高い演算性能を達成するためには処理を並列的に行う必要がある.しかし,本来ウィンドウジョインは逐次的な処理であるため,ウィンドウジョインをハードウェア化してアクセラレーションするには,いかにして並列的な処理を導入するかが重要になる.ハンドシェイクジョインは,並列処理を念頭に考案されたアルゴリズムであるため,専用ハードウェアとして実装できれば高い処理性能が期待できる.しかし,先行研究ではハードウェア化する際の問題点が明らかにされていない.本論文では,ハンドシェイクジョインを専用ハードウェアとして実装する際の問題点を明らかにし,解決することにより,高い並列度を実現する.提案手法を用いることにより,二つのデータストリームに対して結合キーの比較処理を並列実行することが可能となる.このとき,分散して出力されるデータ(出力タプル)を集約(マージ)する機構が必要となる.ハンドシェイクジョインでは,ツリー型のマージネットワークにより出力タプルを集約する.しかし,ツリー型のネットワークでは,マージネットワークがシステム全体のパフォーマンスのボトルネックとなる問題が生じるため,提案するアダプティブ・マージネットワークによりその問題の軽減が可能であることを示す.また,ハンドシェイクジョインでは結合キーの比較処理を並列的に行い,結果が出力される.そのため,出力タプルが同時多発的に生成される場合があり,出力タプルの数が瞬間的に内部のバッファサイズを超えてしまいオーバーフローを起こすという問題が生じる.提案手法では,この問題に対してアドミッション制御機構を導入することで, バッファ・オーバーフロー(出力タプルの欠落)の回避が可能となることを示す. | |||||
学位授与機関 | ||||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2012 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2012-09-28 | |||||
専攻 | ||||||
値 | 情報ネットワークシステム学専攻 |