一般基因分析流程主要分為三個主要步驟。第一步是將DNA reads映射到參考基因組上，第二階段和最後階段是找到DNA中的突變。與最後兩個步驟相比，第一步驟的處理時間最長。BWA-MEM(Burrows-Wheeler Aligner Maximum Exact Match)演算法被使用在基因分析的第一步驟。在BWA-MEM中的Seed Extension階段為矩陣運算，適合利用硬體平行計算，因此本論文提出一個Seed Extension硬體加速器。
在本論文中，我們利用脈動矩陣(Systolic Array)來實現Seed Extension加速器。在脈動矩陣中使用PE(Processing Element)來達到平行運算。為了提高效能，提出了二項改善：其一、平行輸入read到PE陣列的部份上採用並列輸入，以減少設置時間；其二、在PE陣列採用VLL(Variable Logical Length)架構，利用多工器分流，讓參考序列更快流入正在工作的PE中。
設計完成的Seed Extension加速器已經分別在Xilinx的Vertex 5系列的FPGA (xc5vlx110t) 以及TSMC 0.18 µm元件庫(Cell Library)上實現與驗證。在FPGA設計部分，它一共消耗了17610個 LUT 與7954個暫存器，工作頻率為125 MHz，Seed Extension核心運算平均比軟體快6.5x，平均吞吐量為45.90 Mbp/s。在元件庫設計的部分上，工作頻率為100 MHz，Seed Extension核心運算時間平均比軟體快5.2x，平均吞吐量為36.70 Mbp/s。晶片面積為1.761 mm × 1.760 mm，核心面積為1.284 mm × 1.272 mm，其等校閘數量約為169,660個，功率消耗為68.03 mW。

The general genetic analysis process is divided into three main steps. The first step is mapping DNA reads onto a reference genome. The second and the final stages are to find mutations in DNA. Compared to the last two steps, the first step is time-consuming. The BWA-MEM algorithm was used in the first step of genetic analysis process. The Seed Extension stage in BWA-MEM algorithm is matrix calculation, which is suitable for hardware parallel calculation. Therefore, this thesis proposes an Seed Extension hardware accelerator.
In this thesis, we implement a Seed Extension accelerator using a systolic array. Parallel calculations are achieved using PEs in the systolic array. In order to improve performance, the following two improvements are made: First, we use a parallel input for sending read to the systolic array. Second, we adopt a VLL architecture in the PE array, make the reference sequence into the working PE faster using the multiplexer.
The Seed Extension Accelerator has been implemented and verified with an FPGA device(xc5vlx110t) of the Xilinx Vertex 5 family and a TSMC 0.18 μm cell library. In the FPGA part, it needs 17610 LUTs and 7954 registers, operates at 125 MHz, the Seed Extension operation core is 6.5x faster than the software and the average throughput is 45.90 Mbp/s. In the cell-based part, it operates at 100 MHz, the Seed Extension core operation time is 5.2x faster than the software, and the average throughput is 36.70 Mbp/s. The chip area is 1.761 mm × 1.760 mm and the core area is 1.284 mm × 1.272 mm, which is approximately equivalent to 169,660 gates, and consumes about 68.03 mW in the typical operating condition.

[1] National Human Genome Research Institute, “DNA Sequencing Costs,” URL:https://www.genome.gov/about-genomics/fact-sheets/DNA-Sequencing-Costs-Data
[2] H. Li. Burrows-Wheeler Aligner, URL:http://bio-bwa.sourceforge.net/.
[3] BWA Manual Reference Pages, URL:http://bio-bwa.sourceforge.net/bwa.shtml.
[4] T. Smith and M. Waterman. “Identification of common molecular subsequences, ” Journal of molecular biology, vol. 147, no. 1, pp. 195-197, 1981.
[5] H. Li, “ Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM,” Cornell University library arXiv:1303.3997, 2013, pp. 1-3.
[6] E. Houtgast, V. Sima, K. Bertels, and Z. Al-Ars, “An FPGA- Based Systolic Array to Accelerate the BWA-MEM Genomic Mapping Algorithm,” in Intl. Conf. on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), Samos, 2015, pp. 221-227.
[7] E. Houtgast, V. Sima, G. Marchiori, K. Bertels, Z. Al-Ars, “Power-efficient accelerated genomic short read mapping on heterogeneous computing platforms,” Proc. 24th IEEE International Symposium on Field-Programmable Custom Computing Machines, 2016, pp. 28-28.
[8] P. Zhang, G. Tan, G. Gao, “Implementation of the Smith-Waterman algorithm on a reconfigurable supercomputing platform, ” Proceedings of the 1st international workshop on High-performance reconfigurable computing technology and applications: held in conjunction with SC07, 2007, pp. 39-48.
[9] P. Cuong, B. Kieu, N. Tran., “An FPGA Based Seed Extension IP Core for BWA-MEM DNA Alignment,” 2018 International Conference on Advanced Computing and Applications (ACOMP), 2018, pp. 1-6.
[10] E. Houtgast, V. Sima, K. Bertels, Z. Al-Ars,“Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths, ” Computational Biology and Chemistry, vol. 75, 2018, pp. 54-64.
[11] Y. Chen, J. Cong, J. Lei and P. Wei, "A Novel High-Throughput Acceleration Engine for Read Alignment," 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines, Vancouver, BC, 2015, pp. 199-202.
[12] N. Ahmed, V. Sima, E. Houtgast, K. Bertels and Z. Al-Ars, "Heterogeneous hardware/software acceleration of the BWA-MEM DNA alignment algorithm," 2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Austin, TX, 2015, pp. 240-246.
[13] N. Ahmed, K. Bertels and Z. Al-Ars, "A comparison of seed-and-extend techniques in modern DNA read alignment algorithms," 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Shenzhen, 2016, pp. 1421-1428.
[14] A. McKenna, M. Hanna, E. Banks, A. Sivachenko, K. Cibulskis, A. Kernytsky, K. Garimella, D. Altshuler, S. Gabriel, M. Daly, and M. A. DePristo, “The genome analysis toolkit: A mapreduce framework for analyzing next-generation dna sequencing data,” Genome Research, vol. 20, no. 9, pp. 1297–1303.