title: Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA.
abstract: 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.
authors.affiliation: National Laboratory for Parallel&Distributed Processing, Department of Computer Science, National University of Defense Technology, ChangSha, 410073, PR China. xcyphoenix@nudt.edu.cn
authors.forename: Fei
authors.initials: F
authors.lastname: Xia
authors.forename: Yong
authors.initials: Y
authors.lastname: Dou
authors.forename: Xingming
authors.initials: X
authors.lastname: Zhou
authors.forename: Xuejun
authors.initials: X
authors.lastname: Yang
authors.forename: Jiaqing
authors.initials: J
authors.lastname: Xu
authors.forename: Yang
authors.initials: Y
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA; D012984:Software
chemical_list: D012313:RNA