Parallel Design And Optimization Of Sequence Alignment Algorithm Based On APU

Pairwise alignment is a foundation of bioinformatics.Smith-Waterman algorithm is widely used for pairwise alignment.It adopts dynamic programming to calculate the most similar region between two sequences.Due to the explosive increase of DNA/RNA sequences,it becomes crucial to speedup and optimize the pairwise alignment algorithm.Researchers have done a lot of works on pairwise alignment optimization on top of high performance platforms,such as GPU and Xeon Phi.However,existing works cannot well utilize the system resources due to the ignorance of CPU computing ability and high PCI-E transfer cost of CPU and GPU.In this situation,APU is a good choice.The CPU and GPU are integrated in the same die and the data transfer through shared memory.The challenges of realizing pairwise alignment on APU are to make full use of the shared memory and the cooperation between CPU and GPU.First,for long sequences,we propose a APU-based parallel system,ASW,to do the alignment between long sequences.ASW realizes load balancing in two aspects:task splitting and task scheduling.A model is built according to the resource and algorithm limitation to calculate the suitable size of tasks.Then ASW can dispatch tasks to CPU and GPU dynamically.The experimental results show that ASW achieves a good performance of 7.2GCUPS.Second,for short sequences,we propose a APU-based parallel system,ASWD,to do the alignment between a sequence and database.ASWD chooses the suitable platform according to the characteristics of the database.In order to achieve load balancing,ASWD first calculates a ratio to assign tasks and adjusts the ratio during execution.The experimental results show that the speedup is 2.5 after the adjustment.In conclusion,this thesis implements two parallel systems,ASW and ASWD,based on APU targeting at two application scenarios of pairwise alignment,respectively.A number of optimization are made for the two systems according to the feature of APU and sequence alignment algorithm.