Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA.
BACKGROUND
In the field of RNA secondary structure prediction, the RNAalifold algorithm is one of the most popular methods using free energy minimization. However, general-purpose computers including parallel computers or multi-core computers exhibit parallel efficiency of no more than 50%. Field Programmable Gate-Array (FPGA) chips provide a new approach to accelerate RNAalifold by exploiting fine-grained custom design.


RESULTS
RNAalifold shows complicated data dependences, in which the dependence distance is variable, and the dependence direction is also across two dimensions. We propose a systolic array structure including one master Processing Element (PE) and multiple slave PEs for fine grain hardware implementation on FPGA. We exploit data reuse schemes to reduce the need to load energy matrices from external memory. We also propose several methods to reduce energy table parameter size by 80%.


CONCLUSIONS
To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete RNAalifold algorithm. The experimental results show a factor of 12.2 speedup over the RNAalifold (ViennaPackage - 1.6.5) software for a group of aligned RNA sequences with 2981-residue running on a Personal Computer (PC) platform with Pentium 4 2.6 GHz CPU.
Xia
Fei
F
National Laboratory for Parallel&Distributed Processing, Department of Computer Science, National University of Defense Technology, ChangSha, 410073, PR China. xcyphoenix@nudt.edu.cn
Dou
Yong
Y
Zhou
Xingming
X
Yang
Xuejun
X
Xu
Jiaqing
J
Zhang
Yang
Y
D000465:Algorithms; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA; D012984:Software
D012313:RNA