基于异构平台的高复杂度生物序列分析算法并行化研究

Bioinformatics, as a new coming interdiscipline based on the development of several branches of science, has very important intension of theory and practical meanings, which has widely applied in many scientific fields. Biological sequence analysis has become a fundamental task of bioinformatics and modern life science. High performance computer systems based on general-purpose multi-core processors are widely used to accelerate sequence analysis algorithms. However, parallel efficiency is greatly limited by the diversification of program features: bit-wised parallelism, complicated and multi-dimensional data dependency, and tight synchronization resulting from irregular computing and storage features. Although general-purpose architecture computers have powerful peak performance, efficiently executing the task of bio-sequence analysis on a general-purpose parallel computer becomes very awkward..Recently, the use of FPGA and GPU coprocessors has become a promising approach for accelerating bioinformatics applications. In this project, we are going to research fine-grained parallelized algorithms and structures for accelerating complex bio-sequence structure prediction and analysis algorithms based on FPGA and GPU computing platforms. We analysis the dynamic computing and storage features of classic bioinformatics algorithms and models and propose a series of strategies to eliminate data dependency and reduce storage requirements. We propose a "time-space domain overlapping" analysis method to address the complicated data dependency and limited storage bandwidth problem. We exploit data reuse, task distribution and parallel schemes for load balance. And we implement massive parallelism and customized computing for accelerating typical structure prediction and analysis applications on a heterogeneous test-bed platform constructed by general-purpose CPU combination with FPGA/GPU accelerators. Moreover, we want to extract a general optimization method for parallel processing on heterogeneous computer architecture based on FPGA/GPU coprocessors including a basic hardware structural template and parallel programming framework for the group of algorithms oriented to special domain. This method is helpful to decrease design complexity and will lay a foundation for fast generation of algorithm accelerator. Our research can provide technology reference for improving the processing ability of bioinformatics applications and algorithm accelerator generation in other scientific computing field.

生物信息学属于多学科前沿交叉科学，应用广泛，意义重大。生物序列分析是生物信息学乃至现代生命科学领域重要的基础性研究工作，该领域的应用具有程序特征多样化、数据相关多维度、访存行为不规则等特点。通用结构计算机虽然能够提供很强的峰值计算能力，但是不能完全适应该领域复杂计算特性的特殊要求，计算效率不高。.课题以序列分析领域中的复杂结构预测和分析算法对高性能计算的需求为背景，基于通用微处理器结合硬件算法加速器（FPGA和GPU）的异构体系结构，从提取典型方法的动态计算特征入手，研究对复杂数据相关和不规则存储访问的优化方法，对典型算法实现细粒度并行，达到高效加速计算的目的；并在此基础上提取普适的并行优化方法，为特定领域的算法群提供一种基本的硬件结构模板和并行程序设计框架，为有效降低算法加速器设计复杂度、实现加速器快速生成奠定基础，为提高对生物信息的处理能力提供技术参考。

生物信息学属于多学科前沿交叉科学，应用广泛，意义重大。生物序列分析是生物信息学乃至现代生命科学领域重要的基础性研究工作，该领域具有程序特征多样化、数据相关多维度、访存行为不规则等特点。通用计算机虽然能够提供很强的峰值计算能力，但是不能完全适应该领域复杂计算特性的特殊要求，计算效率不高。课题以复杂结构预测算法对高性能计算的需求为背景，基于CPU结合FPGA和GPU硬件加速器的异构体系结构，从提取典型方法的动态计算特征入手，研究对复杂数据相关和不规则存储访问的优化方法，对典型算法实现细粒度并行，达到高效加速计算的目的。课题主要研究内容和成果如下：.（1）针对不同领域动态规划算法的数据相关性和存储访问特征，基于FPGA平台提出了资源受限条件下的数据相关性转换、负载平衡的任务划分和存储调度策略，设计了并行计算结构，对Zuker、CYK、PKNOTS、Phaistos算法实现了细粒度并行和硬件加速。综合采用可变粒度运算单元、数据驱动的循环展开执行、不规则访存优化技术，构建了基于FPGA+CPU的异构平台，并以CPU为参照，对并行算法的性能进行分析和评估。.（2）基于GPU+CPU异构计算平台，研究了Zuker、CYK、Phaistos、CONSAN、RSEARCH等典型结构预测算法并行和协同计算技术，主要包括：并行程序和数据在GPU上的映射问题；GPU片上和片外访存优化；负载平衡的动态任务分配和调度；CPU和GPU的高效协同工作机制，并以CPU为参照，对并行算法的性能进行分析和评估。.（3）基于FPGA平台研究了异构体系结构设计模板和算法加速器生成方法，提出了面向领域的细粒度算法加速器硬件结构模板，包括运算单元阵列、执行控制器、运算单元和存储结构等模块及参数；并设计了包含任务划分策略、核心算法、数据IO、同步和通信方式在内的并行程序设计框架。.（4）基于FPGA和GPU算法加速器构建了CPU+FPGA和CPU+GPU两种异构体系结构原型系统，充分利用CPU通用、可靠和算法加速器灵活、高效的特点，实现二者的优势互补和高效协同运行，达到了对序列分析典型应用的整体加速效果。.研究结果表明，采用异构计算平台对高复杂度生物序列分析应用具有显著的加速效果，平均可获得一个数量级以上的全局加速比，并能实现提高计算性能和降低系统功耗的双重目标。