Accelerating Sequence Alignments
Based on FM-Index
Using the Intel KNL Processor
1Universidad de Málaga
2Universidad de Zaragoza, I3A
News
- December 2018: Article available on IEEE Xplore.
- March 2019: Web launched.
- August 2020: Article published on IEEE Xplore (print ISSN).
Abstract
Abstract—FM-index is a compact data structure suitable for fast matches of short reads to large reference genomes. The matching algorithm using this index exhibits irregular memory access patterns that cause frequent cache misses, resulting in a memory bound problem. This paper analyzes different FM-index versions presented in the literature, focusing on those computing aspects related tothe data access. As a result of the analysis, we propose a new organization of FM-index that minimizes the demand for memorybandwidth, allowing a great improvement of performance on processors with high-bandwidth memory, such as the second-generationIntel Xeon Phi (Knights Landing, or KNL), integrating ultra high-bandwidth stacked memory technology. As the roofline model shows, our implementation reaches 95% of the peak random access bandwidth limit when executed on the KNL and almost all the available bandwidth when executed on other Intel Xeon architectures with conventional DDR memory. In addition, the obtained throughput in KNL is much higher than the results reported for GPUs in the literature.Downloads
Bibtex
@article{Herruzo_FMindex_KNL,
author = {J.M. Herruzo, S. Navarro-González, P. Ibáñez, V. Viñals, J. Alastruey and O. Plata},
title = {Accelerating Sequence Alignments Based on FM-Index Using the Intel KNL Processor},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
year={2020},
volume={17},
number={4},
pages={1093-1104},
keywords={FM-index; short-read alignment; high-bandwidth memory; Intel Xeon Phi Knights-Landing},
doi={10.1109/TCBB.2018.2884701},
ISSN={1557-9964},
month={-}}
Related
2018: Exact Alignment with FM-index on the Intel Xeon Phi Knights Landing Processor. Jose M. Herruzo, Sonia Gonzalez-Navarro, Pablo Ibañez, Victor Viñals, Jesús Alastruey-Benedé, and Oscar Plata. HPCA 2018 Workshop on Accelerator Architecture in Computational Biology and Bioinformatics Workshop (AACBB 2018), February 24, 2018, Viena, Austria.
[paper, pdf] [slides, pdf].