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:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
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