基于FPGA的细粒度并行CYK算法加速器设计与实现

Fine-Grained Parallel RNA Secondary Structure Prediction Using SCFGs on FPGA

基于随机上下文无关文法(SCFG)理论模型进行RNA二级结构预测是目前采用计算方法研究RNA二级结构的一种重要途径.由于基于SCFG模型的标准结构预测算法(Coche-Younger-Kasami,CYK)巨大的时空复杂度,对CYK算法进行加速成为计算生物学领域一个极具挑战性的热点问题.CYK的并行性能受限于算法多维度、非一致性的数据依赖关系和较低的计算/通信比,现有的基于通用微处理器结构的大规模并行处理方案不能获得令人满意的加速效果,并且大规模并行计算机系统硬件设备的购置、使用、日常维护的成本高昂,其适用性受到诸多限制.文中在深入分析CYK算法计算特征的基础上,基于FPGA平台提出并实现了一种细粒度的并行CYK算法.设计采用了对三维动态规划矩阵"按区域分割"和"逐层按列并行处理"的计算策略实现了多个处理单元间的负载均衡;采用数据预取、滑动窗口和数据传递流水线实现处理单元间的数据重用,有效解决了计算和通信间的平衡问题;设计了一种类似脉动阵列(systolic-like array)结构的主从多PE并行计算阵列,并在目前最大规模的FPGA芯片(Xilinx XC5VLX330)上成功集成了16个处理单元(processing elements),实验结果表明作者提出的CYK算法加速器结构具备良好的可扩展性.当RNA序列长度为959bps,CM模型状态数为3145时,与运行在Intel双核E5200 2.5GHzCPU、2.0GB主存通用计算上的Infernal-1.0软件相比,可获得超过14倍的加速效果.配置一个FP-GA算法加速器的通用计算平台的综合处理性能与包含20个Intel-Xeon CPU的PC集群相当,而硬件成本仅为后者的20%,系统功耗不到后者的10%.

In the field of RNA secondary structure prediction, CYK （Coche-Younger-Kasami） algorithm is one of the most popular methods using SCFG （stochastic context-free grammars） model. Accelerating SCFGs for large models and large RNA database searches becomes a challenge task in computational bioinformatics because of the O（L3） computational demands that are required. General purpose computers including parallel SMP multiprocessors or cluster systems exhibit low parallel efficiency. Furthermore, large scaled parallel computers are too expensive to be used easily for many research institutes. FPGA chips provide a new approach to accelerate CYK algorithm by exploiting fine-grained custom design. CYK algorithm shows complicated data dependence, in which the dependence distance is variable, and the dependence direction is also across two dimensions. This paper proposes a systolic-like array structure including one master PE （Processing Element） and multiple slave PEs for fine-grained hardware implementation on FPGA. By columns and assign, tasks are partitioned to PEs for load balance. Data reuse schemes reduce the need to load energy matrices from external memory. The experimental results show a factor of more than 14 speedup over the Infernal-1.0 software for 959-residue RNA sequence and a CM model with 3145 states running on a PC platform with Intel Dual-Core 2.5GHz CPU. The computational power of the accelerator is comparable to a PC cluster consisting of 20 Intel-Xeon CPUs for RNA secondary structure prediction using SCFGs, but the hardware cost and power consumption is only about 20% and 10% that of the latter respectively.