Fine-grained parallel application specific computing for RNA secondary structure prediction using SCFGS on FPGA

ABSTRACT

In the field of RNA secondary structure prediction, the CYK (Coche-Younger-Kasami) algorithm is a most popular methods using SCFG (stochastic context-free grammars) model. However, general purpose parallel computers including SMP multiprocessors or cluster systems exhibit low parallel efficiency and they are too expensive to be used easily for many research institutes. FPGA chips provide a new approach to accelerate the CYK algorithm by exploiting fine-grained custom design. The CYK algorithm shows complicated data dependence, 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 PE and multiple slave PEs for fine grain hardware implementation on FPGA. We partition tasks by columns and assign tasks to PEs for load balance. We exploit data reuse schemes to reduce the need to load matrix from external memory. To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete CYK/inside algorithm. The experimental results show a factor of more than 14 speedup over the Infernal-0.55 software running on a PC platform with Pentium 4 2.66GHz CPU. The computational power of our platform with FPGA 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 15% and 10% of the latter respectively.

REFERENCES

• 1: S. R. Eddy. A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an rna secondary structure. BMC Bioinformatics, 3(18), 2002.
• 2: E. Rivas and S. R. Eddy. A dynamic programming algorithm for rna structure prediction including pseudoknots. J. Mol. Biol., 285:2053--2068, 1999.
• 3: S. R. Eddy. What is dynamic programming? Journal of Nature Biotechnology, 22(7), July 2004.
• 4: T. Liu and B. Schmidt. Parallel rna secondary structure prediction using stochastic context-free grammars. Concurrency Computat.: Pract. Exper., 17:1669--1685, 2005.
• 5: J. C. Hill and A. Wayne. A cyk approach to parsing in parallel: A case study. In Technical Symposium on Computer Science Education: Proceedings of the twenty-second SIGCSE technical symposium on Computer science education, March 1991.
• 6: G. Tan, S. Feng, and N. Sun. Exploiting parallelization for rna secondary structure prediction in cluster. In Proc. International Conference on Computational Science (ICCS'05), LNCS 3516, pages 979--982, May 2005.
• 7: G. Tan, L. Xu, S. Feng, and N. Sun. An experimental study of optimizing bioinformatics applications. In Proc. International Conference on Parallel and Distributed Processing Symposium. IEEE, 2006.
• 8: A. Jacob, J. Buhler, et al. Accelerating nussinov rna secondary structure prediction with systolic arrays on fpgas. In Proc. International Conference on Application-specific Systems, Architectures and Processors (ASAP'08), pages 191--196. IEEE, 2008.
• 9: R. Nussinov, G. Pieczenik, J. R. Griggs, and D. Kleitman. Algorithms for loop matchings. SIAM Journal on Applied mathematics, 35:68--82, 1978.
• 10: C. Ciressan, E. Sanchez, M. Rajman, and J.-C. Chappelier. An fpga-based coprocessor for the parsing of context-free grammars. In Proc. Symposium on Field-Programmable Custom Computing Machines (FCCM'2000), pages 236--245.
• 11: C. Ciressan, E. Sanchez, M. Rajman, and J.-C. Chappelier. An fpga-based syntactic parser for real-life almost unrestricted context-free grammars. In Proc. International Conference on Field Programmable Logic and Application (FPL'2001), LNCS 2147, pages 590--594. IEEE, October 2001.
• 12: S. R. Eddy and R. Durbin. Rna sequence analysis using covariance models. Nucleic Acids Research, 22(11):2079--2088, 1994.
• 13: K. Lari and S. Young. Applications of stochastic context--free grammars using the inside-outside algorithm. Computer Speech and Languages, 5:237--257, 1991.
• 14: Infernal-0.55 software. Washington University School of Medicine web site, http://infernal.janelia.org/, 2009.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, RNA, SCFGS, reconfigurable algorithm accelerator, secondary structure prediction