数理解析研究所講究録
第 1799 巻 2012 年 100-102

100

GPU を用いた簡潔 trie の並列探索田中秀宗

田部井 靖生 *1$\dagger$

はじめに

近年，画像処理専用の演算装置であった GPU (GraphicsProcessing Unit) をより汎用的な計算に利用する動きがある．特に，数値計算や信号処理の分野では，GPU が広く活用され顕著な効果を得ている．本研究では，より汎用的な問題に対して GPU を活用することを究極的な目標とする．そのための 1 段階として，今回は，ある種の文字列検索問題を取り上げ，この問題に対する並列アルゴリズ
ムを GPU 計算のためのプログラミングモデルの 1 つである CUDA 上で実装し，その高速化効果を確かめる．

CUDA プログラミングモデル

2

図 1: CUDA の概要

CUDA とは，NVDIA 社が開発した汎用 GPU 計算のためのプログラミングモデルである 1. CUDA では，GPU上での処理はカーネルと呼ばれ，複数のスレッドによってカーネルが実行される．スレッドには階層が存在し，複数のスレッドの集まりをブロック，複数のブロックの集まりをグリッドと呼ぶブロック内のスレッドの数，ブロックの数には制限がある．各階層でスレッドがアクセスできるメモリに違いがあり，全てのスレッドからアクセスできる共有メモリをグローバルメモリ，同一ブロック内のスレッ3問題と既存の解法
次のような問題を考える:

入力文字列 (キー)
$Q_{1},$ $Q_{2},$$\ldots,$$K_{1},$ $K_{2},$$\ldots,$$K_{N}$, 文字列 (クエリ)$Q_{n}$

質問各 $i\in\{1, \ldots,n\}$ に対して，キーにと完全に一致する文字列はあるか$K_{1},$$\ldots,$$K_{n}$の中$Q_{l}$

ドからのみアクセスできる共有メモリをシェアードメモ
例えば，キーとして $K_{1}=$ ACT, $K_{2}=$ ACG, $K_{3}=C\Gamma G$ ,リと呼ぶそれぞれ，グローバルメモリは大容量であるがクエリとして $Q_{1}=$ ACG, $Q_{2}=$ ACC, $Q_{3}=$ CTG が与えら
低速，シェアードメモリは高速であるが小容量であるとい$Q_{3}\mapsto K_{3}(\perp$ はキーのれたとき，う特徴を持っている．ここまでで述べた CUDA の概要を 中に一致する文字列が無いことを表す) という対応関係を図示したものが図 2 である．この図では，人形でスレッ (例えば表の形で)$n=1$ の場合，すなわちク出力する．
ド，外側の大枠でグリッド，内側の枠でブロックを表して$Q_{1}\mapsto K_{2},$$Q_{2}\mapsto\perp,$

エリが 1 つだけの場合は，既存研究があり，いくつかのいる．

逐次アルゴリズムが知られている．

代表的な手法の 1 つに，高速にクエリを検索するために，キーを索引化する手法があるが，ここでは索引化した
湊離散構造処理系プロジェク ト．データを表現するデータ構造として trie 木を用いる．trieERATOJST
mail:yasuo. tabeiOgail. com
木は辺ラベル付きの木構造で，各辺にアルファベットが割$mail:tanaka7Ois$ . titech. ac.
東京工業大学情報理工学研究科，
1 このプログラミングモデルを実現するためのツール群が，Nvidia 当てられており，頂点から葉までのパスが 1 つの文字列$ip$$\dagger$社によって提供さ). れている (http$://www$. nvidia. comlobj $ect/cuda_{-}$

101
表 1: 実験結果 (1 ブロック，クエリ数 $n=100,000$ )クエ逐リ次長–l$m$$\ovalbox{\tt\small REJECT}|\acute\grave$$3.7687$$9.96174$$30.18348$$78.02696$

1.86

2.27

3.39

8.84

$\grave$-クエリ並列(202 倍)(438 倍)(891 倍)(883 倍)

9.65

trie 分割

15.09

11.10

22.89

(039 倍)(090 倍)(200 倍)(341 倍)

図 2: trie の例(単位は秒，括弧内は対逐次の高速化効果)に対応している．例え$K_{3}=$,$\ovalbox{\tt\small REJECT} \mathfrak{X}$

キーが $K_{1}=$ ACT,$K_{2}=$ACG,CTG のときの trie は図 3 のようになる．てのクエリの処理が終わるまでこの処理を繰返す．以後この手法を痂分割と呼ぶこととする．
実用的には，この trie を格納するための領域を節約する
ブロック数を複数使う場合は，クエリをブロック数で等ため，簡潔データ構造が用いられることが多い．簡潔デー
タ構造とは，表現するデータを極限まで圧縮した上で，少 分割し，各ブロックで上で述べた並列化手法を並列に行しの保持情報を付け加えることで，有用な問合せにも答え う．例えば クエリ数が $n=1000$ , ブロック数が 100 のられるデータ構造である．例えば，この問題を解くための 場合，各プロヅクには 10 個のクエリが割当てられる．

ライブラリ群である tx-trie ? は，木構造の簡潔データ構造である LOUDS ?, ? を利用している．
$[$$[$4$e$$]$$]$

並列化
前章で述べた trie を用いたアルゴリズムの並列化を行った．以降ではまず，ブロック数を 1 っとしたときの並列化手法について述べる．

まず，各クエリを各スレッドに割当て，別々のクエリに対して trie を並列に探索するという並列化手法が考えられる．この場合，trie とクエリをグローバルメモリに置き，各スレッドは割当てられたクエリの文字列を探索し，その結果をグローバルメモリに書き出す．以後この手法をクエリ並列と呼ぶこととする．

5実験
前章で述べた 2 つの手法と逐次アルゴリズムを実装し，実行時間の比較を行った．これらの手法は，tx-trie$[?]$を(ア$m$ 文字のゲノムのデータ基に実装した．入力には，ルファベット $\{A, C, G, T, N\}$ ,$N$は不明を表す) を $n$ 本用意し，キーとクエリの両方に利用した．実験環境は次の通り
である :

.
.
$0$

CPU: AMD Phenom X49850 $(2.5GHz\cross 4$ cores
GPU: Tesla C2070 $(1.15GHz\cross 448$ cores$)$$)$CUDA 4.0

次に，trie の各段を各スレッドに割当て，1 つのクエリ

trie 分割の場合，ブロック当たりのスレッド数はクエリに対して trie を並列に探索するという並列化手法を提案

長 $m$ となるが，比較のため，クエリ並列の場合でも，ブする．複数のクエリに対しては，パイプライン的に各クエリに対する処理を重ね合わせることで高速化を図る．この場合，trie とクエリをグローバルメモリに，スレッド数と同じ長さの配列をシェアードメモリに用意する．この配列には，各スレッドが次に探索を開始する trie の頂点番号が格納される．各ステップで，各スレッドはシェアードメ
モリの配列から頂点番号を，グローバルメモリから担当するクエリの文字を読み，1 段だけ探索し，その結果をシェ

ロック当たりのスレッド数をクエリ長 $m$ で設定する．

アードメモリの配列の次スレッドの担当部に書き込む．全ブロックが 1 つの場合

クエリ数 を 100, 000 で固定
し，クエリ長 $m$ を変化させたときの実行結果を表 5 に示
$n$す．クエリ数 $m$ を 348 で固定し，クエリ長せたときの実行結果を表 5 に示す．

$n$を変化さどの場合でも，クエリ並列が trie 分割より高い高速化効果を得た．しかし，入カサイズを大きくしていったとき，クエリ並列の高速化効果が頭打ちになっているのに対し，trie 分割の高速化効果は高まっている．これにより，大き102
表 2: 実験結果 (1 ブロック，クエリ長 $m=348$ ))$0,000$
クエリ数
1,000
100,000
10,000$1,$ $\alpha$

$n$

30.18
3.39

0303.020030.3

逐次クエリ並列

370.3466.48(915 倍)(903 倍)(891 倍)(557 倍)

0.20

trie 分割

15.09

1.55

162.91(156 倍)(195 倍)(200 倍)(227 倍)

表 3: 実験結果 (複数ブロック，ブロック数 32)
クエリ長 $m$

エ逐次–L
g$145.09174$だと考えられる．

全ての実験でクエリ並列が trie 分割を上回る結果となったが．これは trie 分割のメモリへの不連続アクセスによるものだと考えられる．trie の異なったレベルにある頂点は，LOUDS の場合，メモリ上の不連続な領域に格納される．CUDA では，グローバルメモリへの連続した領域へのアクセスが高速にできるという特徴があるが，これを活(単位は秒，括弧内は対逐次の高速化効果)$52.0287$

特徴が見られる．これは，前段階で行った，ブロックが 1つの場合のクエリ並列の特徴を受け継いだことによるものかせなかったことが，trie 分割が威力を発揮できなかった原因だと考えられる．

$370.34348$$\grave$$\acute\grave$44113.67

148

クエリ並列

(3525 倍)(3293 倍)(2710 倍)

6.30

4.17

trie 分割

16.24(1247 倍)(2302 倍)(2280 倍)(単位は秒，括弧内は対逐次の高速化効果)

なサイズの入力に対しては，trie 分割が効果を発揮すると考えられる．

6結論

本研究では，ある文字列検索問題に対して GPU 上での並列化手法を提案し，計算機実験で 35 倍程度の高速化効果を実現した．この研究を通しても，GPU を用いるとどのような手法を用いれぱ高速化できるのかは明らかになっていないのが現状である．今後，高速化できる手法を明らかにすることで，GPU の理論的計算モデルの構築，および GPU アルゴリズムの理論的解析など研究課題が生まれることを期待する．

をブロックが複数の場合 ここでは，クエリ数1, 000,000 で固定する．ブロック数を 32 で固定し，クエリ長 $m$ を変化させたときの実行結果を表 ?? に示す
また，クエリ長 $m$ を 348 で固定し，ブロック数を変化させたときの実行結果を表 5 に示す．
$n$クエリ長 87, ブロック数 32 のとき，クエリ並列で 3525倍の高速化効果が得られた．どの場合でも，trie 分割よりクエリ並列の方が高い高速化効果が得られている．2 つの手法とも，クエリ長を伸ばすと高速化効果が頭打ちになり，ブロック数にはあまり影響を受けないという共通した

表 4: 実験結果 (1 ブロック，クエリ長 $m=348$ )ブロック数3264

逐次$31_{-\vee}^{\backslash }70.34$

クエリ並列

1367

370.3413.84

128370.34
13.89

256
34370.3414.08(2710 倍)(2676 倍)(2666 倍)(2630 倍)trie 分割

16.24

17.72

17.32

17.82

(2280 倍)(2090 倍)(2139 倍)(2078 倍)(単位は秒，括弧内は対逐次の高速化効果)