著者

河南 克也 藤本 典幸

雑誌

先進的計算基盤システムシンポジウム論文集

巻号頁・発行日

vol.2011, pp.365-372, 2011-05-18

---

2 つの文字列の最長共通部分列を求める LCS 計算は遺伝子の比較などの様々な応用を持つ.本論文では Crochemore らのビット並列アルゴリズムを用いて改善した Hirschberg の CPU 用 LCS アルゴリズムを,GPU を用いて高速化する方法を提案する.Crochemore らのアルゴリズムは 1 ビット毎に同時並列実行が可能なビット毎の論理演算の他に,逐次性が強い算術加算など,GPU での実装に工夫が必要な演算も含んでいる.本論文では特にそれらの演算の効率的な実装方法について論じる.その方法に基いて設計したプログラムを,2.93GHz Intel Core i3 530 CPU とGeForce 8800 GTX,GTX 285,GTX 480 GPU を用いて評価した結果,CPU 上でのビット並列アルゴリズムに対しては最大 12.77 倍,Hirschberg の CPU 用 LCS アルゴリズムに対しては最大 76.5 倍高速であった.また,Kloetzli らの GPU を用いた既存アルゴリズムに対しては 10.9 倍から 18.1 倍高速であった.