| 講演名 | 2014-01-29 Smith-Watermanアルゴリズム向けビット並列手法の検討(並列処理,FPGA応用及び一般) 須戸 里織, 吉見 真聡, 入江 英嗣, 吉永 努, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Smith-Waterman(SW)アルゴリズムは,2つの文字列からよく一致する部分文字列を探索する計算手法であり,遺伝子やアミノ酸配列の配列類似性検索に広く応用されている.SW法の高速化に関する様々な取り組みが行われているなかでも,演算効率を向上させるアルゴリズムの開発は,アクセラレータでの実行で大きな効果が期待できる.SWアルゴリズムと同様に動的計画法で計算を行う編集距離や最長共通部分列(LCS)問題では,アルゴリズムをビットベクトル同士の演算で実現するビット並列化が提案されており,並列度の大きな向上が報告されている.本研究報告では,SWアルゴリズムのビット並列化について議論する.パラメータに制約のある簡略版のSW法を対象に,ブロック単位の入出力をビットベクトルで列挙し,入出力間の演算を進化的計算を用いて発見した.得られた論理式を元に速度評価を行い,ビット並列SWアルゴリズムの実現可能性について議論する. |
| 抄録(英) | The Smith-Waterman (SW) algorithm is a computational method to obtain well accorded subsequences between two strings, and is widely used in a similarity retrieval for genome and amino acid sequences. A lot of effort has been done to accelerate the algorithm, especially new solutions which efficiently utilize recent hardware accelerators are promising. Several dynamic programming based algorithms, such as edit distance and the longest common subsequence, are solved by fast bit-parallelized algorithms. This paper proposes a new bit-parallelization scheme for the SW algorithm. By utilizing a technique of evolutionary computation, calculation formulae from input bit-vectors to output bit-vectors are discovered for an abridged version of the SW algorithm which constrained parameters. We evaluate performance based on the obtained formulae and discuss feasibility of the proposed bit parallel SW algorithm. |
| キーワード(和) | Smith-Watermanアルゴリズム / ビット並列性 |
| キーワード(英) | Smith-Waterman algorithm / bit-parallelism |
| 資料番号 | VLD2013-119,CPSY2013-90,RECONF2013-73 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2014/1/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Smith-Watermanアルゴリズム向けビット並列手法の検討(並列処理,FPGA応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Smith-Watermanアルゴリズム / Smith-Waterman algorithm |
| キーワード(2)（和/英） | ビット並列性 / bit-parallelism |
| 第 1 著者 氏名（和/英） | 須戸 里織 / Saori SUDO |
| 第 1 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 吉見 真聡 / Masato YOSHIMI |
| 第 2 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 入江 英嗣 / Hidetsugu IRIE |
| 第 3 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, The University of Electro-Communications |
| 第 4 著者 氏名（和/英） | 吉永 努 / Tsutomu YOSHINAGA |
| 第 4 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, The University of Electro-Communications |
| 発表年月日 | 2014-01-29 |
| 資料番号 | VLD2013-119,CPSY2013-90,RECONF2013-73 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 416 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |