Cargando…

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 P...

Descripción completa

Detalles Bibliográficos
Autores principales: Xia, Fei, Dou, Yong, Zhou, Xingming, Yang, Xuejun, Xu, Jiaqing, Zhang, Yang
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2009
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648794/
https://www.ncbi.nlm.nih.gov/pubmed/19208138
http://dx.doi.org/10.1186/1471-2105-10-S1-S37
_version_ 1782164989883187200
author Xia, Fei
Dou, Yong
Zhou, Xingming
Yang, Xuejun
Xu, Jiaqing
Zhang, Yang
author_facet Xia, Fei
Dou, Yong
Zhou, Xingming
Yang, Xuejun
Xu, Jiaqing
Zhang, Yang
author_sort Xia, Fei
collection PubMed
description 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.
format Text
id pubmed-2648794
institution National Center for Biotechnology Information
language English
publishDate 2009
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-26487942009-03-03 Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA Xia, Fei Dou, Yong Zhou, Xingming Yang, Xuejun Xu, Jiaqing Zhang, Yang BMC Bioinformatics Research 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. BioMed Central 2009-01-30 /pmc/articles/PMC2648794/ /pubmed/19208138 http://dx.doi.org/10.1186/1471-2105-10-S1-S37 Text en Copyright © 2009 Xia et al; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an open access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Xia, Fei
Dou, Yong
Zhou, Xingming
Yang, Xuejun
Xu, Jiaqing
Zhang, Yang
Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title_full Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title_fullStr Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title_full_unstemmed Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title_short Fine-grained parallel RNAalifold algorithm for RNA secondary structure prediction on FPGA
title_sort fine-grained parallel rnaalifold algorithm for rna secondary structure prediction on fpga
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648794/
https://www.ncbi.nlm.nih.gov/pubmed/19208138
http://dx.doi.org/10.1186/1471-2105-10-S1-S37
work_keys_str_mv AT xiafei finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga
AT douyong finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga
AT zhouxingming finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga
AT yangxuejun finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga
AT xujiaqing finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga
AT zhangyang finegrainedparallelrnaalifoldalgorithmforrnasecondarystructurepredictiononfpga