日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

動的なロジック切り替えによる結合演算高速化の検討
上田 高徳

伊藤 愛

小原 盛幹

FPGA による処理エンジンは，回路面積の制約に加えて，外部メモリアクセスのレイテンシやスループットを考慮して設計する必要がある．本論文で議論の対象とするデータベースの結合演算は，演算内容が同一であっても，処理対象データの性質やサイズに応じて，処理時間が最も短い処理戦略が変わる．しかし，FPGA 上に複数の戦略をプ
ログラムすると，それぞれの実装が利用できる回路面積が狭くなり，FPGA のリソースを最大限に利用することができず，FPGA チップ全体を利用した場合よりも性能が劣化する．そこで本論文では，ソフトウェア側から FPGAをプログラムしなおすことで，1 つの結合演算が FPGA のリソースを占有できるようにし，より高速にデータベースの結合演算を実行する技法について議論する．

用できるハードウェア面積が狭くなり，1 つの実装で1 はじめにFPGA チップ全体を利用した場合よりも利用できる

ハードウェアを設計する際には，利用可能な回路面

リソース量が少なくなり性能が劣化する．

積を効率よく利用して性能を引き出すことが求めら本論文で対象とするのは，キーが等しい行を結合すれる．回路を占有できる専用ハードウェアによる処理

る等価結合である．等価結合の代表的なアルゴリズム

エンジンであったとしても，利用可能な回路面積を最であるハッシュ結合とソート・マージ結合の実行時間

大限に利用して，いかに高い性能を実現できるかが，を予測し，高速に実行できると予想される方の結合

そのハードウェア処理エンジンの価値を左右すると回路を FPGA にプログラムすることで，FPGA チッ

いえる．ただし，一概に性能といっても，電力効率のプ全体のリソースを最大限に利用してより高速に結場合もあれば，レイテンシやスループットの場合もあ

合演算を実行できることを示す．そして，実機におけり，その性能目標はアプリケーションと合わせて議論る提案手法の効果を立証するために，計算機のバスにを行う必要がある．

接続された FPGA カードを用いて性能を評価した．

本論文では関係データベースの結合演算を FPGA

データベースの演算に FPGA を用いる試みは，近(Field Programmable Gate Array) を用いて処理す年になって始まったばかりである [7]．データストリーることを考える．大規模データを処理する関係デー

ムに対するウィンドウ結合 [10] [11] は，FPGA がデー

タベースにおいては，処理スループット，すなわちクタストリームに対して効果的に処理できることを示

エリの実行時間がもっとも重要な指標となる．データ

す良い例である．しかし，本論文が対象とするのは永ベースの結合演算は，演算内容が同一であっても，処続化された，あるいはメモリ上に存在するテーブルに

理対象データの性質やサイズに応じて，処理時間が対する結合演算であり，半永続的に到着するデータス

最も短い処理戦略が変わる．しかし，FPGA 上に複トリームに対するウィンドウ結合とは演算が異なる．

数の戦略をプログラムすると，それぞれの実装が利FPGA による結合演算機構 [4] や，クエリ処理エンジ
ン [1] [2] [8] [9] も開発されているが，本論文のような結This is a non-refereed paper.
Ueda, Ito, Ohara, 日本 IBM 東京基礎研究所, IBM Research - Tokyo.

合演算の選択方法については議論されていない． [3]は本論文と同様に動的に FPGA をプログラムするこ

図1

図2

同一の ID を結合する結合演算

ハッシュ結合の処理の流れとを提案しているが，対象が選択演算であり，結合演

合，テーブル R のまだ処理していない行のみでハッ算ではない．

シュテーブルを構築する．そして，(2) もう一方の

以下，2 節では，結合演算の基本とアルゴリズムにテーブル S の行を順に読み込み，各行の ID 列でハッついて確認する．3 節においては，ハードウェア処理

シュテーブルを検索し，同一の ID を持つ行を発見しエンジンにおいて結合演算を用いる場合の課題について結合する．必要に応じて，(3) テーブル R の残りのて議論する．4 節においては，結合演算を切り替える

行に対して (1) と (2) を繰り返す．ここで，ハッシュために，実行時間を予測するモデルについて述べる．

5 節において実験結果を述べ，6 節において関連研究

テーブルが記憶領域を使い切った時に格納できる行数⌈ ⌉回発生を C とすると，図 2 (3) の繰り返しは |R|
Cについて議論する．そして，7 節においてまとめる．

し，その度にテーブル S の全ての行が読まれる．テー2 結合演算とアルゴリズム

ブル R の各行は一度しか読まれないから，読まれる⌈ ⌉行数の合計は |R||S| + |R| となり，実行時間のオーC

本節では本論文の対象である結合演算とそのア

ダーは，ルゴリズムについて説明する．結合演算は，関係代数における基本演算のひとつであり，複数のテーブ

O (|R||S|) + O (|R|)

(1)

となる．

ル (Relation) から，指定された条件にマッチした行

ソート・マージ結合では図 3 のように，まず ID 列を（Tuple）同士を結合して出力する演算である．以下，

キーとみなして両方のテーブルをそれぞれマージソー

本論文ではキーが等しいものを結合するものとする．

トした後，両テーブルを昇順あるいは降順に比較してまた，テーブル R と S の行数をそれぞれ |R|，|S| とマージすることにより，同一の ID を持つ行を発見し書くこととし，|R| ≤ |S| とする．

て結合する．マージソートの計算量は O (|R| log |R|)

図 1 はテーブル R とテーブル S から ID 列が同一と O (|S| log |S|) であり，マージにおいては両テーブの行を結合する結合演算の例を示している．結合演算

ルを読み込むことになるから，ソート・マージ結合のは関係代数の演算子であるから，その定義に計算アル実行時間のオーダーは

ゴリズムは含まれない．よって同一の結合演算を実行

O (|R| log |R|) + O (|S| log |S|) + O (|R| + |S|) (2)するためのアルゴリズムが様々に考えられ，代表的なとなる．

ものにハッシュ結合とソート・マージ結合がある [6]．

以上のことから，ハッシュ結合とソート・マージ結

ハッシュ結合では図 2 のように，(1) 容量が小さい

合の実行時間は，テーブルのサイズに依存することにテーブル R に対して ID 列をキーとしてハッシュテー

なる．例えば，ハッシュ結合においては，小さい方のブルを構築する．この時，テーブル R 全体に対してテーブルのハッシュテーブルが記憶領域に収まるならハッシュテーブルを構築すると記憶領域が不足する場

ば，図 2 (3) の繰り返しはなく，両テーブルに対する

図3

ソート・マージ結合の処理の流れ

一度の読み込みのみで結合演算が完了する．しかし，テーブルのサイズが大きく，ハッシュテーブルが記憶領域に収まらない場合は，図 2 (3) の繰り返し回数が増え，実行時間が増加する．結合演算においては，入力に与えられるデータに応じて計算時間が変わるた
め，適切な結合アルゴリズムを用いることが高速な実

図48 ウェイのソートツリー

行を実現する鍵である．

1 つのソート済み配列を生成できる．未ソートの配列

3 FPGA による処理エンジンと結合演算に対して，ソートツリーを繰り返し適用することで，前節においてはソフトウェアの視点から結合演算ソート済みの配列を生成することができる．繰り返しを説明したが，本節では，FPGA で結合演算を実行

回数は大きなウェイ数のソートツリーを用いるほど少する場合でも処理対象のテーブルサイズに応じて結なくなるので，やはりできるだけ大きなソートツリー

合演算の処理時間が変わることを確かめる．そして，を FPGA に確保することが目標になる．

本論文のテーマである，結合演算の内容に応じて実装を切り替える利点について議論する．

ここで，ASIC のような専用ハードウェア処理エン
ジンでは，アルゴリズムごとに専用の回路を実装する

結合演算に用いるデータ構造の記憶先として FPGA

必要があることに注意すべきである．ハッシュ結合との外部にある記憶領域を利用すると，処理中にデーソート・マージ結合の回路の双方をハードウェア上にタ構造へアクセスした際のレイテンシが問題になる．

配置すると，それぞれの実装が利用できる回路面積

アクセスレイテンシにより処理が止まることで，1 クが狭くなり，ハードウェアチップを最大限に利用する

ロックあたりに処理できるテーブルの行数が減少し，ことができず，チップ全体を利用した場合よりも，使スループットが低下する．よって本論文では，外部メ用できるレジスタ数や記憶容量に制約を受ける．よっモリはデータの入出力に利用するのみとし，チップ内て，使用する結合戦略を決定し，動的に回路を変更しやチップに近い低レイテンシでアクセスできる記憶領てチップ全体を利用すれば，ハードウェアリソースを域にデータ構造を配置することを考える．

最大限に利用できるという着想が得られる．動的な回

前節で確認したように，ハッシュ結合においては路の変更は FPGA にユニークな特徴であり，ASIC

ハッシュテーブルのサイズを大きく確保するほど，実のような専用ハードウェアを用いた処理エンジンでは

行時間を短くできる．よって，低レイテンシでアクセ

不可能である．本論文では，ハッシュ結合とソート・スできる記憶領域をできるだけ大きく確保すること

マージ結合に対して議論するが，他の結合アルゴリズが目標になる．また，ソート・マージ結合においては

ムにおいても適用できる．

ソートの計算時間が支配的であることは明らかである．本論文においては我々の開発したソートツリー

4 結合回路の実行時間予測[5] を用いる．図 4 に 8 ウェイのソートツリーを示し

本節ではハッシュ結合とソート・マージ結合のどちた．このソートツリーは 8 つのソート済み配列かららが高速か決定する手法について議論する．まず，結れる．

⌈
T H2 =

|R|
C

⌉

|S|
vH2

(4)

最後に，処理の開始やステップの切り替えに定数時
図5

FPGA によるハッシュ結合の実行の流れ．FPGA

内部に記憶できる量だけテーブル R を読み込み，テーブル

S を読み込んで結合演算を行う

合対象のテーブルサイズを元に両結合方法の実行時間の制御オーバーヘッド EH が掛かるとする．以上の結果から，ハッシュ結合の実行時間 TH は

TH = TH1 + TH2 + EH⌈⌉
|R|
|R| |S|
=
+
+ EH
v H1
C vH2

(5)

間を予測するためのモデルを説明する．実行時間を予測することができれば，処理時間が短い方の実装で計算することができる．

を選択すればよい．以下では，ある結合演算のステッ
プ s において，FPGA が単位時間あたりに処理できるテーブルの行数を vs とする．vs はメモリ帯域や行のサイズ，FPGA の周波数によって変わることにな
る．詳細は 4. 3 項で議論する．

をソートする．(S3) ソート済みの 2 つのテーブルの行を順に確認してマージする．

ハッシュ結合では，FPGA の内部記憶領域を利用してデータを格納し，ハッシュ結合を行う．まず，(H1)
容量が小さいテーブル R を FPGA 内部に格納できる量だけ読み込んだ後，(H2) もう一方のテーブル S
を読み込み結合する．そして，(H3) テーブル R がFPGA 内部に収まらない場合は (H1) と (H2) を繰り返す．
ここで，(H1) においては (H3) での繰り返し回数によらず，処理全体で テーブル R の各行が 1 度ずつ読まれることになる．よって，処理全体における (H1)の処理時間 [s] の合計 TH1 は以下の式で表される．

|R|
v H1

前節で説明したように，FPGA にソートツリーを構築し，以下の手順でソート・マージ結合を実現する．(S1) テーブル R をソートする．(S2) テーブル S

4. 1 ハッシュ結合の実行時間

TH1 =4. 2 ソート・マージ結合の実行時間(3)

ここで，(S1) のテーブル R をソートする際のイ
テレーション回数は，K ウェイのソートツリーを用いれば ⌈logK |R|⌉ 回となる．(S2) についても同様に⌈logK |S|⌉ 回となる．各イテレーションにおいてはテーブルの全ての行を読み込むことになる．よって，(S1) と (S2) の実行時間は以下の式で表される．

TS1 =|R|⌈logK |R|⌉
vS1

(6)

TS2 =

|S|⌈logK |S|⌉
vS2

(7)

次に (S3) については，昇順にソートされたテーブ
ルを順に確認して，マージソートのマージフェーズと同様の手順で結合する．この時，注目している行につ(H2) においては (H3) の繰り返しごとに，テーブ
ル S の全ての行を読み込むことになる．FPGA 内に記憶可能なテーブルの行数を C としたとき，(H3) の⌈ ⌉
繰り返し回数は |R|回となる．よって，結合処理全C体を通した (H2) の実行時間の合計は以下の式で表さいて，(S3-a) テーブル R と S のキーが同一，(S3-b)
テーブル R のキーの方が小さい，(S3-c) テーブル Sのキーの方が小さい，の 3 パターンが考えられる．

(S3-a) は同一のキーを持つ行がテーブル R と S のらハッシュ結合とソート・マージ結合の実行時間が分
かり，処理時間が短い戦略を選択することができる．
本論文では，E については経験的に求めた値を用いることとし，以下，我々の実装を前提とした時のパラ
メータ v について説明する．本論文で用いた FPGA
カードは計算機の専用バスに接続され，FPGA から計算機のメインメモリに直接アクセスできる．理論
上，メインメモリと 128bit のデータを各クロックごとに送受信できるインターフェースを持つ．また本論
文の実験では，テーブルの 1 行は 1 つの 64bit キーと 1 つの 64bit 値の合計 128bit から構成している．
図6

ハードウェアによるソート・マージ結合の流れ

よって，メモリ帯域がボトルネックでなく，必ず各ク
ロックでデータを受信できるとすれば，FPGA は各両方に見つかったことを意味するから，結合演算の出クロックに 1 行ずつのデータ読み込むことができる．

力となる．何個の行が結合されるかは入力データに依

以下では FPGA のクロック周波数 [Hz] を f とし，v存するため事前には分からないが，テーブルの統計

を f で表現することを考える．

を用いる従来手法で予想することができる [6]．そこ

我々のハッシュ結合の実装では，(H1) でのテーブ

で，(S3-a) が発生する回数，すなわち結合される行のル 1 行の処理に 2 クロック必要である．1 クロック目

個数を M とする．すると，(S3-b) が発生する回数はでキーがすでに格納されているか確認し，格納されて|R| − M 回となる．また，(S3-c) も同様に |S| − M

いなかった場合は 2 クロック目で格納するためであ回発生することになる．従って，ステップ S3 の実行

る．そして，(H2) においては 1 クロックで 1 行処理

時間 TS3 は以下の式で表すことができる．

できる．以上から，vH1 = f /2，vH2 = f となる．

TS3 =|R| − M
|S| − M
M
+
+
vS3-a
vS3-b
vS3-c

ソート・マージ結合の実装においては，(S1) と (S2)(8)

については 1 クロックで 1 行を処理できるようになっている．また，(S3) については (S3-a)，(S3-b)，(S3-c) のいずれの場合にも 1 クロックで処理を 1 ス
最後に，処理の開始やステップの切り替えに定数時

テップ進めることができるようになっている．ただ間の制御オーバーヘッド ES が掛かるとする．以上のし，(S3-a) については，両方のテーブルから行を読結果から，ソート・マージ結合の実行時間 TS は

み込むことになるため，倍のメモリ帯域を消費し，実際には 2 クロック必要になると考えられる．よって，

TS = TS1 + TS2 + TS3 + ES
|S|⌈logK |S|⌉
|R|⌈logK |R|⌉
+
=
vS1
vS2
|R| − M
|S| − M
M
+
+
+
+ ES
vS3-a
vS3-b
vS3-c

vS1 = vS2 = vS3-b = vS3-c = f ，vS3-a = f /2 となる．
(9)

さて，上記の説明においては，FPGA は各クロッ
クにおいて必ずデータを受け取ることができるとしている．しかし，実機における処理においてはメモ
リ帯域やバスのボトルネックにより，必ずしもクロッで計算することができる．

ク毎にデータを受け取れるとは限らない．よってパラメータ v は実機上の測定結果に基づいてキャリブ

4. 3 回路の再プログラムとパラメータ v
以上の議論から，処理テーブルのサイズとパラメー
タとなっている v と E が分かれば，(5) 式と (9) 式かレーションする必要がある．本論文では以下の実験において上記パラメータをそのまま用いている．実機を用いた v の決定とその時のモデル精度の評価は今後の課題である．

20

5 評価実験
15

ハードウェア実装を切り替える利点について確認する．そして，切り替えることで性能上の利益が実機で実行時間 [s]本節ではまず，4 節で導いた計算時間の式を用いて10も得られることを確かめるため，計算機に接続された
5

FPGA カードを用いて性能を評価した．

ハッシュ結合 容量4万行
ハッシュ結合 容量8万行
ハッシュ結合 容量10万行
ソート・マージ結合 2ウェイ
ソート・マージ結合 4ウェイ
ソート・マージ結合 8ウェイ
00

1e+0082e+0083e+008

5. 1 回路再プログラムの利点の確認
まず，回路を切り替える利点について 4 節で導いた
実行時間の式に基づいて考察する．ハッシュ結合の実装において記憶領域に格納できる行数を 10 万行，8
万行，4 万行の 3 種類，ソート・マージ結合で用いる

図7

4e+0085e+0086e+008
テーブルサイズ [Rows]

7e+0088e+0089e+0081e+009片方のテーブルが 20 万行の時の理論実行時間．左上から順にソート・マージ結合の 2 ウェイ，4 ウェイ，8
ウェイ，続いてハッシュ結合のメモリ容量 4 万行，8 万行，10 万行．

ソート実装のウェイ数を 8, 4, 2 の 3 種類として，それぞれの処理時間について式 (5) と式 (9) を用いて比100較する．以下では，EH = 0, ES = 0, M = 0 としている．また通常，ハッシュ結合では，小さい方のテーブ

80以下では常に固定長のテーブル，すなわち 20 万行と1000 万行に対してハッシュテーブルを構築している．

実行時間 [秒]ルでハッシュテーブルを構築した方が性能が良いが，
60

40

図 7 はハッシュテーブルの構築対象であるテーブ
ルを 20 万行とし，もう一方のテーブルの行数を変化

20
ハッシュ結合 容量4万行
ハッシュ結合 容量8万行
ハッシュ結合 容量10万行
ソート・マージ結合 2ウェイ
ソート・マージ結合 4ウェイ
ソート・マージ結合 8ウェイ

させた場合の式 (5) と式 (9) による理論実行時間で00

ある．20 万行は記憶領域に格納できる行数である 10万行に近いため，ハッシュ結合の方がソート・マージ結合よりも有利になる．具体的には，記憶領域に格納できる容量が 10 万行の場合，ハッシュ結合におけるテーブル再構築回数は 2 回であり，8 万行の時は 3回，4 万行の時は 5 回となる．4 節で確認したとおり，

図8

1e+0082e+0083e+0084e+008 5e+008 6e+008
テーブルサイズ [行]

7e+0088e+0089e+0081e+009片方のテーブルが 1000 万行の時の理論実行時間．

左上から順にハッシュ結合のメモリ容量 4 万行，8 万行，10 万行，そしてソート・マージ結合の 2 ウェイ，4 ウェイ，
8 ウェイ．

記憶領域の容量が少なくなるほど構築回数が増える

性能が良いのは 8 ウェイの場合であり，2 ウェイの場

ため，処理時間が長く掛かることが確認できる．よっ合は，もっとも性能が悪くなる．

て，ハッシュ結合が優位な場合においては，できるか

我々のハッシュ結合の実装では 10 万行の格納領域

ぎり高速記憶領域をハッシュ結合に利用することが必を実現するためには，FPGA のロジック数の 86%を要である．

使用する必要があった．ハッシュ結合とソート・マー

これに対して，図 8 は一方のテーブルを 1000 万行

ジ結合を同一の FPGA に共存させると，ハッシュ結とし，もう一方のテーブルの行数を変化させた場合の合用の記憶容量が圧迫され，格納容量が低下する可能

式 (5) と式 (9) による理論実行時間である．記憶領域性がある．FPGA を回路を占有して結合演算を実行に格納できる行数よりも大きいため，ソート・マージ

することで，そのような低下の可能性を排除すること結合の方がハッシュ結合よりも有利になる．もっともができる．我々の FPGA の再構成時間は，ハッシュ結合，ソート・マージ結合のどちらであっても 1.44

表1秒であった．実験結果においては，ハッシュ結合の 8ウェイと 4 ウェイ，また，ソート・マージ結合の容量

10 万行と 8 万行の実行時間において，特にテーブル

評価実験の環境CPU

POWER7 3.55GHz

Memory256GBFedora release 18(3.9.4-200.fc18.ppc64p7)

OS

サイズが大きい場合に，1.44 秒以上の差がある．よって，FPGA を 1 つの結合実装で占有することで，より高速に結合演算を実行可能であると考えられる．

1e+006
ソート・マージ結合
ハッシュ結合ソート・マージ結合の理論値
ハッシュ結合の理論値

1000005. 2 実ハードウェアでの結合演算
次に，実機でも議論が成り立つことを確認するた
め，FPGA カードを用いて実験を行った．実験に用いた FPGA カードは表 1 の計算機の専用バスに接実行時間 [ms]

10000

1000

100

10

続され，FPGA から計算機のメインメモリに直接ア

1

クセスできる．Linux 上からハードウェアに対して，0.1

結合演算対象の 2 つのテーブルのメモリアドレスと，

0.01
100

1000

結果の格納先のアドレス，計 3 つのメモリアドレス
を FPGA に送信する．すると FPGA がメインメモ
リに直接アクセスして結合演算を実行する．ハッシュ

図9

10000
1000001e+006
テーブルサイズ [Rows]

1e+007

1e+008FPGA による結合演算の性能比較．破線はモデルによる推測値，＋はソート・マージ結合，×印はハッシュ結結合の実装は，FPGA 内に 10 万行のデータを格納

合の実測値

でき，ソート・マージ結合に用いたソートツリーは 8
ウェイである．本実験での理論値のグラフにおいてをデータベースの演算に使用する研究は近年になっは，EH = 0.0001[s], ES = 0.005[s], M = 0とした．

て始まったばかりである [7]．データストリームに対

図 9 は両方のテーブルを同一サイズとして変化さするウィンドウ結合 [10] [11] は，FPGA がデータストせた時の実験結果である．テーブルの行数が少ない時

リームに対して効果的であることを示す良い例であは，ハッシュ結合が優位であるが，テーブルサイズがる．しかし，本論文が対象するのは永続化あるいは，大きくなるとソート・マージ結合が優位になることもすでにメモリ上に存在するテーブルに対する結合演確認できる．ハッシュ結合においては実行時間を概ね算であり，半永続的に到着するデータストリームとは予測できているが，ソート・マージ結合においては誤演算が異なる．FPGA による結合演算機構 [4] や，ク

差が見られる．なお，2 つの実装を使い分けるという

エリ処理エンジン [1] [2] [8] [9] も開発されているが，本観点からは，特に 2 つの曲線が交わる周辺のテーブ

論文のように結合演算の選択方法については議論さ

ルサイズにおいて正確な実行時間の予測が必要になれていない． [3] は本論文と同様に動的に FPGA をり，それ以外のテーブルサイズにおいて常に正確な実プログラムすることを提案しているが，対象が選択演

行時間予測が求められるわけではない．様々なテーブ算であり，結合演算に適用できるものではない．

ルサイズにおいて本モデルの精度を評価することと，
パラメータ v の実機を用いた決定方法の検討が今後

7 おわりにの課題である．

本論文では，結合演算の回路をクエリ処理時にFPGA にプログラムし直し，1 つの結合演算回路が6 関連研究FPGA のハードウェアリソースを占有できるように

専用ハードウェアを用いたデータベース処理は古くすることで，より高速に結合演算を実行する方法にからの研究課題であるが，動的再構成が可能な FPGA

ついて議論した．データベース分野において，クエリ

の性質に応じて結合演算のアルゴリズム決定することは従来からの研究分野である．しかし，ハードウェ
アの回路面積に着目して同様の最適化を考える必要があることを示したことが，本研究のユニークな点である．本論文ではハッシュ結合とソート・マージ結合を対象に議論を行ったが，同様のアイデアを他の結合アルゴリズムに適用することも可能である．今後，実際のデータベースエンジンに組み込むなどして，本切り替え手法の利点を実証すると共に，対象とする結合演算アルゴリズムを増やして詳しい性能評価を行いたいと考えている．本研究がハードウェア処理エンジンの発展の一助になれば幸いである．

謝辞 本研究で利用した FPGA カードの主開発チームである IBM Research - Austin の研究チームに感謝する．

参 考 文 献[ 1 ] Casper, J. and Olukotun, K.: Hardware Acceleration of Database Operations, FPGA 2014, FPGA
’14, New York, NY, USA, ACM, 2014, pp. 151–160.
[ 2 ] Chung, E. S., Davis, J. D., and Lee, J.: LINQits:

Big Data on Little Clients, Proc. ISCA 2013, 2013,
pp. 261–272.
[ 3 ] Dennl, C., Ziener, D., and Teich, J.: Acceleration of SQL Restrictions and Aggregations
through FPGA-Based Dynamic Partial Reconfiguration, FCCM 2013, April 2013, pp. 25–28.
[ 4 ] Halstead, R., Sukhwani, B., Min, H., Thoennes,
M., Dube, P., Asaad, S., and Iyer, B.: Accelerating Join Operation for Relational Databases with
FPGAs, Proc. FCCM 2013, pp. 17–20.
[ 5 ] Hayashizaki, H., Ito, M., Ueda, T., and Ohara,
M.: Variable-Length-Key Sorter on FPGA using
Tries, Proc. IWLS 2014, 2014.
[ 6 ] Hector Garcia-Molina, Jeﬀrey D. Ullman, J.
D. W.: Database Systems: The Complete Book,
2002.
[ 7 ] Mueller, R. and Teubner, J.: FPGA: What’s in
It for a Database?, SIGMOD ’09, 2009, pp. 999–
1004.
[ 8 ] Mueller, R., Teubner, J., and Alonso, G.:
Streams on Wires – A Query Compiler for FPGAs,
Proc. VLDB Endow., Vol. 2, No. 1(2009), pp. 229–
240.
[ 9 ] Najafi, M., Sadoghi, M., and Jacobsen, H.-A.:
Flexible Query Processor on FPGAs, Proc. VLDB
Endow., Vol. 6, No. 12(2013), pp. 1310–1313.
[10] Oge, Y., Miyoshi, T., Kawashima, H., and Yoshinaga, T.: An Implementation of Handshake Join on
FPGA, Proc. ICNC 2011, Nov 2011, pp. 95–104.
[11] Teubner, J. and Mueller, R.: How Soccer Players
Would Do Stream Joins, SIGMOD 2011.