Web of Science: 2 citas, Scopus: 3 citas, Google Scholar: citas,
Boosting the FM-index on the GPU : effective techniques to mitigate random memory access
Chacón de San Baldomero, Alejandro (Universitat Autònoma de Barcelona)
Marco-Sola, Santiago (Centre Nacional d'Anàlisi Genòmica)
Espinosa Morales, Antonio Miguel (Universitat Autònoma de Barcelona)
Ribeca, Paolo (The Pirbright Institute)
Moure López, Juan Carlos (Universitat Autònoma de Barcelona)

Fecha: 2015
Resumen: 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.
Nota: Número d'acord de subvenció MICINN/TIN2011-28689-C02-01
Derechos: Tots els drets reservats.
Lengua: Anglès.
Documento: article ; recerca ; acceptedVersion
Materia: GPGPU ; Bioinformatics ; Short read mapping ; FM-index ; Fine-grain parallelism ; Memory-level parallelism
Publicado en: IEEE/ACM Transactions on computational biology and bioinformatics, Vol. 12, No. 5 (Sep.-Oct. 2015) , ISSN 1545-5963

DOI: 10.1109/TCBB.2014.2377716

13 p, 995.3 KB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados

 Registro creado el 2015-04-28, última modificación el 2019-02-03

   Favorit i Compartir