Smith-Waterman アルゴリズムにおけるGPUを用いた実装方法の一提案 An Efficient GPU Implementation Approach of Smith-Waterman Algorithm

この論文をさがす

著者

抄録

本稿では,Smith-Waterman (SW)アルゴリズムをGPU上で並列計算させるための設計,実装を行う.実装では,二つのシーケンスのアライメントマトリックスを小領域に分割し,それらをwarp単位でスレッドに割り当て計算を行う.評価の結果,9.09GCUPS (Giga Cell Update per Second)から12.71GCUPSの性能を達成し,4つのGPUコアを用いた場合では,29.46GCUPSから43.05GCUPSの性能を達成した.現在発表されている最も高速なGPU上での実装と比較して,最大46%の高速化に成功した.

This paper describes a implementation of the Smith-Waterman (SW) algorithm on GPUs. Central to this is a divide and conquer approach which divides the computation of a whole pairwise sequence alignment matrix into multiple sub-matrices (or parallelograms) each running efficiently on the available hardware resources of the GPU. Moreover, we use thread warps and padding techniques in order to decrease the cost of thread synchronization. As a result, our implementation of the SW algorithm achieves a throughput ranging between 9.09 GCUPS (Giga Cell Update per Second) and 12.71 GCUPS on a single-GPU version, and a throughput between 29.46 GCUPS and 43.05 GCUPS on a quad-GPU platform. Compared with the best GPU implementation of the SW algorithm reported to date, our implementation achieves up to 46% improvement in speed.

収録刊行物

  • 電子情報通信学会技術研究報告. CPSY, コンピュータシステム

    電子情報通信学会技術研究報告. CPSY, コンピュータシステム 109(319), 1-6, 2009-11-26

    一般社団法人電子情報通信学会

参考文献:  20件中 1-20件 を表示

被引用文献:  1件中 1-1件 を表示

各種コード

  • NII論文ID(NAID)
    110008000644
  • NII書誌ID(NCID)
    AN10013141
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    10511278
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS 
ページトップへ