Web of Science: 16 cites, Scopus: 17 cites, Google Scholar: cites,
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


Postprint
13 p, 995.3 KB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2015-04-28, darrera modificació el 2022-09-15



   Favorit i Compartir