CPU和GPU协同并行加速多生物序列比对

Accelerating Multiple Bio-sequences Alignment Using CPU and GPU Cooperative Computing

将主库构建阶段的输入序列分成多个分主库、将主库扩展阶段的主库元素划分成多个计算窗口,使之符合GPU并行计算的线程结构特性,GPU以计算窗口为单位并行计算比对矩阵、并行约减主库及并行扩展比对矩阵,结合库优化思想优化主库构建过程,利用阈值cutoff控制主库约减程度,设计实现CPU和多个GPU协同计算并行比对多生物序列的高效可扩展算法OGM SA.实验结果表明,当cutoff≤0.20时,算法OGM SA的比对结果质量与算法G-M SA相同,计算速度是G-M SA算法的近4倍,内存容量需求比G-MSA算法也有所降低.

The input bio-sequences are divided into multiple partial primary libraries in constructing primary library phase, and the ele- ments in primary library are partitioned into multiple compute windows in extending primary library phase to conform the threads structural characteristics for GPU computing. Several GPUs compute alignment matrix, reduce primary library and extend alignment matrix in parallel by using a compute window as a unit. The constructing primary library procedure is optimized by the library optimi- zation method and the library reduction degree is controlled by the thresholdvalue#cutoff. An efficient and scalable parallel aligning multiple bio-sequences algorithm OGMSA is designed by CPU and GPUs cooperative computing. The experimental results show that when cutoff〈~O. 20,the alignment quality of OGMSA algorithm is the same as that of G-MSA algorithm, the speed of OGMSA algo- rithm is nearly 4 times than that of G-MSA algorithm, and the memory capacity requirement of running OGMSA algorithm is also low- er than that of running G-MSA algorithm.