Uma implementação do algoritmo LCS em FPGA usando High-Level Synthesis
Resumo
Este trabalho apresenta uma implementação do algoritmo Longest Common Subsequence (LCS) para comparação de duas sequências biológicas utilizando linguagem de alto nı́vel High Level Synthesis (HLS) para FPGAs. Foram comparados resultados entre a execução em uma CPU Intel Core i73770 e uma FPGA Xilinx® ADM-PCIE-KU3 que possui uma Xilinx Kintex® UltraScale XCKU060-2. Os resultados mostraram que a implementação em CPU consumiu 6,8x mais energia em relação à FPGA.
Referências
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.
Publicado
08/11/2019
Como Citar
JORGE, Carlos Antonio; NERY, Alexandre; MELO, Alba.
Uma implementação do algoritmo LCS em FPGA usando High-Level Synthesis. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 20. , 2019, Campo Grande.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 324-333.
DOI: https://doi.org/10.5753/wscad.2019.8679.
