OpenCL-based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors
D. Castells-Rufas, S. Marco-Sola, Q. Aguado-Puig, A. Espinosa-Morales, J.C. Moure, L. Alvarez, M. Moreto, in: 2021 31st International Conference on Field-Programmable Logic and Applications (FPL), IEEE, 2021.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Castells-Rufas, David;
Marco-Sola, Santiago;
Aguado-Puig, Quim;
Espinosa-Morales, Antonio;
Moure, Juan Carlos;
Alvarez, Lluc;
Moreto, Miquel
Abstract
An FPGA accelerator for the computation of the semi-global Levenshtein distance between a pattern and a reference text is presented. The accelerator provides an important benefit to reduce the execution time of read-mappers used in short-read genomic sequencing. Previous attempts to solve the same problem in FPGA use the Myers algorithm following a column approach to compute the dynamic programming table. We use an approach based on diagonals that allows for some resource savings while maintaining a very high throughput of 1 alignment per clock cycle. The design is implemented in OpenCL and tested on two FPGA accelerators. The maximum performance obtained is 91.5 MPairs/s for 100 × 120 sequences and 47 MPairs/s for 300 × 360 sequences, the highest ever reported for this problem.
Keywords
Publishing Year
Proceedings Title
2021 31st International Conference on Field-Programmable Logic and Applications (FPL)
LibreCat-ID
Cite this
Castells-Rufas D, Marco-Sola S, Aguado-Puig Q, et al. OpenCL-based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors. In: 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE; 2021. doi:10.1109/fpl53798.2021.00036
Castells-Rufas, D., Marco-Sola, S., Aguado-Puig, Q., Espinosa-Morales, A., Moure, J. C., Alvarez, L., & Moreto, M. (2021). OpenCL-based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors. 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). https://doi.org/10.1109/fpl53798.2021.00036
@inproceedings{Castells-Rufas_Marco-Sola_Aguado-Puig_Espinosa-Morales_Moure_Alvarez_Moreto_2021, title={OpenCL-based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors}, DOI={10.1109/fpl53798.2021.00036}, booktitle={2021 31st International Conference on Field-Programmable Logic and Applications (FPL)}, publisher={IEEE}, author={Castells-Rufas, David and Marco-Sola, Santiago and Aguado-Puig, Quim and Espinosa-Morales, Antonio and Moure, Juan Carlos and Alvarez, Lluc and Moreto, Miquel}, year={2021} }
Castells-Rufas, David, Santiago Marco-Sola, Quim Aguado-Puig, Antonio Espinosa-Morales, Juan Carlos Moure, Lluc Alvarez, and Miquel Moreto. “OpenCL-Based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors.” In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 2021. https://doi.org/10.1109/fpl53798.2021.00036.
D. Castells-Rufas et al., “OpenCL-based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors,” 2021, doi: 10.1109/fpl53798.2021.00036.
Castells-Rufas, David, et al. “OpenCL-Based FPGA Accelerator for Semi-Global Approximate String Matching Using Diagonal Bit-Vectors.” 2021 31st International Conference on Field-Programmable Logic and Applications (FPL), IEEE, 2021, doi:10.1109/fpl53798.2021.00036.
Google Scholar