抄録
D-009
大規模並列文字列照合のGPUによる高速化
◎笹川裕人・金田悠作・有村博紀（北大）
数千個のパターンを照合する大規模並列文字列照合は，ネットワーク不正侵入検出や生物情報処理など，広い応用分野において重要な基盤技術である．膨大なデータに対して照合を行うために，本稿では，多数の演算コアを備えるGPU上での大規模文字列照合の実現法を考察する．特に，ビット並列パターン照合（BP）手法に基づく方式を提案し，正規表現の部分クラスである拡張文字列パターンに対して，BP手法の一種である拡張SHIFT-AND法を用いたシステムを実現する．さらに，共有メモリを用いた高速化法や，領域削減のためのパターンマスク圧縮手法を提案する．最後に計算機実験によって，提案手法の有効性を示す．