近年來隨著DNA定序技術的不斷提升以及生物學知識的整理，大量的生物序列資料被建構成資料庫，序列比對是生物資訊中最基本的運算之一，通常都是使用近似演算法而非需要相當大計算時間的精準演算法。Smith-Waterman方法是一個搜尋局部比對的精準演算法， GPU是適合於執行資料平行問題的高度平行架構，因此在多GPU平台發展平行程式以加速Smith-Waterman方法的計算是一個值得探討的主題。
本論文提出一個在多GPU平台的流水線式序列比對演算法以加速巨量序列的序列比對。DP矩陣的連續數列組成一個執行排，他是一個分配給執行區組去執行的基本單位，因此整個DP矩陣可看成一串執行排。現行執行區組將所屬執行排的最後列的狀態寫入一個流水線給下一個執行區組讀取。本機的管理程序只負責精簡管理執行核心的啟動與特殊列狀態的儲存，因此本論文的流水線式處理能盡量減少同步，大大提升系統效能。

In recent years, DNA sequencing techniques and the management of bioinformatics have been developed prosperously. Sequence alignment is usually solved by heuristic methods due to the excessive computation times of the exact methods. Smith-Waterman(SW) is an exact algorithm to search local alignment. GPUs are highly parallel architectures which are suitable for executing data parallel problems. Thus it is worthwhile to develop parallel algorithms on multiple GPUs to accelerate SW computation.
The aim of this thesis is to propose a pipelined sequence alignment algorithm on multiple GPUs for speeding up the sequence alignment of huge sequences. Consecutive rows of the DP matrix are grouped as an execution-bank, which is assigned to a block for execution. Thus, the DP matrix can be regarded as a sequence of execution-banks. The current block writes the state of the last row of its own execution-bank into a pipeline for the reading of the next block. The manager process in the host is only in charge of streamlining kernel invocations and storing of the special rows. Thus this pipelined fashion of proposed algorithm can have as little synchronization as possible, resulting in speeding up the system performance significantly.

[1] American Museum of Natural History, "https://www.amnh.org/."
[2] Science-Based Medicine, "https://sciencebasedmedicine.org/."
[3] T. F. Smith and M. S. Waterman, "Identification of Common Molecular Subsequences," J. Molecular Biology, vol. 147, no. 1, pp. 195-197, Mar. 1981.
[4] R. Inam, "An Introduc tion to GPGPU Programming-CUDA Architecture," Malardalen Real-Time Research Centre Malardalen University, Vasteras, Sweden http://www.mrtc.mdh.se.
[5] J. P. J. Ghorpade, M. Kulkarni, and A. Bawaskar, "GPGPU PROCESSING IN CUDA ARCHITECTURE," Advanced Computing: An International Journal ( ACIJ), vol. 3, No.1, January 2012.
[6] NVIDIA, "https://www.geforce.com/hardware/desktop-gpus/geforce-gtx-980-ti/specifications."
[7] C. Angelini, "https://www.tomshardware.com/reviews/nvidia-geforce-gtx-980-ti,4164.html," 2015.
[8] ZPOOL, "https://www.zpool.ca/bench."
[9] S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," Journal of Molecular Biology, vol. 48, no. 3, pp. 443–453, March 1970.
[10] E. W. Myers and W. Miller, "Optimal Alignments in Linear Space," Computer Applications in the Biosciences, vol. 4, no. 1, pp. 11-17, 1988.
[11] Sandes, E. F. D. and A. de Melo, "CUDAlign: Using GPU to Accelerate the Comparison of Megabase Genomic Sequences," Acm Sigplan Notices 45(5): 137-146, 2010.
[12] E. F. d. O. Sandes and A. C. M. A. d. Melo, "Smith-Waterman Alignment of Huge Sequences with GPU in Linear Space.," In IPDPS, pages 1199–1211, 2011., 2011.
[13] E. F. d. O. Sandes and A. C. M. A. d. Melo, "Retrieving Smith-Waterman Alignments with Optimizations for Megabase Biological Sequences Using GPU," IEEE Transactions on Parallel and Distributed Systems 24(5): 1009-1021., 2013.
[14] G. M. E. F. O. Sandes, , A. C. M. A. Melo, X. Martorell, and E. Ayguadé., "Cudalign 3.0: Parallel biological sequence comparison in large gpu clusters," CCGrid, pages 160–169, 2014.
[15] G. M. Edans F. de O. Sandes, Xavier Martorell, and G. T. Eduard Ayguade, and Alba C. M. A. Melo, "Parallel Optimal Pairwise Biological Sequence Comparison: Algorithms, Platforms, and Classification.," Acm Computing Surveys 48(4). 2016.
[16] P.-C. Su, "A Sequence Alignment Strategy for Large-Scale Biological Sequences Using GPU," 2016.
[17] National Center for Biotechnology Information,
"https://www.ncbi.nlm.nih.gov/."
[18] Techpowerup, "https://www.techpowerup.com/gpudb/1537/tesla-m2090."