Optimization Of Sequence Alignment Parallel Software On CUDA

Stream applications, such as scientific computation, are abstracted from many fields and now have become a key load on microprocessors. Sequence alignment is one of the stream applications, which is a fundamental operation in bioinformatics. However, the execution of sequence alignment becomes much more time-consuming by exponential growth rate of sequence database. Many traditional computers are reluctant to meet the requirement of real-time, so a new parallel computing platform is urgently demanded. Since the application scenario of NVIDIA GPU has been extended from 3D graphics rendering into general purpose computing, it has become the most successful stream architecture in industry. CUDA is the main driving force to make NVIDIA GPU become a general data parallel computing device.Our research contents and achievements are as follows: (1) Study on the platform adaptivity of sequence alignment parallel software, including developing the coarse-grained parallelism of sequence alignment software on CUDA platform, and the fine-grained parallelism of the core Smith-Waterman algorithm of sequence alignment software. (2) Research on the following four points to optimize sequence alignment parallel software on CUDA platform: optimizing the computation and memory access; load balancing; developing two-level parallelism of sequence alignment; setting the grid and block dimension in a flexible way. Firstly, a new execution algorithm called Optimized GSW is proposed to optimize computing and memory access operations of GPU threads, which is based on the runtime characteristic of Smith-Waterman algorithm. Secondly, to achieve the load balance among GPU threads, and between CPU and GPU, two execution algorithms called G_Optimized GSW and CG_Optimized GSW are designed. These two algorithms improve the utilization of computing resoureces and application performance. Thirdly, we design a two-level parallel algorithm called DL_GSW using partitioning principle in a flexible way on CUDA platform. It changes the mapping method of sub-task, but not very appropriate because of some limitations of CUDA platform. Finaly, setting the grid and block dimension based on specific situations, unlike the method in GSW, which increases the computing power of each GPU thread. (3) Implementing and evaluating the four optimization schemes to prove the high efficiency and adaptability of our optimization schemes, and these conclusions could be applied to other stream applications mapping on CUDA and are also valuable for the development of CUDA architecture.