DEIM Forum 2013 E2-4

長大な拡張文字列パターンに対する GPU による高速な文字列照合
笹川 裕人†

喜田 拓也†

有村 博紀†† 北海道大学大学院情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目
E-mail: †{sasakawa,kida,arim}@ist.hokudai.ac.jp
あらまし

数千個のパターンを照合する大規模並列文字列照合は，ネットワーク不正侵入検出や生物情報処理など，

広い応用分野において重要な基盤技術である．しかし，大規模文字列照合は，計算負荷が非常に大きな処理であり，CPU 上の実時間処理は難しい．そのため，GPU を用いたハードウェアによる高速化が注目されている．そこで本稿
では，筆者らが提案した，NFA の階層的なモジュール分割に基づくビット並列照合アルゴリズム RunNFA を GPU 上の並列実装へ拡張する手法を提案する．階層的モジュール分割によるモジュール間の並列実行と，ビット並列手法によるコンパクトな NFA 表現と，高速な遷移計算により，GPU 上での拡張文字列パターンに対する高速な文字列照合を実現する．提案システムの性能評価のため，CUDA による GPU 上での実装を与え，計算機実験によってその有効
性を示す．
キーワード

文字列照合，並列処理，GPGPU，拡張文字列パターン，正規表現照合

GPU Acceleration of Faster String Matching for Very Long Extended
Patterns
Hirohito SASAKAWA† , Takuya KIDA† , and Hiroki ARIMURA†† Graduate School of Information Science and Technology, Hokkaido University
Kita 14, Nishi9, Kita–ku, Sapporo, Hokkaido, 060–0814 Japan
E-mail: †{sasakawa,kida,arim}@ist.hokudai.ac.jp
Abstract
Key words string matching, parallel processing, GPGPU, extended pattern, regular expression matching

1. は じ め に
1. 1 背景

ターンに対して，強い制約を持つため，物理シミュレーション
や，科学技術計算の分野への応用が中心であり，大規模な離散的計算への応用はまだ少ない．

数千個のパターンを照合する大規模並列文字列照合は，生物

これまでに著者らは，GPU を用いた大規模並列文字列照合

情報処理やネットワーク不正侵入検出など，広い応用分野におを研究してきた [9, 10]．文献 [9] では，ビット並列手法に基づいて重要な基盤技術である．特にゲノムやネットワークの分野

く Gaps-SHIFT-AND 法 [6] により CBG パターンと呼ばれる，では，ハードウェアの高性能化により，扱うデータ量が急速に文字クラスと有限長のギャップを許した正規表現の部分クラス

増大しており，データ解析の観点から照合の更なる高速化が求上のパターン照合アルゴリズムを与えた．ここでは，パターン

められている．一方で，大規模並列文字列照合は，処理全体の長に制限を設け，1 レジスタ内でのみ動作するアルゴリズムの計算負荷が非常に大きく，汎用 CPU 上のソフトウェアによるGPU 実装を考え，使用領域が大きい配列による実装に比べて実時間処理が難しい．そのため，GPU を用いたハードウェア

約 60 倍の高速化を実現した．

による高速化が注目を集めている．

文献 [10] では，拡張文字列パターンにおけるビット並列照GPU (Graphics Processing Unit) とは，画像処理を専門に合手法である拡張 SHIFT-AND 法 [5] を拡張し，複数レジス担当するハードウェアであり，数十から数百の演算コアと，各コ

タにまたがる長大なパターンに対して効率良く実行するためのア間で共有の高速なメモリを備えている．その高い並列演算能

NFA の階層的モジュール分解に基づく CPU 上のアルゴリズム

力を画像処理以外の汎用的な計算へ用いる GPGPU (General

RunNFA を与えた．分解した各モジュールの計算順序を工夫

Purpose computing on GPUs) という手法が近年注目されてし，レジスタ間の通信回数を減らし，複数のレジスタを並べている [1, 3, 7]．しかし，GPU はメモリサイズや，アクセスパ

長いレジスタを模倣する従来型のアルゴリズムと比較して，使用レジスタ数が 10 のパターンの時で 20%高速に動作する事を
確認した．

Σ

0

A

1

B

2

本稿では，RunNFA [10] を GPU 実装への拡張し，長大かB

つ大量の拡張文字列パターンに対する高速な照合を行う方法
を提案する．RunNFA はパターンを上位モジュールと，下位

図1

A
ε

3

B
ε

C

4

5

C

6

ε

B
ε

7

C
ε

8

A

9

ε

例 1 のパターン P1 に対応する非決定性有限オートマトン (NFA)

モジュールの 2 階層で構成される階層型 NFA に変換し，各モジュールの遷移をビット並列手法を用いて模倣する方法である．

拡張文字列照合問題とは，与えられたパターンとテキストに

階層型 NFA は，各モジュールが独立して動作できることが特対し，パターンが出現するテキスト中の位置を列挙する問題で徴であり，並列実行に向いている．また，ビット並列手法によある．正確には，次のように定義する．

るコンパクトな NFA 表現により，GPU のメモリ制約下でも高［定義 3］ 拡張文字列照合問題: テキスト T と拡張文字列パ

速な遷移計算を実現した．

ターン P を入力として受け取り，P の T 中の出現位置を全て計算機実験では，100 個のパターンについてアミノ酸データ

求める．

上で照合を行い，提案システムは，同アルゴリズムの CPU 実

2. 2 拡張 SHIFT-AND 法装に対して，2 倍程度高速であった．

ビット並列手法とは，ビット演算と，数値演算レジスタ内並列

1. 2 関 連 研 究性を利用し，計算を高速化する手法である．拡張 SHIFT-AND

大規模文字列照合に関する関連研究について説明する．Lin,

法は，Navarro ら [5, 6] による，ビット並列手法を用いた拡張

Tsai ら [2] は，Aho-Corasick 法と呼ばれる，決定性有限オー

文字列パターンに対する照合アルゴリズムである．このアルゴ

トマトンを用いた照合アルゴリズムの GPU 上の実装を与えてリズムでは，前処理時に，与えられた拡張文字列パターンに対いる．Wu, Diao, Rizvi ら [8] は，高速ストリームデータ上に応する非決定性有限オートマトン (NFA) を構築し，照合時に，おける複合イベント処理システムのための系列イベントクエ

この NFA の遷移をビット演算と，整数の加算を用いて模倣しリに対する照合アルゴリズムを与えている．これに関連して，照合を行う．例えば，例 1 のパターンに対しては，図 1 のようMargara, Cugola ら [4] は，GPU 上の複合イベント処理シス

な NFA が構築される．ここで，テキスト長を n，NFA の状態

テムを与えている．

数を ℓ とする．拡張 SHIFT-AND 法は，前処理に O(m + |Σ|)

2. 準

時間，照合に O(n⌈ℓ/w⌉) 時間それぞれかかり，アルゴリズム

備

全体で (2Σ + 4)⌈ℓ/w⌉ の領域を使用する．

2. 1 拡張文字列照合問題

2. 3 計算モデル

文字集合 Σ をアルファベットとする．テキストは，長さ n の文字列 T = t1 · · · tn ∈ Σ∗ である．
［定義 1］ 拡 張 文 字 列 パ タ ー ン:

計算モデルとして，レジスタ長 w の RAM モデルを用いる．
ここで，レジスタ内の AND 演算 “&”，OR 演算 “|”，NOT 演

Σ 上の正規表現 P =算 “∼”，XOR 演算 “∧”，左シフト演算 “<<”，右シフト演算

a1 . . . am (m >= 0) が拡張文字列パターンであるとは，任“>>”，整数の加減算を O(1) 時間で実行できると仮定する．

意の i = 1, . . . , m に対して, ai が下記の定義の (1)-(6) のいず

ビットマスク (マスク) は，幅 w のビット列である．また，各れかであることをいう. なおここで，≡ は構文糖衣を表し，·

0<=j<= w − 1 に対して，Bit(j) は，j 番目のビットのみに 1∗と， , | は言語の連結と，繰り返し，選言をそれぞれ表す．
（ 1 ） 定数文字 : a ∈ Σ. L(a) = a.

が立ったビットマスクを表す．

2. 4 GPU と GPGPU（ 2 ） ワイルドカード : “.”. L(.) = Σ.

Graphics Proccesing Unit (GPU) とは，画像処理専（ 3 ） 文字種 : β = [abc · · · ] ⊂=Σ. L(β) = β.

用のハードウェアである．GPU は，複数の Stream Multi-（ 4 ） オプション文字 : β? ≡ (β|ε). L(β?) = L(β) ∪ {ε}.

processor (SM) を備え，各 SM は 32 個の SIMD 演算コア

（ 5 ） 限定繰り返し : β{x, y} ≡ (β?)

y−x

x

β .

を持つ．各演算コアは，SM 内に搭載された 64KB の高速な共（ 6 ） 0 個以上の非限定繰り返し : β ∗ . L(β ∗ ) = L(β)∗ .

有メモリと，GPU ボード上に搭載された，低速であるが，大（ 7 ） 1 個以上の非限定繰り返し : β + ≡ ββ ∗ .

容量（数 GB）のグローバルメモリにアクセスし，並列に計算

ここで, 拡張文字列パターン P = a1 , · · · , am のサイズを Pを行うことで，高速な画像処理を実現する．このような多数のの中の文字と演算子の個数の総和とし，その言語を, L(P ) =演算コアと，高速なメモリを利用した高い演算能力を，画像

L(a1 ) · · · L(am ) と定義する.

処理以外の汎用的な計算に用いる手法を GPGPU (General［定義 2］ パターンの出現: パターン P が T の部分系列とPurpose computing on GPUs) と呼び，近年注目を集め

して位置 1 <= q <= n に出現するとは，長さ 0 以上の文字列ている [1, 3, 7]．

∗u, v, w ∈ Σ が存在して, (i) T = uvw かつ (ii) v ∈ L(P ), (iii)q = |uv| + 1 となることをいう. すなわち, q は, パターン P の後端の出現位置である.

3. GPU 照合システム
本節では，アルゴリズム RunNFA を GPU 実装へ拡張する［例 1］ ア ル ファベット Σ = {A, B, C} に 対 し て ，P1 =GPU 上の照合システムについて説明する．以下では，GPU 上

AB + A?B?C?CB?C?A? は拡張文字列パターンの例である．

で並列に実行される計算をスレッドと呼ぶ．

[Step4]

3. 1 システムのアーキテクチャ
提案システムは，大きく分けて CPU 側の計算（ホスト）とΣ

GPU 側の計算（デバイス）からなる．システムは任意のパター

10ン集合 P at = {P1 , P2 , . . . , Pk } に対して以下の様に動作する．

ε11[Step1][Step1]（ 1 ） P at の各パターンに対し，対応するビットマスク集合

0

1

3

2

3

ε

（ 2 ） 計算したビットマスク集合をデバイス側へ転送する

54ε[Step2]（ホスト，デバイス間通信）．

[Step1][Step3][Step3]を計算する（ホスト側）．

13

12

6

[Step3]

7

6

ε

ε

[Step2]（ 3 ） ビットマスク集合を用いて各パターンの照合を並列に

8
ε

9
ε

[Step2]図 2 階層型 NFA の動き．

実行する（デバイス側）．
（ 4 ） 照合結果をホスト側へ報告する（ホスト，デバイス間通信）．

Algorithm 1 RunNFA(U M, (LMj )k−1
j=0 : module, T : text)

3. 2 RunNFA アルゴリズム

1: procedure Search

パターン集合 P at における各々のパターンの照合について説2:n ← length(T );3:

U M.I ← 0w−1 1;

4:

EpsClo(U M );5:for i = 0 to n do

明する．基本的な照合アルゴリズムは，著者らが提案したビット並列手法に基づく RunNFA アルゴリズムを用いる．RunNFA
では，まず，前処理として，入力パターン P を階層型 NFA

6:

for j = 0 to k − 1 do UpperToLower(U M, LMj );と呼ぶ，NFA の集合に変換する．階層型 NFA は 1 つの上位

7:

par j = 0 to k − 1 do RunExShiftAnd(LMj , T [i]);モジュール （upper module）U M と，k 個の下位モジュール

8:

for j = 0 to k − 1 do LowerToUpper(LMj , U M );（lower module）LM で構成される．i 番目のモジュールを Mi

9:Syncthreads();と書く．また，モジュール M が持つ変数 X を表す時は，M.X

10:

EpsClo(U M )と書く．例として，図 1 の NFA を，w = 4 のとき，階層型

11:

if U M.S & Bit(w) ̸= 0 then12:

report an occurrence at i;

NFA に変換したものを図 2 に示す．次に，変換された階層型
NFA に対応するビットマスク集合を計算する．各モジュールが

図3

階層型 NFA による照合アルゴリズム．

保持するビットマスク集合は以下の通りである．

•

S : 状態集合を表すビットマスク．

•

Ebeg : ε 遷移の開始位置を示すビットマスク．

•

Eend : ε 遷移の終了位置を示すビットマスク．

•

Eblk : ε 遷移が 1 回以上連続する位置を示すビットマ

スク．

•

Algorithm 2 EpsClo(M : module)
1: M.S ← M.S | M.I
2: Z ← M.S | M.Eend
3: M.S ← M.S | (M.Eblk & ((∼ (Z − M.Ebeg)) ∧ Z))

Ch[c] : 文字 c ∈ Σ によって文字遷移が行われる位置を

図 4 手続き EpsClo．

示す．

•

Rep[c] : 文字 c ∈ Σ によって文字繰り返し行われる位置を示す．
各種ビットマスクの計算方法の詳細については [10] を参照されたい．ビットマスク集合の計算後，RunNFA は図 3 の実行時
アルゴリズムを用いて照合を行う．図 2 の実行時アルゴリズム
では，まず，1〜4 行目までで階層型 NFA の初期化を行う．次Algorithm 3 RunExShiftAnd(LMj : module, T [i]: letter)
1: LM.S ← LM.S | LM.I;
2: EpsClo(LM );3: LM.S← (((LM.S<< 1) | LM.I) & LM.Ch[T [i]]) |(LM.S & LM.Rep[T [i]]);4: EpsClo(LM );に，テキストを 1 文字ずつ読み込みながら，以下の手順を繰り返し，階層型 NFA の遷移を模倣する．

図5

手続き RunExShiftAnd．

Step1 UM から LM へ遷移情報を伝える (6 行目)．
Step2 LM の遷移を行う (7 行目)．
Step3 LM から UM へ遷移情報を伝える (8 行目)．

Algorithm 4 UpperToLower(U M, LM : modules)
1: if U M.S & Bit(j) ̸= 0

Step4 UM の遷移を行う (10 行目)．

2: then LM.I ← 1;

Step5 UM が終了状態に達したかどうかをチェックし，達して

3: else LM.I ← 0;

いれば報告する (11 行目)．

3. 3 GPU 実装
GPU 上での実装の詳細について説明する．GPU 上では，階層型 NFA の各モジュールに対して，1 ずつスレッドを割り振
り，遷移の計算を並列に行う．

図 6 手続き UpperTolower．

手続き UpperToLower（図 6）は，上位モジュールのビット状態を，下位モジュールの開始状態に対してコピーする手続き

4. 1 記 憶 領 域
Algorithm 5 LowerToUpper(LM, U M : module)
1: if LM.S & Bit(w) ̸= 0

上位モジュール数は 1 であり，下位モジュール数は k = ⌈ℓ/w⌉
個である．上位モジュール一つ当たり，NFA の状態集合を表す

2: then U M.S ← U M.S | Bit(j);▷ j ビット目を 1 にするビットを 1 個と，ε 遷移のためのビットマスクを 3 個用いるので，

3: else U M.S ← U M.S & (∼ Bit(j));▷ j ビット目を 0 にする

合計で Su = 4 (語) の領域を使用する．下位モジュール一つ当た

図 7 手続き LowerToUpper．

り，NFA の状態集合を表すビットを 1 個と，ε 遷移のためのマス
クビットを 3 個，文字遷移と文字繰り返しのためのマスクビットである．1 行目の if 文により，コピー先の下位モジュールに該当する状態のビットを確認し，その状態に応じて，1 または，

0 のビットを下位モジュールの開始状態にコピーする．手続き

をそれぞれ Σ 個用いるので，合計で Sl = (2|Σ| + 4)⌈ℓ/w⌉ (語)の領域を使用する．以上から，RunNFA は合計で，Sall = (2|Σ| + 4)⌈ℓ/w⌉ + 4

LowerToUpper（図 7）は，下位モジュールの終了状態を，上= O(|Σ|⌈ℓ/w⌉) (語)位モジュールの該当位置にコピーする手続きである．手続きの内容は，UpperToLower とほぼ同様である．

の領域を使用する (表 1)．

UpperToLower と LowerToUpper では，上位モジュールのマルチストリームマッチングは，s 個の入力ストリームに対状態マスク S を保持する 1 つのレジスタに対して，全ての下して，一つのパターンの照合を同時に行う．この場合，前処理

位モジュールのスレッドが同時にアクセスするため，モジューで構築するマスクを一組だけ保持して共有し，状態マスクのみ

ル同士のアクセス競合が起こる．提案手法では，特に競合のを s 個保持することで単純に s 台のパターン照合アルゴリズム

解決は行わず，書き込み時にロックを行いながら変更を行う

を走らせることができる．このとき，領域はAtomic 命令を使用し，照合の正しさを保証している．この対処方法では，下位モジュール数 k に対して，O(k) 回のアクセ

Sall = s(⌈ℓ/w⌉ + 1) + (2|Σ| + 3)⌈ℓ/w⌉ + 3= O((s + |Σ|)⌈ℓ/w⌉) (語)スが必要になる．提案システムでは採用していないが，平衡二分木スキームを利用することで，このアクセス回数を O(log k)となり，入力ストリーム数 s が非常に大きいときにメモリ削減

回のアクセスまで減らすことができる．また，上位モジューに有効である．

ルへの書き込みを伴う LowerToUpper においては，全てのモジュールの書き込みが終了した上で次の操作を行う必要がある

表1

ため，手続き LowerToUpper のあとで全スレッドの同期手続

Module ε 遷移 文字遷移 状態 Module 数

き Syncthreads() を行う（10 行目）．

Upper

3

0

1

1

4

Lower

3

2Σ

1

⌈ℓ/w⌉

(4 + 2Σ)⌈ℓ/w⌉

手続き RunExShiftAnd（図 5）は，下位モジュールの NFA の

記憶領域の解析．
合計

遷移を計算する手続きである．これは，Navarro と Raﬃnot [5]によって提案された Extended-SHIFT-AND 法そのものであ

4. 2 計 算 時 間

る．ビット演算と，整数の加算を用いて，NFA の文字遷移と文NFA サイズが ℓ のパターンの前処理時間は，O(ℓ) 時間であ字繰り返し（3 行目）と，ε 閉包の計算（2,4 行目）を各モジュー

る．図 3 の手続き RunNFA は，テキスト T の文字を 1 文字読ルについて，1 文字あたり O(1) で計算する．RunExShiftAnd

むごとに，for ループ内 (5〜12 行目) の手続きを行う．6〜8 行

では，モジュールごとに動作が独立しているため，並列に計算

目の UpperToLower (図 6)，RunExShidtAnd (図 5)，Lower-を実行することができる．また，手続き UpperToLower によToUpper (図 7) の 3 つの手続きは，すべての下位モジュール

り，上位モジュールの状態をコピーした際，初期状態に 0 がコ

LMj (0 <=j<= k − 1) について行われ，それぞれに対して O(1)ピーされた場合については，遷移計算を行う必要がないため，時間かかるので，合計で O(k) = O(⌈ℓ/w⌉) 時間かかる．また，

この場合，スレッドを休ませることで高速化をはかることがで

10 行目の上位モジュールにおける EpsClo は，U M0 についてきる．

実行され，O(1) 時間かかる．以上から，for ループ内の処理

なお，上位モジュールと，下位モジュールは同時に遷移計算には，を行うことはないので，先頭の下位モジュール LM0 の遷移計算を担当するスレッドが，上位モジュールの遷移計算も兼任することで，パターン 1 つあたりのスレッドを 1 つ減らすことができる．よって，1 つのパターンの照合に必要なスレッド数は下位モジュール数分の k 個である．

4. 計算量の解析
本節では，RunNFA アルゴリズムについて，記憶領域と計算時間について詳しく解析する．

O(⌈ℓ/w⌉) + O(1) = O(⌈ℓ/w⌉) (時間)

(1)

かかる．
以上から，逐次計算量について，次の定理を示すことが出来る．
［定理 1］ 提案アルゴリズム RunNFA は，ℓ <= w(w − 1) を満たす拡張文字列パターン P と入力テキスト T に対して，前処理
時間 O(ℓ) と領域 O(|Σ|⌈ℓ/w⌉) 語を使い，計算時間 O(n⌈ℓ/w⌉)
で P の T 中のすべての出現を見つける．ここに，n はテキス
ト長であり，ℓ はパターンに対応する NFA の総状態数である．

GPU などの並列ハードウェアの理論的モデルである並列
RAM (PRAM) 上の並列計算量について，次の結果を示すこと
140

が出来る．
［定理 2］ 提案アルゴリズム RunNFA は，ℓ <= w(w − 1) を満

Optimize

GPU
CPU

120

台のプロセッサを用いて，並列計算時間 O(n log⌈ℓ/w⌉) で P のT 中のすべての出現を見つける．ここに，n はテキスト長であり，ℓ はパターンに対応する NFA の総状態数である．

NFA サイズ ℓ が非常に大きなパターンに対して，多くのプロセッサを用いることで高速化できる．

5. 実

験

本論文で提案したシステムの有用性を検証するため計算機実験を行った．実験では，提案システムである RunNFA アルゴリ

実行時間（秒）

たす拡張文字列パターン P と入力テキスト T に対して，前処理
時間 O(ℓ) と，一台当たり O(|Σ|) 語の領域使用する O(⌈ℓ/w⌉)

100
80
60
40
20
0
1

3

5
7
9
11
使用レジスタ数（語）ズムの CUDA による GPU 実装と，比較対象として，同アルゴ
リズムの C++言語で実装した CPU 実装と，パターンの NFA

図8

13

15

パターンのワード数と実行時間．

を配列で表現し，その遷移を模倣する ArrayNFA アルゴリズ
ムの CUDA による GPU 実装を用いた．なお，ArrayNFA は，
文字遷移，ε 遷移，NFA の新旧の状態集合を長さ ℓ の 4 本の配列を用いて表現し，遷移の計算は，状態集合をスキャンしながら，一文字あたり O(ℓ) 時間で計算するアルゴリズムである．

5. 1 実験環境とデータ
実験は，以下の計算機上で行った．

•

CPU : Intel Core i7 processor 2.8GHz•

メモリ : 12GB•

GPU : NVIDIA GeForce GTX480– 演算コア数 : 480 個– メモリ : 1.5GB•

OS : Debian GNU/Linux 6.0.5•

CPU コンパイラ : g++ 4.6.3•

CUDA コンパイラ : nvcc 5.0

以下では，パターンに含まれる {∗, +, ?} の文字を特殊文字と呼ぶことにする．また，ℓ をパターンの NFA サイズとする．
実験で使用したデータは，ExPASy : SIB Bioinformatics

Resource Portal （注 1） から取得した 10MB のアミノ酸配列データである．アミノ酸配列データは，|Σ| = 20 のテキストデータ
である．パターンは，ランダムに生成した特殊文字を 60% 含
んだ拡張文字列パターンを使用した．

5. 2 GPU 上のアルゴリズムの比較
GPU 上のアルゴリズム，RunNFA と，ArrayNFA に対して，ℓ = 130 のパターンを用意し，パターン数を 20 個〜100 個まで 20 個ずつ変化させながら照合時間を計測した．表 2 に実
験結果を示す．ここで，t は SM あたりの同時に起動可能なス
レッド数を表す．全てのパターン数において，RunNFA の実
行時間は，ArrayNFA に対して 20 倍前後高速である．これは，ArrayNFA の使用領域が非常に大きく，GPU の共有メモリを圧迫し，同時に起動可能なスレッド数が 4 つに制限されるのに対し，RunNFA は NFA をレジスタに圧縮してコンパクトに表現するため，14 スレッドを並列実行可能であることが原因と考えられる．また，ArrayNFA は，状態遷移の計算に一文字あた
り O(ℓ) 時間かかり，RunNFA は，各モジュールに対して定数時間であることも高速化の一因であると考えられる．
表 2 アルゴリズムに対する総計算時間（秒）．

Algorithmt

Number of Patterns p
20

40

60

80

100

ArrayNFA

4

568.2 569.1 570.1 571.6 628.5

RunNFA

14

20.9

23.8

29.3

32.8

32.6

5. 3 パターンの使用するワード数による比較実験
RunNFA の GPU 実装と CPU 実装に対して，100 個のパターンの照合時間を，パターンの使用するワード数 ⌈ℓ/w⌉ を変化させながら計測し，比較した．図 8 に実験結果を示す．ワー
ド数が 1 個の場合は，CPU 実装が GPU 実装に比べ実行時間が短いが，ワード数が 2 個以上になると GPU 実装が上回っている．CPU 実装は，ワード数に対して線形に実行時間が伸びているのに対して，GPU 実装の実行時間は，伸びが緩やかである．使用レジスタ数が 12 の時，GPU 実装が CPU 実装に対して 2 倍高速である．これは，GPU の並列性により，パターン数の増加に対してスケールしているためであると考えられる．

5. 4 パターン数に関する実験
RunNFA の GPU 実装に対して，使用ワード数が 4 ワードとなるパターンを用意し，パターン数を 10 個〜200 個まで 10 個ずつ変化させながら照合時間を計測した．図 9 に実験結果を示
す．パターン数 120 個と 130 個の間で照合時間に大きな差が出ているのがわかる．これは，パターン一つ当たりの使用ワード数が 4 ワードのパターンに対して，今回実験に使用した GPU（注 1）：ExPASy : SIB Bioinformatics Resource Portal- http://expasy.

org/が持つコア数が 480 個であるため，120 パターンを照合する時，

7

6

実行時間

5

4

3

2

1

0
20

40

60

80 100 120 140 160 180 200
パターン数（個）図 9 パターン数と実行時間の変化．

全ての演算コアが使い切られ，130 パターン以降では，スレッドが逐次的に動作する事になるためこのような結果になったと考えられる．

6. お わ り に
本稿では，大規模文字列照合の GPU を用いた高速化を実現する方法について考察を行った．提案システムでは，NFA の階層型モジュール分解に基づくビット並列照合アルゴリズム

RunNFA を GPU 上の実装へ拡張する手法を与え，計算機実験において，同アルゴリズムの CPU 実装に比して，パターン数

100 のとき，約 2 倍高速に照合できることを確認した．階層型
NFA の各下位モジュールにおいて，照合の計算が並列に実行できることに加え，ビット並列手法を用いたことによる NFA のコンパクトな表現により，NFA を配列実装した場合にくらべ，

SM あたり 3.5 倍のスレッドが並列実行できることにより，高速な照合を実現した．今後の課題としては，本稿では，3. 3 節で検討した，上位モジュールでの競合に対して，平衡二分木を使う方法など手法の改良により競合回数を減らすことによる，パフォーマンスの改善があげられる．また，階層型 NFA を多階層の構成へ一般化し，より複雑な正規表現の照合を実現することを考えている．

文

献[1] N. Bell and M. Garland. Implementing sparse matrix-vector
multiplication on throughput-oriented processors. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, p. 18. ACM, 2009.

[2] Cheng-Hung Lin, Sheng-Yu Tsai, Chen-Hsiung Liu, ShihChieh Chang, and Jyuo-Min Shyu. Accelerating string
matching using multi-threaded algorithm on GPU. In
the 2010 IEEE Global Telecommunications Conference(GLOBECOM’10), pp. 1 –5, dec. 2010.
[3] S.A. Manavski and G. Valle. Cuda compatible gpu cards aseﬃcient hardware accelerators for smith-waterman sequencealignment. BMC bioinformatics, Vol. 9, No. Suppl 2, p. S10,
2008.
[4] A. Margara and G. Cugola. High performance contentbased matching using gpus. In Proceedings of the 5th ACM
international conference on Distributed event-based system,
pp. 183–194. ACM, 2011.
[5] Gonzalo Navarro and Mathieu Raﬃnot. Fast and simple
character classes and bounded gaps pattern matching, withapplication to protein searching. In Proceedings of the fifth
annual international conference on Computational biology,
RECOMB ’01, pp. 231–240, New York, NY, USA, 2001.
ACM.
[6] Gonzalo Navarro and Mathieu Raﬃnot. Flexible Pattern
Matching in Strings: Practical on-line search algorithms
for texts and biological sequences. Cambridge University
Press, 2002. ISBN 0-521-81307-7. 280 pages.
[7] P.D. Vouzis and N.V. Sahinidis. GPU-BLAST: using graphics processors to accelerate protein sequence alignment.
Bioinformatics, Vol. 27, No. 2, pp. 182–188, 2011.
[8] Eugene Wu, Yanlei Diao, and Shariq Rizvi.
Highperformance complex event processing over streams. In
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’06), pp. 407–418.
ACM, 2006.
[9] 笹川裕人, 金田悠作, 有村博紀. 大規模並列文字列照合の gpuによる高速化. 第 10 回情報科学技術フォーラム, pp. D–009,
2011.
[10] 笹川裕人, 金田悠作, 有村博紀. 長大な拡張文字列パターンに対する大規模文字列照合の高速化. 第 4 回データ工学と情報マネジメントに関するフォーラム, pp. D7–1, 2012.