WEKO3
-
RootNode
アイテム
GPUを使用したビット並列アルゴリズムに基く最長共通部分列の導出
https://ipsj.ixsq.nii.ac.jp/records/74410
https://ipsj.ixsq.nii.ac.jp/records/744107fce455b-0ab9-43f9-81ac-8fa195c36523
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-SACSIS2011072.pdf (810.6 kB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Symposium(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-05-18 | |||||||
| タイトル | ||||||||
| タイトル | GPUを使用したビット並列アルゴリズムに基く最長共通部分列の導出 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Computing the Longest Common Subsequence with Bit-Parallelism on a GPU | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | GPU | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 大阪府立大学大学院理学系研究科情報数理科学専攻 | ||||||||
| 著者所属 | ||||||||
| 大阪府立大学大学院理学系研究科情報数理科学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University | ||||||||
| 著者名 |
河南, 克也
藤本, 典幸
× 河南, 克也 藤本, 典幸
|
|||||||
| 著者名(英) |
Katsuya, Kawanami
Noriyuki, Fujimoto
× Katsuya, Kawanami Noriyuki, Fujimoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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 倍高速であった． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌情報 |
先進的計算基盤システムシンポジウム論文集 巻 2011, p. 365-372, 発行日 2011-05-18 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
