Research On Key Technologies Of Parallel Optimization For Biological Sequence Analysis Algorithm Based On CPU+GPU Heterogeneous System

Biological Sequence Analysis is an important foundation of the field of modernbioinformatics research with great theoretical and practical values. With the continuousdevelopment of biotechnology, the sizes of the biological sequences databases are expandingrapidly. The support demand from the high-performance computing for biological sequenceanalysis is becoming very urgent. In recent years, with the rapid development of GPU hardwareand its programming model, using heterogeneous systems based on CPU and GPU to acceleratebiological sequence analysis algorithms and applications has become an inevitable trend.However, how to effectively utilize the computing power of the heterogeneous systems is still agreat challenge.To meet these challenges, this thesis emphasizes on the study of parallel algorithmoptimization for biological sequence analysis based on the CPU+GPU heterogeneous system.The main work and research results are as follows:(1) We made studies on the the collaborative parallel computing mode and optimizationstrategies of heterogeneous systems. We established a computing task partitioning model and aload balancing model, proposed optimization strategies of communication between the CPU andGPU of heterogeneous system, introduced maximize equipment utilization, multi-level storagereuse and instruction-level optimization of the GPU program performance optimization strategybased on CUDA architecture’s features.(2) A hybrid parallel algorithm combining inter-task and intra-task paralleling ofSmith-Waterman algorithm is presented based on deep study of core algorithm of the field ofsequence alignment. On the GPU side, diagonal-priority storage and data-cross storage strategyare used to optimize memory accessing, and software pipelining strategy are used to enhance theutilization of computing resource. We designed a collaborative parallel architecture to make theCPU and GPU process a certain percentage of the computing tasks simultaneously. Theexperimental results show that our design can enhance the application performance and thesystem efficiency significantly.(3) Based on the study in characteristics of the Zuker algorithm, a multi-level parallelarchitecture with diamond-tile-wave-front algorithm is introduced. On the GPU side, the threadscheduling stategy and storage optimization and compute-in-advance optimization strategies areproposed. We also designed a collaborative parallel algorithm for Zuker based on CPU+GPUheterogeneous systems. The results show that the proposed optimization design has anacceleration effect of over a hundred times for the original serial version of RNA secondarystructure prediction software.