Smith-WatermanアルゴリズムのGPUによる並列化

2010年4月1日

2009-12-03 10:20 　Smith-WatermanアルゴリズムにおけるGPUを用いた実装方法の一提案（土肥慶亮（長崎大）・Ling Cheng（エディンバラ大）・濱田　剛・柴田裕一郎・小栗　清（長崎大）・Khaled Benkrid（エディンバラ大）

（ 信学技報, vol. 109, no. 31,  CPSY2009-43, pp. 1-6, 2009年12月 ）

Smith-WatermanはDPマッチング手法を使っているので、直前に計算した情報をすぐ次に使う構造になる。
だから素直に考えると（アルゴリズム内の）並列化は難しい気がしていた。もちろん、多数のデータに対して
計算するのは並列に出来て当たり前。　というところで、どうやって並列度を稼ぐのか？　どこかの論文では、
（右上から左下への）対角線上に並んだ要素は同時に計算できる話が出ていたが、確かにその通りだが、
これまた余分に必要になる対角インデックスの計算のオーバーヘッドが大きい割に、並列化される個々の要素の計算
は小さいので余りメリットが見えない気がする。１つ可能性として想像できるのは、マルチプルアラインメントで
次元数が大きい時、対角超平面上を並列計算する場合か？