DEIM Forum 2016 C6-5

効率的なテキスト処理を目指した
簡潔データ構造を用いるトライ木の GPU 上での実装
若月

駿尭†

欅

惇志††

宮崎

純††

† 東京工業大学工学部情報工学科 〒 152–8550 東京都目黒区大岡山 2-12-1†† 東京工業大学大学院情報理工学研究科 〒 152–8550 東京都目黒区大岡山 2-12-1
E-mail: †{wakatsuki,keyaki}@lsc.cs.titech.ac.jp, ††miyazaki@cs.titech.ac.jp
あらまし

大量の文書に対するテキスト処理を GPU を用いて効率的に行うために，GPU の特性を考慮した省メモ

リかつメモリへのランダムアクセスの少ない辞書データ構造の実装方式の提案を行う．GPU を用いたテキスト処理を効率的に行うためには，単語を ID に変換する大規模な語彙集合を扱う辞書データ構造が必要である．提案手法は
状態遷移表 (STT) によるトライ木と比較して 40 分の 1 以下のメモリ使用量であるとともに，辞書に含まれる語彙数が多い状況では STT より実行時間が短くなることが判明した．
キーワード

辞書，記号化，GPGPU，情報検索
そこで，自然言語文書における最小解釈単位は単語であるた

1. は じ め にめ，単語の語彙集合を扱うデータ構造としての辞書を用い，単コンピュータの普及や Web の隆盛により，大量の電子文書

語を一意な整数値の ID に変換することで，代わりに整数値が日々作成されている．これら大量の文書を利用するためには，ソートで済むようになる．GPU を用いた整数値ソートについ

文書中のテキストを高速に処理する必要がある．しかし，近年ては数多くの研究がなされており，広く使われている高速なラ

シングルコアプロセッサの性能向上は鈍化しており，逐次実行

イブラリ [4] が存在する．

による大幅な高速化は期待できない．そのため多数のコアをGPU が搭載するメモリは一般的にデータ処理に用いられる一つのチップに搭載することにより性能向上を目指す方向に進サーバが搭載するメモリと比べると少量である．また Web 文

んでいる．処理の並列化を行い，これら多数のコアを搭載する

書には固有名詞，人名，URL，メールアドレス等が含まれる

ハードウェアを活用することで，高速なテキスト処理を実現すため，大規模な語彙集合を，省メモリで格納可能な辞書データ

ることができると期待されている．

構造が求められる．しかし GPU 上で用いることのできる辞書

多数のコアを搭載したプロセッサは，メニーコアプロセッサと呼ばれている．GPU は 3D グラフィックスの描写を目的とデータ構造，特に簡潔データ構造を用いるものについては，ほとんど研究されておらず効率的な手法は明らかでない．

したメニーコアプロセッサであり，安価であるため広く普及し本稿では GPU 上で効率的に利用できる辞書データ構造につている．この GPU を汎用的な用途に応用する GPGPU が研いて議論する．簡潔データ構造を用いるトライ木の参照アルゴ

究開発されている．GPU はスーパーコンピュータのアクセラ

リズム [5] を GPU が不得手なメモリへのランダムアクセスが（注 1）など科学技術計算の応用が目立っ少なくなるよう効率的に実装する手法を提案する．評価実験にているが，データ処理に重点をおくデータインテンシブな分野

レータとして採用されるより，非圧縮なアルゴリズムと比べて辞書のメモリ使用量が少においても GPU を利用した研究が行われている [1, 2]．

なく，語彙数が多い状況では，より高速に単語から ID への変効率よく GPU を活用しテキスト処理を行うためには，以下のような課題がある．例えば高精度な情報検索で用いられる統換が可能であることを明らかにする．
本稿の構成は以下の通りである．2. 節では用語の定義および計量である各文書中の単語の出現頻度 (term frequency, TF)

本研究の基礎をなす技術について述べる．3. 節では GPU 上を求める際には，各スレッドが担当範囲の文書中での単語の出で簡潔データ構造を用いたトライ木による辞書の効率的な実装現を求めた後に，単語をキーとしてデータを配分し各単語の統手法を提案する．4. 節では提案手法を一般的な手法と比較する計量を求める．このデータ配分のために単語をキーとしたソー実験を行うことにより評価する．5. 節では本研究に関連する研トが用いられる．しかし GPU に適した高速な並列基数ソート

究について述べる．6. 節では結論および今後の課題について述は，単語などの可変長キーによるソートに対応できず，他の可べる．

変長キーソート手法では各スレッドに不規則な負荷が生じるな
ど [3] 効率的な文字列ソートは困難であり整数値ソートに性能が劣っている．

2. 基礎的事項
2. 1 用語の定義
本稿で用いる用語と記号の定義を行う．

（注 1）：http://www.top500.org/

長さ n のテキスト T を文字 c の並び T = c1 c2 c3 . . . cn と定義

する．c は有限な集合であるアルファベット Σ の要素であり，Σ の
0

要素数 |Σ| を σ で表す．英単語を考えたとき Σ = {a, b, . . . , z}，

表 1 状態遷移表

σ = 26 である．また，自然言語で書かれた文書は有限の語彙

a

b

c

から単語を並べることによって構成されている．語彙 L を定義
し単語 w は語彙 L の要素 w ∈ L であると定義すると，単語数

1

4

8

m のテキスト T は単語 w の並び T = w1 w2 w3 . . . wm と表す
b

ことができる．

2. 2 辞

書

5

a
2

b

b
6

7

c
9

辞書はキーと呼ぶ文字列の集合を扱うデータ構造である．
キーの集合とその文字列に関する付帯情報 (ID や説明など) をa

あらかじめ辞書に登録する．その後この辞書を利用して，あるキーが辞書に含まれているか否かを判定することができ，含ま3

れているのであればその付帯情報を取り出すことができる．

N

a

b

c

0

1

4

8

1

-1

5

-1

2

-1 -1 -1

3

-1 -1 -1

4

2

6

5

3

-1 -1

6

-1 -1 -1

7

-1 -1 -1

8

-1

9

-1 -1 -17

-19

図1 トライ木

巨大な語彙を扱う必要のある分野，または使用できるメモリの限られた環境下では，低速な二次記憶ではなくメインメモリ，
さらにはより高速なプロセッサのキャッシュに収めることができるような，メモリ使用量が少なく，かつ高速な操作が行える辞書が理想である．Martı́nez-Prieto らは理論上だけではなく実用的な実際のメモリ使用量と実行時間に着目し，さまざまな
圧縮辞書データ構造の比較実験を行っている [6]．
以降では辞書を単語の集合を扱うデータ構造として扱い，付
帯情報は単語の ID とする．

1 にも現れているように遷移先が −1，すなわち遷移できないことを示すセルが占める割合がかなり多く，必要なメモリ領域が大きいという課題がある．STT に必要なメモリ領域はトラ
イ木のノード数を t，ノード番号を 4 バイト整数で表すとすると 4σt バイトとなる．

2. 2. 3 簡潔データ構造を用いたトライ木
本研究ではメモリ使用量と実行速度のバランス，GPU への適合性を考慮し Hon らによる Prefix Matching アルゴリズム [5]2. 2. 1 辞書符号化をもとにすることにした．以降では当アルゴリズムについて述

語彙 L を辞書を用いて表現し，各単語 w に一意な整数値のべる．

単語 ID を割り当てる変換 fL : w → i を考える．テキスト T
を文字 c の並びとして表現するのではなく，fL を用いて単語

w の ID i の並び T = i1 i2 i3 . . . im として表現する．そうすると二つの単語の等価を確認する処理では，低速な文字列同士の比較ではなく，高速な整数値同士の比較として処理できる．また，テキストが極端に短い単語で構成されていない限り，テキストを格納するために必要なメモリ領域は少なくなる．これを辞書符号化と呼ぶ．
森谷らが行った GPU を用いた MapReduce による索引語重
み付けにおいて，Shuﬄe ステップ時の語のソートにおける文字列比較が，処理時間全体の大部分を占めていることが報告されている [7] ことからも，辞書符号化を行うことで実行時間を減少させることが可能であると期待される．Bazoobandi らは

RDF に対する辞書符号化のための，動的に辞書が更新される
状況下での，メモリ使用量の少ないコンパクトなトライ木を提案している [8]．

2. 2. 2 STT を用いたトライ木
トライ木 [9] は可変長キーを用いて情報を取り出すためのデータ構造である．トライ木はエッジに文字 c のラベルが付与されている木構造である．キーを一文字ずつ取り出し，木のルート
からその文字に対応するラベルを持つエッジをたどりノードを移動することにより，目的のキーの情報を取り出すことができる．例として aba, ba, bb, cb, cc をキーとしたトライ木の具体例
を図 1 に，状態遷移表 (state transition table, STT) を表 1 に示す．
この STT によるトライ木の実装は最も高速 [8] であるが，表

当アルゴリズムは簡潔データ構造を用いたトライ木によりPrefix Matching を行う．トライ木のノードは，対応する接頭辞を逆順に並び替えた文字列 (reverse prefix) の，辞書順を用いてルートを 0 として順序付けられている．この順序をノードを表す番号とし，各接頭辞の ID としても用いる．図 1 に各ノードに前述の方法で番号を付けた aba, ba, bb, cb, cc を持つトライ木の図を示す．
各文字ごとに，あるノードにおいてその文字で次のノードに遷移可能な場合は 1，そうでない場合は 0 をノードの番号順に並べたビット列を構築する．これらのビット列を利用してノード x から文字 c を用いて遷移した先の子ノード x′ を求める方
法について説明する．
まずノード x から文字 c で遷移可能であるか否かは c のビット列 (Bc ) の x 番目のビットを見ることで判断する．ノード

x に対応する接尾辞を P とすると，P の後に文字 c をつなげてできる文字列は P c と表せる．P c が辞書に含まれているな
らば，接尾辞 P c に対応するノード x′ が存在する．ここで各ノードは reverse prefix の辞書順に並んでいるため，ノード xは文字 c で遷移できるノードの中で，何番目であるか Bc を調べることで求めることができる．この関数を rank(x, Bc ) と表
す．すなわち文字 c で始まるノードの中で何番目か分かり，Pを逆順に並び替えた文字列を Q とすると，求めたいノードのreverse prefix は cQ であるので，文字 c で始まる最初のノードの番号 C[c] を予め記憶しておくことで，cQ のノード番号は

x′ = rank(x, Bc ) + C[c] と求められる．各ノードから遷移する

Algorithm 1 rank(x, Bc ) を求めるアルゴリズム

a

ab
0

aba
1

b

b

ba

bb

bc

2

ba

bb

c

cc

3
bc

1: function rank(x, Bc )2:u ← x/s▷ x の属するスーパーブロック3:o ← rank[Bc ][u]▷ ビット列の先頭からのランク

4:p ← pointer[Bc ][u]5:v ← x/t

6:

for i = u × s/t to v − 1 do

7:8:

C[b]=4
図2•

ルートノード 0 から文字 b で遷移した先の子ノード′

x = rank(0, Bb ) + C[b] = 0 + 4 = 4•▷ ランクを加算( t )p ← p + ⌈log K[i]⌉9:end fork ← K[v]

各ノードから b で遷移する際の例

様子を図 2 に示す．以下に遷移先ノード番号の計算例を示す．

o ← o + K[i]

10:
11:

▷ ポインタ▷ x の属するブロック▷ ポインタを加算▷ ブロック v の組 (k, r) を取得
( t )
( t )
r ← R(p, ⌈log K[v]⌉) ▷ p ビット目から ⌈log K[v]
⌉ ビット

読み出し
12:

b ← Decode(k, r)

13:o ← o + Popcount(b, x mod t)

14:

return o▷ 組 (k, r) を元のビット列に復元▷ x までの 1 の数を加算

15: end function

ノード 8 から文字 b で遷移した先の子ノード′

x = rank(8, Bb ) + C[b] = 3 + 4 = 7格である OpenCL と NVIDIA による独自規格の CUDA [12]rank 関 数 を サ ポ ー ト す る ビット 列 の デ ー タ 構 造 と し てがある．本稿では NVIDIA 製の GPU を使用し，GPU のアー

RRR [10] と呼ばれる簡潔データ構造が用いられている．この手( )法は O(1) 時間で rank 関数が実行でき，log ntc + o(nc ) ビット

キテクチャを考慮した実装を試みるため CUDA を使用する．

のメモリ領域で格納できる．ここで t は全てのノード数, nc はのアーキテクチャについて述べる．

文字 c で遷移可能なノード数である．

実験で使用する NVIDIA GeForce GTX 970 を例として GPU

2. 3. 1 GPU のアーキテクチャ

この結果を用いることで簡潔データ構造によるトライ木は，GPU は ストリーミングマルチプロセッサ (SM) を複数束ねある文字列 P に対して文字列から ID を求める操作を O(|P |)た構成になっており，例えば本研究で使用する GTX 970 には

時間，トライ木を tH0 (X) + O(t) ビットのメモリ領域で格納13 基の SM が搭載されている．各 SM には 128 基の CUDA

できることが示されている [5]．ここで H0 (s) は文字列 s の 0

Core と レジスタ，キャッシュ，ワープスケジューラ等が含ま

次経験エントロピー，X はトライ木の XBW string である．

れる．GTX 970 のコア数は合計で 1664 となる．GPU で実行

2. 2. 4 rank 関数をサポートするビット列

されるプログラムであるカーネルは CPU から起動され複数の

RRR はまずビット列を長さ t のブロックに分割し，各ブロッ

SM において並列に実行される．複数のスレッドはブロックとクはブロック内の 1 の数，クラス k により分類される．各クラ( )ス k に含まれる要素は kt 個である．各ブロックはクラス k という単位でまとめられ，ブロック内のスレッド数とブロック数

要素の番号 r の組 (k, r) で表現される．組 (k, r) と元のビット当てられ，カーネル内からこの値を用いることができる．

列間の変換はテーブルを用いる方法と，二項係数を用いて計算を指定して起動される．各スレッド，ブロックには ID が割り

2. 3. 2 GPU のメモリ階層する方法 [11] がある．k は ⌈log t + 1⌉ ビットで配列 K に，r( )は ⌈log kt ⌉ ビットで配列 R に格納する．k は固定長なので k

上に 4GB の DRAM が搭載され，理論上では 224GB/s といを格納する配列 K を用いて任意のブロックの k をただちに取う高いバンド幅を持つ．しかし，理論値に近いスループットが得することができるが，r は各ブロックの k により長さが定ま達成できるのはある程度長い範囲をシーケンシャルアクセス

る可変長なので配列 K から目的のブロックまで k を取得しポする場合のみであり，細かい粒度でのランダムアクセスではス

インタを計算する必要がある．加えて，ビット列の先頭からのループットが低下する．ランダムアクセスの際のスループット

ランクとポインタを持つスーパーブロックを s ビットごとに一は，一度のアクセスの際のデータサイズが小さいほど，ランダ

つ用意する．このデータ構造を用いて rank(x, Bc ) を求めるア

ムアクセスの範囲となるメモリ領域が広いほど低下する [13]．

ルゴリズムを Algorithm 1 に示す．

GTX 970 には GPU が利用できるメモリ領域としてボードチップ内にあるメモリ領域として L2 キャッシュ，Unified

2. 3 GPGPU

L1/Texture キャッシュのほか，同一ブロック内のスレッドはそ

3D グラフィックスの描写を目的として浮動小数点演算性能

れらの間で共有されるメモリ領域であるシェアードメモリを利とメモリバンド幅を向上させている GPU (graphics process-用できる．これらのメモリ領域は高いバンド幅と低いレイテン

ing unit) [12] を，3D グラフィックス以外のこれまで CPUシを持つが容量は限られている．

が使用されてきた用途に利用する GPGPU (General-purpose

computing on GPU) が研究されている．
GPGPU のための主なプログラミングモデルとして，標準規2. 3. 3 ワ ー プ
各スレッドは 32 スレッドごとにワープという単位でまとめられており，ワープ内のすべてのスレッドは同じ命令が実行さAlgorithm 2 単語単位で並列にトライ木をたどるアルゴリ

Algorithm 3 提案手法による遷移関数

ズム

1: function ChildNode Proposed(x, c)

1: i ← blockIdx.x × blockDim.x + threadIdx.x

2:

2: while i < m do

3:3:b ← begin[i]4:4:l ← length[i]5:5:node ← 0

6:

end if

6:

for k = 0 to l − 1 do

7:

return x′

7:c ← string[b + k]

8:

if getbit(x, Bc ) = 1 thenx′ ← rank(x, Bc ) + C[c]elsex′ ← −1

8: end function

node ← ChildNode(node, c)

9:

end for10:

result[i] ← node11:i ← i + blockDim.x × gridDim.x

12: end while

れる．そのためプログラム中の分岐により各スレッドが異なる
実行パスをたどっている場合，各スレッドは自らの実行パス以外の命令による結果を破棄しつつ順次すべてのパスが実行されることになる．これを warp divergence と呼び，性能低下の原因となる．

DRAM へのアクセスは 32, 64, 128 バイト のメモリトラン
ザクションにより行われる．ワープ内のスレッドのメモリアクセスが上記のメモリトランザクション内に収まるとき，メモリ
アクセスはコアレスされると呼び，最も効率が良いのはワープ内の各スレッドの 4 バイトアクセスが一つの 128 バイトメモリ
トランザクションで行われる場合である．

3. 提 案 手 法
3. 1 テキストの表現
本稿では辞書符号化を行うテキストはあらかじめ前処理等が行われ，各単語の位置と長さが判明していると想定する．具体的には図 3 に示すように string 配列に処理するテキスト全体，

begin 配列に各単語の位置，length 配列に各単語の長さがそれぞれ記録されているとする．

3. 2 並列化手法
GPU の利用にあたっては GPU の持つ 多数のコアを用いて並列に処理を行うことによって性能を引き出す必要がある．ト
ライ木を用いて ID への変換をする際には単語の始めの文字から 1 文字ずつ遷移していくことで ID が求まる．それぞれの単語は独立に辞書を用いて ID への変換が可能である．ゆえに各スレッドが 1 単語ずつ変換処理を行うことにより多数のコアを有効活用することができる．
単語単位で並列に処理を行うアルゴリズムを Algorithm 2 に示す．全スレッド数 N 並列に単語の処理を行う．各スレッド i
は k を自然数として，入力テキスト全体の単語数以下の i + kN
番目の単語の処理を担当する．隣り合うスレッドは隣り合う単語を処理するため，配列 begin, length, result へのアクセスは
必ずコアレスアクセスになり効率的である．

3. 3 遷 移 関 数
トライ木の実装にあたっては， Algorithm 2 に含まれる，あるノード x から入力の文字 c による遷移先の子ノード x′ を求める遷移関数 ChildNode をどのように実現するかにより，性能やメモリ使用量は大きく変わる．GPU 上で動作させる遷移関数として求められる点を以下にまとめる．

•

比較的少量なメモリで利用可能であること•

ランダムアクセスの少ない手法であること•

キャッシュを有効活用できる手法であること•

実行パスの分岐が少ないアルゴリズムであることゆえに本研究では省メモリな遷移関数を実現する 2. 2. 3 節にて述べたアルゴリズムを採用し，新たな遷移関数 Algorithm 3を提案する．

3. 4 実装2. 2. 4 節で述べたビット列の実装として CPU 上で動作するライブラリでは sdsl [14] などいくつか存在するが，GPU 上で利用できるライブラリは存在しない．ブロックサイズなどの各パラメータは理論上ビット列の長さ n に依存して決まるが，実装するうえで可変なパラメータで効率的な実装をすることは難しいため，固定したパラメータが用いられる．まずブロックサ
イズ t は 15 ビットとする．これによりブロックのクラス k がとりうる値の範囲 [0, . . . , 15] は 4 ビット整数を用いて表現できるため無駄が生じない．スーパーブロックは 16 ブロックごとに一つ置く．このときランク，ポインタ，ブロックのクラス 16個の合計が 16 バイトとなる．これらを一つのサイズ 16 バイトの構造体としてまとめて格納することで，CUDA のベクトルデータ型による一度の 16 バイトアクセスで必要なデータをレジスタに取得できるため効率的である．
符号列から元のビット列の復号に関してはテーブルを用いて行う．このテーブルはエントリ数 215 ，エントリサイズ 2 バイ
トのため合計で 64 キロバイトである．
こ れ ら の デ ー タ は 繰 り 返 し 用 い ら れ る た め Unified

L1/Texture キャッシュにキャッシュするよう設定する．一方入力となる begin, length, string 配列は一度アクセスした後に再びアクセスされることはないのでこれらのデータはキャッシュしないよう設定し，辞書データがキャッシュから追い出されることを防ぐ．
各クラスの r が要するビット数，テーブルにアクセスする際のオフセットは定数としてシェアードメモリにキャッシュする．
それぞれ要素数は 16 なのでバンクコンフリクトは生じない．

begin0

612length

18

22

...

o

r

5

5

5

3

4

...

a

m

e

t

string
l

o

r

e

m

i

p

s

u

m

d

o

l

s

i

t

...

図 3 テキストの表現

Algorithm 4 状態遷移表 (STT) による遷移関数
100GB

1: function ChildNode STT(x, c)x′ ← ST T [x][c]

10GB

3:

return x′

1GB

4: end function

100MB

4. 評 価 実 験

辞書サイズ

2:

簡潔データ構造を用いたトライ木
STT

10MB
1MB
100kB
10kB

4. 1 実 験 準 備

B
1G
B
0M
10
B
M
10
B
1M
B
0k

10

B

B

抽出することで用意した．なお，単語は全て小文字化処理され

kB

10

0

1k

B

B

となる単語を除外して，4,000 万種類の単語とその出現頻度を

10

gory B に含まれる英文 Web 文書 5,000 万ページから，ノイズ

10

1kB
100 B
1

実験に用いる語彙は TREC の公開する ClueWeb09 Cate-

語彙サイズている．すなわち Σ = {a, b, . . . , z}，σ = 26 である．
図4

各実験において k 単語を辞書として使用する際には 4,000 万辞書データ構造のメモリ使用量

種類の単語からなる語彙集合 L から出現頻度の高い上位 k 単
語を取り出した部分集合 Lk ⊂ L を使用する．

4.0GB

入力として与える単語数 m のテキストとして以下の二種類

3.5GBを使用する．
出現頻度による合成テキスト Tf req•

一様分布による合成テキスト Tunif

Tf req は出現頻度に基づく離散分布により Lk から m 回復元抽
出，Tunif は一様分布により Lk から m 回復元抽出して得た合成テキストである．

3.0GB
メモリ使用量

•

2.5GB
2.0GB
1.5GB
1.0GB

本稿では GPU を用いたテキスト処理の一部として組み込

500.0MB

むことを想定し処理対象のテキストおよび辞書はあらかじめ

0.0 B
10
M

7M
5M

いことを想定する．従って，一度構築した辞書は再構築しない．

4M

含まない．また，辞書として使用する単語は頻繁に更新されな

3M

結果における実行時間は CPU ↔ GPU 間のデータ転送時間を

2M
1M K
0
50 K
0
10
K
50
K
10

GPU のメモリに配置されているとする．そのため以降の実験

STT
提案

語彙数 k
図 5 全体のメモリ使用量，Tf req ，m = 100M

状態遷移表 (STT) を用いた遷移関数の実現法 (Algorithm 4)と，提案手法による遷移関数の実現法 (Algorithm 3) を比較す

モリ使用量について提案手法は STT と比べて大幅に省メモリる．並列化手法は Algorithm 2 を双方に用い，遷移関数のみそである．辞書に含まれる単語の語彙数が 1,000 万，語彙サイズ

れぞれの手法に変更した．

100MB のとき，辞書のメモリ使用量は STT は 2.9GB である以降の実験は Intel Core i7-6700K (4.0GHz, 4 コア), DDR4

16GB, NVIDIA GeForce GTX 970 (1.05GHz, 1664CUDA コ
ア, 4GB), Ubuntu 14.04, CUDA 7.5. を用いて行った．

4. 2 メモリ使用量
図 4 に辞書データ構造のみのメモリ使用量を示す．辞書のメのに対して，提案手法では 58MB である．
図 5 に辞書やテキスト等，評価実験において使用された合計の GPU メモリ使用量を示す．入力として単語数一億のテキスト Tf req を与えており，入出力の占めるメモリ領域は約 1.7

1500
STT(100K)
提案 (100K)
STT(10M)
提案 (10M)

450
350

0.8

300

ナノ秒

実行時間 (ミリ秒)

400

STT
提案

250
200

0.6
0.4

150
100

0.2

50
0

0
M
10
7M
5M

図6

4M
3M

2M
1M
0K
50
0K
10
K
50
K
10

00
14

00
12

00
10

0

80

0
60

0

40

0

20

0

入力テキストサイズ (MB)

語彙数 k

入力テキストサイズによる性能特性

図 7 一文字あたりの実行時間，Tf req , m = 100M

GB である．実験に使用した GPU の搭載するメモリ容量は

1

4GB であり，語彙数 10M 以降では STT は GPU メモリの不足により実行できない．一方提案手法は語彙数 10M の場合で

STT
提案

0.8

対応でき，残りのメモリ領域をより多くのテキストを格納するためにも使用することができる．

4. 3 入力テキストサイズによる性能特性

ナノ秒

も 58MB のメモリ使用量であるため，より多くの語彙数にも0.6
0.4

次に実行時間について示す．ブロック数，スレッド数については複数の組み合わせで実行し最短の実行時間を採用した．図6 は語彙数 100K (100,000) と 10M (10,000,000) の場合につ0.20が，提案手法は語彙数による実行時間の変化が小さい．また，
語彙数 10M の場合の STT は辞書の占めるメモリ使用量が大
きいため処理できる入力テキストサイズは最大で約 350MB となっている．

4. 4 語彙数の大小による性能特性
辞書に載せる語彙数を変化させたときの実行時間について示
す．実行時間は処理する文字数に依存するため一文字あたりの実行時間を示している．入力として単語の出現頻度を考慮し実際のテキストを模した単語数一億のテキスト Tf req を与え，IDに変換したときの実行時間を図 7 に示す．語彙数が 3M より少ないときは STT が提案手法より高速であるが，語彙数 3Mの時点で逆転し提案手法の実行時間の方が短くなる．今回実験した語彙数の範囲では STT は語彙数が増えるに従って実行時間が増大していくが，提案手法はゆるやかな上昇にとどまっている．

4. 5 テキスト特性による性能特性
入力として一様分布で作られた単語数一億のテキスト Tunifを与え， ID に変換したときの実行時間を図 8 に示す．STT，

M

例している．STT は語彙数によって実行時間の変化が大きい

10

いずれの場合についても実行時間は入力テキストサイズに比

7M
5M

語彙数 k

系列の右端の点は GPU メモリを超過しない最大の入力テキス
トサイズを処理したときの実行時間となっている．

4M

STT と提案手法の実行時間をグラフに示したものである．各

3M

10

2M
1M
0K
50
0K
10
K
50
K

いて，入力テキストサイズを約 50MB ずつ増加させたときの

図 8 一文字あたりの実行時間，Tunif , m = 100M

提案手法ともに語彙数が増加すると実行時間が長くなり，増加
率は Tf req と比べて大きい．この差はテキストの性質の差によるものと考えられる．一様分布では語彙に含まれる出現頻度の低い単語も全て同じ確率で抽出される．出現頻度の低い単語は単語長が長いことが多く，結果としてテキストに含まれる単語
長のばらつきが大きくなる．テキスト中の単語長の平均および分散を表 2 に示す．Tunif は語彙数が増加すると単語長の分散が増加する．
単語長のばらつきはスレッド間の負荷のばらつきを生じさせる．特にワープ内のスレッドは同期して実行されるため，ワー
プ内のすべてのスレッドはワープ内でもっとも長い単語を処理しているスレッドが終了するまで待機することとなる．そのため単語長のばらつきが大きいほど待機状態となるスレッドが増加し実行効率が低下する．メモリアクセスのみで遷移可能な

STT と比べて提案手法はランク計算に必要な演算量が多いた
め実行効率低下の影響がより大きく，実行時間が増加したと考えられる．

表 2 テキスト中の単語長の平均，分散
語彙数

Tf reqTunif

10K 100K

1M

10M

平均

4.55

4.78

4.84

4.86

分散

6.34

6.91

7.09

7.24

平均

6.66

7.12

7.84

9.44

分散

6.42

7.04

8.32

17.2

5. 関 連 研 究
田部井らは木構造の簡潔データ構造である LOUDS を利用したトライ木を用いて GPU 上での並列探索を試みている [15]．
並列化手法として各クエリを並列に処理するクエリ並列と，トライ木の各深さにスレッドを割り当て，パイプライン的に並列化するトライ分割の二種類を提案している．

メモリ使用量（対数）10.0GB

ゲノムデータを対象とした評価を行っており，σ = 5 で辞書

STT
提案

1.0GB

に使用するゲノムパターン数は最大で 1M まで実験が行われている．実験結果としてクエリ並列がトライ分割よりも高速であり，逐次アルゴリズムと比べて最大で 35 倍程度の高速化を達

100.0MB成している．しかし GPU を用いてどのような手法を用いると高速化が達成できるのか明らかではなく，GPU の理論的計算

10.0MB

モデルや GPU アルゴリズムの理論的解析が求められると結論
1.0MB付けている．

100.0kB

全文索引アルゴリズムの GPU 上での高速化法を提案していChacon らはゲノム配列を対象として FM-Index と呼ばれる
10
M

7M

5M
4M

3M

K

2M
1M K
0
50 K
0
10
K

50

10

る [13]．FM-Index は本稿で用いた 2. 2. 3 節で述べたアルゴリ
ズムに類似した原理を用いるアルゴリズムであるが，この研究

語彙数 k

では簡潔データ構造を用いていない．ゲノムデータを対象とし

図 9 辞書データ構造のメモリ使用量，σ = 256

た評価を行っており，少ない文字種であることを利用したアルゴリズムの改善を行った．また FM-Index はランダムアクセスが必要なアルゴリズムであるので，GPU が不得手とするラン

1
STT
提案

0.8

ダムアクセスを減少させ，かつワープ内の複数のスレッドが協調してメモリアクセスを行うことでコアレスアクセスとなるメ

ナノ秒

モリアクセスにする工夫を行っている．実験結果としてマルチ
0.6

コア CPU と比べて 8 倍，NVIDIA 社による GPU 上で動作するバイオインフォマティクスライブラリである NVBIO に含0.4

まれる FM-Index の実装と比べて 3 倍から 5 倍の高速化を達成している．

0.2

Lin らはパケット中から攻撃パターンを検出する侵入検知シ
ステムを対象として GPU を用いたマルチパターン完全一致

0
M

10

7M

5M

4M
3M

2M
1M
0K
50
0K
10
K
50
K

10

語彙数 k
図 10 一文字あたりの実行時間，Tf req , m = 100M, σ = 256

マッチングを行う状態遷移表によるアルゴリズム PFAC を提案している [16]．あくまで特異なパターン検出が主目的であり，本研究の目的であるすべての単語を ID に変換するような用途は考慮されていない．また実験に使われているパターン数は数
万にとどまっている．

4. 6 文字種が 256 種類の場合
これまで文字種は σ = 26 種類として実験を行ってきたが，数字や記号を含む単語も語彙として扱いたい場合や英語以外の単語を語彙として扱いたい場合には任意の 1 バイトを文字とし

本提案は文字種，語彙数ともに多い辞書を使用することを想定し，簡潔データ構造を用いたトライ木 [5] を， GPU 上で効率的に動作させるという点で，これらの研究とは異なる．

6. お わ り にて処理する方法が考えられる．1 バイトで表すことのできる文字種は最大で 256 個のため σ = 256 とした場合の実験を行っ

本稿では大量の文書に対するテキスト処理を GPU を用いてた．ただし実験に用いたデータはこれまでと同様に英単語のみ

効率的に行うために必要となる，単語を ID に変換する辞書とである．図 9 にメモリ使用量，図 10 に実行時間を示す．σ がして，簡潔データを用いた省メモリなトライ木の GPU 上での26 から 256 に増加したためメモリ使用量はどちらの手法も約実装方法を提案し，評価実験を行った．

10 倍に増加している．提案手法と STT の実行時間が逆転する

その結果，提案手法は STT と比べて 40 分の 1 以下のメモ

語彙数は 500K となり STT の実行時間はメモリ使用量に依存

リ使用量となった．単語を ID に変換する処理速度については，していることが分かる．

語彙数が少ない場合には 提案手法 は STT よりも低速である
が，語彙数が多い場合については提案手法は STT よりも高速となった．語彙数が 700 万単語のとき提案手法は STT と比べて 16%高速であった．また，処理するテキストの特性として単語長の分散が処理速度に大きく影響し，分散が大きい場合には大きく性能が低下することが分かった．
今後の課題として，本稿では最も単純な並列化手法を用いたが，各単語の処理時間は単語長に依存するため，各タスクの処
理時間を考慮してスレッド間での負荷分散を行うスケジューリ
ング手法を用いることで性能向上の余地があると考えられる．
辞書データ構造の構築については辞書が頻繁に更新されるものではないとして本稿の範囲には含めていないが，効率的な構築法は応用先を広げるためには重要だと考えられる．
今回は合成したテキストを利用したが，実際のテキストでの実験も行い，索引語重み付け計算 [7] を高速化するために利用
したい．

謝

辞

本研究の一部は，科研費基盤研究 (B)(課題番号:15H02701)，
挑戦的萌芽研究 (課題番号:26540042) の支援による．ここに記して謝意を表す．

文

献[1] Yongpeng Zhang, Frank Mueller, Xiaohui Cui, and Thomas
Potok. Data-intensive document clustering on graphics processing unit (GPU) clusters. Journal of Parallel and Distributed Computing, Vol. 71, No. 2, pp. 211 – 224, 2011.
[2] Wenbin Fang, Bingsheng He, Qiong Luo, and Naga K.
Govindaraju. Mars: Accelerating mapreduce with graphics
processors. IEEE Transactions on Parallel and Distributed
Systems, Vol. 22, No. 4, pp. 608–620, 2011.
[3] Andrew Davidson, David Tarjan, Michael Garland, andJohn D. Owens. Eﬃcient parallel merge sort for fixed andvariable length keys. In Proceedings of Innovative Parallel
Computing (InPar ’12), pp. 1–9, May 2012.
[4] Nathan Bell and Jared Hoberock. Thrust: A productivityoriented library for cuda. In Wen-mei W. Hwu, editor, GPU
Computing Gems Jade Edition, chapter 26, pp. 359–372.
Morgan Kaufmann Publishers Inc., Oct 2011.
[5] Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V.
Thankachan, and Jeﬀrey Scott Vitter. Faster compressed
dictionary matching. Theoretical Computer Science, Vol.
475, pp. 113 – 119, 2013.
[6] Miguel A. Martı́nez-Prieto, Nieves Brisaboa, Rodrigo Cnovas, Francisco Claude, and Gonzalo Navarro. Practical compressed string dictionaries. Information Systems, Vol. 56,
pp. 73 – 108, 2016.
[7] 森谷祐介, 欅惇志, 宮崎純. GPU を用いた MapReduce による高精度検索のための高速な重み計算. 第 7 回データ工学と情報
マネジメントに関するフォーラム (DEIM 2015), 2015. Article
No. G3-6.
[8] HamidR. Bazoobandi, Steven de Rooij, Jacopo Urbani,
Annette ten Teije, Frank van Harmelen, and Henri Bal.
A compact in-memory dictionary for rdf data. In Proceedings of the 12th European Semantic Web Conference(ESWC2015), pp. 205–220, May 2015.
[9] Edward Fredkin. Trie Memory. Communications of theACM, Vol. 3, No. 9, pp. 490–499, Sept 1960.
[10] Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti.
Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms, Vol. 3, No. 4, Nov 2007. Article No.

43.
[11] Gonzalo Navarro and Eliana Providel. Fast, small, simple
rank/select on bitmaps. In Proceedings of the 11th International Conference on Experimental Algorithms, SEA’12,
pp. 295–306, Berlin, Heidelberg, 2012. Springer-Verlag.
[12] NVIDIA. CUDA Toolkit Documentation. http://docs.
nvidia.com/cuda/.
[13] A. Chacon, S. Marco-Sola, A. Espinosa, P. Ribeca, and J.C.
Moure. Boosting the FM-Index on the GPU: Eﬀective techniques to mitigate random memory access. IEEE/ACM
Transactions on Computational Biology and Bioinformatics, Vol. 12, No. 5, pp. 1048–1059, Sept 2015.
[14] Simon Gog and Matthias Petri. Optimized succinct data
structures for massive data. Software: Practice and Experience, Vol. 44, No. 11, pp. 1287–1314, 2014.
[15] 田部井靖生, 田中秀宗. GPU を用いた簡潔 trie の並列探索. 数理解析研究所講究録, Vol. 1799, pp. 100–102, Jan 2012.
[16] Cheng-Hung Lin, Chen-Hsiung Liu, Lung-Sheng Chien, andShih-Chieh Chang. Accelerating pattern matching using anovel parallel algorithm on GPUs. IEEE Transactions on
Computers, Vol. 62, No. 10, pp. 1906–1916, Oct 2013.