Xia Fei, Jin Guoqing
Electronic Engineering College, Naval University of Engineering, Wuhan 430033, China.
J Bioinform Comput Biol. 2014 Jun;12(3):1450008. doi: 10.1142/S0219720014500085. Epub 2014 Jan 21.
PKNOTS is a most famous benchmark program and has been widely used to predict RNA secondary structure including pseudoknots. It adopts the standard four-dimensional (4D) dynamic programming (DP) method and is the basis of many variants and improved algorithms. Unfortunately, the O(N(6)) computing requirements and complicated data dependency greatly limits the usefulness of PKNOTS package with the explosion in gene database size. In this paper, we present a fine-grained parallel PKNOTS package and prototype system for accelerating RNA folding application based on FPGA chip. We adopted a series of storage optimization strategies to resolve the "Memory Wall" problem. We aggressively exploit parallel computing strategies to improve computational efficiency. We also propose several methods that collectively reduce the storage requirements for FPGA on-chip memory. To the best of our knowledge, our design is the first FPGA implementation for accelerating 4D DP problem for RNA folding application including pseudoknots. The experimental results show a factor of more than 50x average speedup over the PKNOTS-1.08 software running on a PC platform with Intel Core2 Q9400 Quad CPU for input RNA sequences. However, the power consumption of our FPGA accelerator is only about 50% of the general-purpose micro-processors.
PKNOTS是一个非常著名的基准程序，已被广泛用于预测包括假结在内的RNA二级结构。它采用标准的四维（4D）动态规划（DP）方法，是许多变体和改进算法的基础。不幸的是，随着基因数据库规模的爆炸式增长，O(N(6))的计算需求和复杂的数据依赖性极大地限制了PKNOTS软件包的实用性。在本文中，我们提出了一个基于FPGA芯片的细粒度并行PKNOTS软件包和原型系统，用于加速RNA折叠应用。我们采用了一系列存储优化策略来解决“内存墙”问题。我们积极利用并行计算策略来提高计算效率。我们还提出了几种方法，共同减少FPGA片上内存的存储需求。据我们所知，我们的设计是第一个用于加速包括假结在内的RNA折叠应用的4D DP问题的FPGA实现。实验结果表明，对于输入的RNA序列，与在配备英特尔酷睿2 Q9400四核CPU的PC平台上运行的PKNOTS-1.08软件相比，平均加速比超过50倍。然而，我们的FPGA加速器的功耗仅约为通用微处理器的50%。
