拡張文字列パターンのクラスに対するGPU上の並列照合アルゴリズムとその性能評価

摘要

本稿では，正規表現の部分クラスである拡張文字列パターンのクラスに対して，NFA模倣に基づく効率よい並列パターン照合アルゴリズムを与え，その性能評価を行う．本手法では，とくに，高速化の鍵である空遷移演算のためゐ到達可能性演算に関して，ビット並列化（ワード内SIMD）のアイディアに基づく，GPUアーキテクチャ上での種々の並列化を検討し，実験結果を示す．