Uma implementação do algoritmo LCS em FPGA usando High-Level Synthesis
Abstract
This paper presents an implementation of the Longest Common Subsequence (LCS) algorithm for comparing two biological sequences using High Level Synthesis (HLS) for FPGAs. Results were obtained with a CPU Intel Core® i7-3770 CPU and a FPGA Xilinx® ADM-PCIE-KU3 that has a Xilinx Kintex® UltraScale XCKU060-2. Our experiments showed that the CPU implementation consumed 6.8x more energy to execute compared to FPGA.
References
Arslan, A. (2004). Sequence Alignment. Biyoinformatik-II.
Blum, C., Blesa, M. J., and López-Ibáñez, M. (2009). Beam search for the longest common subsequence problem. Comput. Oper. Res., 36(12):3178–3186.
Bucak, I. O. and Uslan, V. (2011). Sequence alignment from the perspective of stochastic optimization: a survey. Turkish Journal of Electrical Engineering and Computer Sciences, 19:157–173.
Canonical (2015). Ubuntu Manpage: powerstat - a tool to measure power consumption. http://manpages.ubuntu.com/manpages/xenial/man8/powerstat.8.html.
Mount, D. W. (2001). Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press.
NCBI (2019). National center for biotechnology information. National Center for Biotechnology Information. Disponı́vel em https://www.ncbi.nlm.nih.gov/.
Needleman, S. B. Setubal, J. C. and Meidanis, J. (1997). Introduction to Computational Molecular Biology. PWS.
Smith, T. F. and Waterman, M. S. (1981). Identification of common molecular subsequences. pages 195–197.
Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM, 21(1):168–173.
Xilinx (2016) Vivado high-level synthesis. Xilinx. Disponı́vel em https://www.xilinx.com/products/design-tools/vivado/integration/esl-design.html.
Xilinx Corporation (2019). Ultrafast high-level productivity design methodology guide.
Blum, C., Blesa, M. J., and López-Ibáñez, M. (2009). Beam search for the longest common subsequence problem. Comput. Oper. Res., 36(12):3178–3186.
Bucak, I. O. and Uslan, V. (2011). Sequence alignment from the perspective of stochastic optimization: a survey. Turkish Journal of Electrical Engineering and Computer Sciences, 19:157–173.
Canonical (2015). Ubuntu Manpage: powerstat - a tool to measure power consumption. http://manpages.ubuntu.com/manpages/xenial/man8/powerstat.8.html.
Mount, D. W. (2001). Bioinformatics: Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press.
NCBI (2019). National center for biotechnology information. National Center for Biotechnology Information. Disponı́vel em https://www.ncbi.nlm.nih.gov/.
Needleman, S. B. Setubal, J. C. and Meidanis, J. (1997). Introduction to Computational Molecular Biology. PWS.
Smith, T. F. and Waterman, M. S. (1981). Identification of common molecular subsequences. pages 195–197.
Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM, 21(1):168–173.
Xilinx (2016) Vivado high-level synthesis. Xilinx. Disponı́vel em https://www.xilinx.com/products/design-tools/vivado/integration/esl-design.html.
Xilinx Corporation (2019). Ultrafast high-level productivity design methodology guide.
Published
2019-11-08
How to Cite
JORGE, Carlos Antonio; NERY, Alexandre; MELO, Alba.
Uma implementação do algoritmo LCS em FPGA usando High-Level Synthesis.
Proceedings of the Symposium on High Performance Computing Systems (SSCAD), [S.l.], p. 324-333, nov. 2019.
ISSN 0000-0000.
Available at: <https://sol.sbc.org.br/index.php/sscad/article/view/8679>. Date accessed: 18 may 2024.
doi: https://doi.org/10.5753/wscad.2019.8679.
Section
Full Papers
