@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00074410,
 author = {河南, 克也 and 藤本, 典幸 and Katsuya, Kawanami and Noriyuki, Fujimoto},
 book = {先進的計算基盤システムシンポジウム論文集},
 month = {May},
 note = {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 倍高速であった．, The longest common subsequence (LCS for short) for given two strings has various applications, e.g. comparison of DNAs. In this paper, we propose a GPU algorithm to accelerate Hirschberg's CPU LCS algorithm improved using Crochemore et al's bit-parallel CPU algorithm. Crochemore's algorithm includes bitwise logical operators which can be computed in embarrassingly parallel. However, it also includes some operators with less parallelism, e.g. an arithmetic sum. In this paper, we focus on how to implement these operators efficiently in parallel. Our experiments with 2.93GHz Intel Core i3 530 CPU, GeForce 8800 GTX, GTX 285, and GTX 480 GPUs show that the proposed algorithm runs maximum 12.77 times faster than the bit-parallel CPU algorithm and maximum 76.5 times faster than Hirschberg's LCS CPU algorithm. Furthermore, the proposed algorithm runs 10.9 to 18.1 times faster than Kloetzli's existing GPU algorithm.},
 pages = {365--372},
 publisher = {情報処理学会},
 title = {GPUを使用したビット並列アルゴリズムに基く最長共通部分列の導出},
 volume = {2011},
 year = {2011}
}