Smith-Watermanアルゴリズム向けビット並列手法の検討(並列処理,FPGA応用及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
Smith-Waterman(SW)アルゴリズムは,2つの文字列からよく一致する部分文字列を探索する計算手法であり,遺伝子やアミノ酸配列の配列類似性検索に広く応用されている.SW法の高速化に関する様々な取り組みが行われているなかでも,演算効率を向上させるアルゴリズムの開発は,アクセラレータでの実行で大きな効果が期待できる.SWアルゴリズムと同様に動的計画法で計算を行う編集距離や最長共通部分列(LCS)問題では,アルゴリズムをビットベクトル同士の演算で実現するビット並列化が提案されており,並列度の大きな向上が報告されている.本研究報告では,SWアルゴリズムのビット並列化について議論する.パラメータに制約のある簡略版のSW法を対象に,ブロック単位の入出力をビットベクトルで列挙し,入出力間の演算を進化的計算を用いて発見した.得られた論理式を元に速度評価を行い,ビット並列SWアルゴリズムの実現可能性について議論する.
- 一般社団法人電子情報通信学会の論文
- 2014-01-21
著者
-
入江 英嗣
電気通信大学大学院情報システム学研究科
-
吉永 努
電気通信大学
-
入江 英嗣
電気通信大学
-
吉見 真聡
電気通信大学大学院情報システム学研究科
-
須戸 里織
電気通信大学大学院情報システム学研究科
関連論文
- CellおよびGPGPUの性能比較評価(ARC-5:並列処理1,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 低遅延オンチップネットワークのための予測ルータの評価(組込みシステムプラットフォーム)
- 高信頼性マルチホーミング通信方式(ネットワーク,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- プログラム実行時のキャッシュ連想度の需要予測方式(ARC-1:アーキテクチャ1,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 6ZD-4 マルチリンクEthernet環境におけるSMPクラスタの性能評価(ネットワークと専用アーキテクチャ,学生セッション,アーキテクチャ)
- 動的故障に対応する並列計算機用適応ルータに関する検討(ディペンダブルコンピュータシステム及び一般)
- 予測機構を持った低遅延オンチップルータアーキテクチャ(オンチップ・ネットワーク/メモリシステム,集積回路とアーキテクチャの協創〜どう繋ぐ?どう使う?マルチコア〜)
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式 (集積回路)
- 分散共有メモリアクセスの優先度制御(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- トランザクショナルメモリのための性能評価手法(ARC-9:並列処理2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- メニーコア時代に向けたインオーダ・アーキテクチャ再考 (コンピュータシステム)
- 耐故障・適応デッドロック回復ルーチングのためのネットワーク再構成プロトコル(コンピュータシステム)
- コンパイラとランタイムによるソフトウェアキャッシュの更新オーバヘッド隠蔽手法
- 動的推定によるプリフェッチ量最適化
- 低遅延オンチップネットワークのための予測ルータの評価
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 省ハードウェア資源のフィードバックつきハイブリッドプリフェッチ方式
- 部分的試行に基づく動的共有キャッシュ分割方式
- GeForce GTX 280 vs. Cell
- 置換データの性質に着目した動的キャッシュパーティショニング
- 追い出しラインに着目したプリフェッチスロットリング手法
- フィードバックを用いたハイブリッド・プリフェッチ方式
- 低遅延オンチップネットワークのための予測ルータの評価(組込みシステムプラットフォーム)
- 低遅延オンチップネットワークのための予測ルータの評価(組込みシステムプラットフォーム)
- 予測機構を持つルータを用いた低遅延チップ内ネットワークに関する研究
- 予測ルータによる低遅延Fat Treeネットワーク
- キュー計算原理によるSMT型マルチスレッド並列キュープロセッサの提案と設計(アーキテクチャ)
- キュー計算原理によるSMT型マルチスレッド並列キュープロセッサの提案と設計
- C-026 携帯端末とネットワーク上計算資源の協調によるカメラセンサアプリ高速化の検討(C分野:ハードウェア・アーキテクチャ,一般論文)
- PCクラスタによる行動支援サービスプラットフォームZeoBroの初期実装と評価(ホームネットワーク,ユビキタスネットワーク,クラウドコンピューティング,コンテキストアウェア,位置情報サービス,eコマース及び一般)
- メニーコア時代に向けたインオーダ・アーキテクチャ再考(システムアーキテクチャ2,デザインガイア2010-VLSI設計の新しい大地-)
- 2ZP-5 未知のSQLインジェクション攻撃検知システムの構築(情報爆発時代における分散処理と運用技術,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 2-Dトーラスネットワークにおける動的通信予測による低遅延化
- 通信予測機構を用いた低遅延ネットワークの構成方法と評価(予測及び通信機構)
- ルールベースアクセス制御機能を持つDLNA情報家電の遠隔共有支援機構
- 2ZP-3 資源情報の特徴抽出によるモデル化手法と攻撃検知法の提案(情報爆発時代における分散処理と運用技術,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- B-022 GCCによるキュー・コンパイラ開発手法の提案(B分野:ソフトウェア)
- 耐故障・適応ルーティングのセルフチューニングに関する検討
- 耐故障・適応ルーティングのセルフチューニングに関する検討(ディペンダブルコンピュータシステム及び一般)
- 耐故障・適応ルーティングのセルフチューニングに関する検討(ディペンダブルコンピュータシステム及び一般)
- キャンパスP2Pネットワークにおけるパーソナライズド検索(ネットワーク, 組込技術とネットワークに関するワークショップ)
- キャンパスP2Pネットワークにおけるパーソナライズド検索
- 耐故障性を考慮したk-ary n-cube用適応デッドロック回復ルーティング(ネットワーク)
- C-029 Verilog-HDLによる並列キュープロセッサのデザイン(C.アーキテクチャ・ハードウェア)
- 並列キュー計算モデルの基本特性評価(CPSY-3 性能評価)(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- 動的故障に対応する並列計算機用適応ルータに関する検討(ディペンダブルコンピュータシステム及び一般)
- JXTAネットワークに対するユーザ認証およびアクセス制御の導入
- Qjavaプロセッサの基本設計(デペンダブルコンピュータシステム及び一般)
- QJavaプロセッサの基本設計(ディペンダブルコンピュータシステム及び一般)
- クラウドによる携行可能な指先での署名認証システムの開発 (アドホックネットワーク)
- 予測機構を持った低遅延オンチップルータアーキテクチャ(集積回路とアーキテクチャの協創 : どう繋ぐ?どう使う?マルチコア)
- Mobile-Wormhole Device : DLNA情報家電の相互遠隔接続支援機構の携帯端末への応用(UBI-1【ホームネットワーク/実世界インタフェース】)
- Mobile-Wormhole Device : DLNA情報家電の相互遠隔接続支援機構の携帯端末への応用(UBI-1【ホームネットワーク/実世界インタフェース】)
- 受信メッセージ予測法によるMPI受信処理の高速化
- D-6-4 キュー計算モデルを用いた並列プロセッサの設計
- 並列デッドロック回復ルータRecover-xのLSI試作
- 並列FPGAシステムによる医療用画像処理の高速化
- 仮想チャネル数と動作周波数を考慮した適応ルータの性能評価
- 2Dトーラスネットワークにおける動的予測ルーティング(ARC-6:相互結合網,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- 仮想リモートレプリケーションによる3拠点ストレージシステム制御方式
- 並列キュープロセッサの基本設計
- 並列キュープロセッサの基本設計
- DT-2 CPSY企画セッション : 先進的コンピュータ・システムとその応用技術(チュートリアルセッション,ソサイエティ企画)
- 視覚神経系モデルシミュレーションの複数GPUによる高速化
- 3次元積層向けブロック配置問題の検討
- 3次元積層向けブロック配置問題の検討
- 視覚神経系数理モデルシミュレーションのMPIによる並列化
- クラウドによる携行可能な指先での署名認証システムの開発
- クラウドによる携行可能な指先での署名認証システムの開発
- 2010年度論文賞の受賞論文紹介 : 低次キャッシュとプリフェッチ
- ネットワークコンピューティングのための包括的マッシュアップフレームワークの検討
- スマートフォンを用いた歩行動作改善ツールの開発
- 「覗き込み」を利用した直感的な外部ディスプレイアクセス方式の提案
- FPGAを用いたデータストリームに対するウィンドウジョインの検討(FPGAアクセラレーター,FPGA応用及び一般)
- FPGAを用いたデータストリームに対するウィンドウジョインの検討(FPGAアクセラレーター,FPGA応用及び一般)
- FPGAを用いたデータストリームに対するウィンドウジョインの検討(FPGAアクセラレーター,FPGA応用及び一般)
- キューマシン用並列化Cコンパイラ
- SMPクラスタにおけるハイブリッドMPI-OpenMPプログラミングのためのマスタースレーブアルゴリズム
- PCクラスタによる行動支援サービスプラットフォームZeoBroの初期実装と評価
- ウィンドウ結合演算子のFPGAによる実現(スマートな社会を支えるインターネットアーキテクチャ論文)
- D-6-5 QJavaコンパイラ : 並列性を重視したQJavaバイトコードの生成
- D-6-6 QJavaバイトコードの実行環境の構築
- MPI埋め込み可能GPUプログラミングフレームワーク適用可能性の評価(並列処理支援,2011年並列/分散/協調処理に関する『鹿児島』サマー・ワークショップ(SWoPP鹿児島2011))
- DT-2 CPSY企画セッション : 先進的コンピュータ・システムとその応用技術(チュートリアルセッション,ソサイエティ企画)
- 配線アクティビティを考慮した3次元積層プロセッサ向けフロアプランナ
- FLAT:MPIを埋め込み可能なGPUプログラミングフレームワーク
- C-015 関連データ先読みとスマートフォンの消費電力に関する研究(コンピュータシステム,C分野:ハードウェア・アーキテクチャ)
- 配線アクティビティを考慮した3次元積層プロセッサ向けフロアプランナーのための熱評価手法(モデリング・シミュレーション,集積回路とアーキテクチャの協創〜新しいアプリケーション創造に向けたアーキテクチャ、回路技術の貢献〜)
- UDU-L:レーザポインティングによる柔軟なデバイス接続手法(計算機システム,ヒューマンコミュニケーション〜価値ある生活環境構築のための情報技術〜論文)
- AirTarget:光学シースルー方式HMDとマーカレス画像認識による高可搬性実世界志向インタフェース
- HMD端末単体で動作する指先認識アルゴリズムの性能評価(メディア処理・コンシューマデバイス,ユーザを支えるコンピューティング及び一般-パーソナル機器からスマートシティまで-)
- Smith-Watermanアルゴリズム向けビット並列手法の検討(並列処理,FPGA応用及び一般)
- 光学シースルー方式HMDに適した直観的ジェスチャーUI(メディア処理・コンシューマデバイス,ユーザを支えるコンピューティング及び一般-パーソナル機器からスマートシティまで-)