Boosting the FM-index on the GPU : effective techniques to mitigate random memory access
Chacón, Alejandro (Universitat Autònoma de Barcelona)
Marco-Sola, Santiago (Centre Nacional d'Anàlisi Genòmica)
Espinosa, Antonio (Universitat Autònoma de Barcelona)
Ribeca, Paolo (The Pirbright Institute (Regne Unit))
Moure, Juan C (Universitat Autònoma de Barcelona)
Data: |
2015 |
Resum: |
The recent advent of high-throughput sequencing machines producing big amounts of short reads has boosted the interest in efficient string searching techniques. As of today, many mainstream sequence alignment software tools rely on a special data structure, called the FM-index, which allows for fast exact searches in large genomic references. However, such searches translate into a pseudo-random memory access pattern, thus making memory access the limiting factor of all computation-efficient implementations, both on CPUs and GPUs. Here we show that several strategies can be put in place to remove the memory bottleneck on the GPU: more compact indexes can be implemented by having more threads work cooperatively on larger memory blocks, and a k-step FM-index can be used to further reduce the number of memory accesses. The combination of those and other optimisations yields an implementation that is able to process about 2 Gbases of queries per second on our test platform, being about 8× faster than a comparable multi-core CPU version, and about 3× to 5× faster than the FM-index implementation on the GPU provided by the recently announced Nvidia NVBIO bioinformatics library. |
Ajuts: |
Ministerio de Ciencia e Innovación TIN2011-28689-C02-01
|
Drets: |
Tots els drets reservats. |
Llengua: |
Anglès |
Document: |
Article ; recerca ; Versió acceptada per publicar |
Matèria: |
GPGPU ;
Bioinformatics ;
Short read mapping ;
FM-index ;
Fine-grain parallelism ;
Memory-level parallelism |
Publicat a: |
IEEE/ACM Transactions on computational biology and bioinformatics, Vol. 12, No. 5 (Sep.-Oct. 2015) , ISSN 1545-5963 |
DOI: 10.1109/TCBB.2014.2377716
El registre apareix a les col·leccions:
Articles >
Articles de recercaArticles >
Articles publicats
Registre creat el 2015-04-28, darrera modificació el 2022-09-15