簡潔データ構造のFPGA実装について

HDLアドベントカレンダー2015の記事です。
FPGAにwavelet treeを用いた簡潔データ構造を実装したという論文を紹介します。PDPTA'15(International Conference on Parallel and Distributed Processing Techniques and Applications)という学会で発表されたようです。
http://www.kameyama.ecei.tohoku.ac.jp/papers_pdf/PDP3384.pdf

簡潔データ構造とはビット列Bに対して

access(B,i) i番目のビットの値を返す
rank_q(B,s) 範囲s内にある文字qの数を返す
select_q(B,n) n番目に出現した文字qの位置を返す

の操作がデータ数に対して定数~logオーダーで行えるようなデータ構造であり、効率的な処理としてデータベースの全文検索やゲノムデータの検索に使われているそうです。gzipで使われている LZ78などの可逆圧縮されたデータの一部分を取り出すには通常全データを伸張しなければ行けないのですが、データの区切り部分に1,その他の場所に0をおいたビット列を索引として作っておくことで途中の文字列を取り出すことが出来るようになります(圧縮全文索引)。
ビット列Bに対して1の数を数えるpopcount処理を行うことでrankが分かり、selectはその逆関数といえるのでrankによる二分探索で計算できますが、n番目までの全てのビット列にpopcountを適用するのは時間がかかります。そのため一定間隔sごとにその位置までの各文字の累積出現回数を記録したrank tableに持たせておくのが効率的です。これによってrank_1(B,n)は
rank_table[n/s]+popcount(B[i//s])
と書かれます。popcountは以前LUTで書いたことがあり、またSSEにpopcount専用の命令もあるようですが、こちらのバージョン５のような処理をHDLで実装するとパイプライン化もできて良さそうです。

module popcount(
     input clock,
     input resetn,
     input [63:0] bits
     output reg [5:0] num);

    reg [63:0] bits1,bits2,bits3;

   always@(posedge clock or negedge resetn)
     if(!resetn)
          bits1<=0;
     else
         bits1 <= (bits & 0x5555_5555) + (bits >> 1 & 0x55555555);

   always@(posedge clock or negedge resetn)
     if(!resetn)
          bits2<=0;
     else
         bits2 <= (bits1 & 0x33333333) + (bits1 >> 2 & 0x33333333);

   always@(posedge clock or negedge resetn)
     if(!resetn)
          bits3<=0;
     else
         bits3 <= (bits2 & 0x0f0f0f0f) + (bits2 >> 4 & 0x0f0f0f0f);

   always@(posedge clock or negedge resetn)
     if(!resetn)
          bits4<=0;
     else
         bits4 <= (bits3 & 0x00ff00ff) + (bits3 >> 8 & 0x00ff00ff);

   always@(posedge clock or negedge resetn)
     if(!resetn)
          num<=0;
     else
         num<= (bits4 & 0x0000ffff) + (bits4 >>16 & 0x0000ffff);

endmodule

多ビットデータの配列に対してはwavelet treeというデータ構造で簡潔データ構造が実現できます。これはデータの各桁に対し

桁の値のビットを記録する
桁の値が0のもの,1のものを左右に分け、子とする

という手順で作成されるデータ構造です*1。
多ビットデータB、クエリーqに対しrank_q(X)の上限k、下限lは
k(q[i])=C(q[i])+rank_q[i](B,k(q[i-1])-1)
l(q[i]) =C(q[i])+rank_q[i](B,l(q[i-1]))-1

と再帰的な書き方をすることが出来ます(式(1),(2))。Cは文字aに対するrank tableでアドレスに対して単調に増加します。
FPGAでの実装では各桁のbit列を2つの部分headerとbodyに分け、headerに対するrank tableをLUTで実現しています(Fig. 6)。headerのサイズは2値データに対してはデータの総数Nのlogになり、残りがbodyのサイズになります。m値ビットを同時に処理する場合にはlog(m)*log(N)となります。bodyに対して1の個数を返すpopcount命令に相当する処理をLUTや並列の条件文を用いて実装することに成ります(Fig. 9)
FPGAや専用の回路(ASIC)では並列性を高めることの出来る一方、CPUやGPUに比べ動作周波数が遅いこと(100~300MHz程度)、メモリのバンド幅がGPUに比べると狭いことが不利な点です。そこでpopcountに比べbodyのサイズが大きい場合に処理単位(PE)を並列化させることも提唱されています(Fig, 7,8,10)。DRAMへの具体的なアクセス、スループットなどの定量的な結果は示されていませんが、その他に複数のクエリーを並列に実行したり桁ごとにパイプライン処理したりすることでスループットを稼ぐことが出来るかもしれません。DRAMの帯域と容量(2GB x 2個)がボトルネックとなっているのでこれ以上の大きなデータに対して検索を行うにはデバイスを並列につないで処理を行うか、DRAMを複数接続する構成のFPGAボード、ASICを作るしかないと思います。