Web of Science: 12 cites, Scopus: 18 cites, Google Scholar: cites
Thread-cooperative, bit-parallel computation of Levenshtein distance on GPU
Chacón de San Baldomero, Alejandro (Universitat Autònoma de Barcelona)
Marco-Sola, Santiago (Centre Nacional d'Anàlisi Genòmica)

Data: 2014
Resum: Approximate string matching is a very important problem in computational biology; it requires the fast computation of string distance as one of its essential components. Myers' bit-parallel algorithm improves the classical dynamic programming approach to Levenshtein distance computation, and offers competitive performance on CPUs. The main challenge when designing an efficient GPU implementation is to expose enough SIMD parallelism while at the same time keeping a relatively small working set for each thread. In this work we implement and optimise a CUDA version of Myers' algorithm suitable to be used as a building block for DNA sequence alignment. We achieve high efficiency by means of a cooperative parallelisation strategy for (1) very-long integer addition and shift operations, and (2) several simultaneous pattern matching tasks. In addition, we explore the performance impact obtained when using features specific to the Kepler architecture. Our results show an overall performance of the order of tera cells updates per second using a single high-end Nvidia GPU, and factor speedups in excess of 20 with respect to a sixteen-core, non-vectorised CPU implementation.
Nota: Número d'acord de subvenció MICINN/TIN2011-28689-C02-01
Drets: Tots els drets reservats.
Llengua: Anglès
Document: conferenceObject
Matèria: SIMD ; GPU ; CUDA ; Myers' algorithm
Publicat a: ICS : International Conference on Supercomputing. Munic, Alemanya, : 2014

DOI: 10.1145/2597652.2597677

10 p, 646.3 KB

El registre apareix a les col·leccions:
Contribucions a jornades i congressos > Ponències i comunicacions

 Registre creat el 2015-04-28, darrera modificació el 2021-03-16

   Favorit i Compartir