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%.
CONCLUSION: 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.