KIT | KIT-Bibliothek | Impressum | Datenschutz

Coupling SIMD and SIMT Architectures to Boost Performance of a Phylogeny-aware Alignment Kernel

Alachiotis, N.; Berger, S.; Stamatakis, A.

Abstract:

Background: Aligning short DNA reads to a reference sequence alignment is a prerequisite for detecting their biological origin and analyzing them in a phylogenetic context. With the PaPaRa tool we introduced a dedicated dynamic programming algorithm for simultaneously aligning short reads to reference alignments and corresponding evolutionary reference trees. The algorithm aligns short reads to phylogenetic profiles that correspond to the branches of such a reference tree. The algorithm needs to perform an immense number of pairwise alignments. Therefore, we explore vector intrinsics and GPUs to accelerate the PaPaRa alignment kernel.
Results: We optimized and parallelized PaPaRa on CPUs and GPUs. Via SSE 4.1 SIMD (Single Instruction, Multiple Data) intrinsics for x86 SIMD architectures and multi-threading, we obtained a 9-fold acceleration on a single core as well as linear speedups with respect to the number of cores. The peak CPU performance amounts to 18.1 GCUPS (Giga Cell Updates per Second) using all four physical cores on an Intel i7 2600 CPU running at 3.4 GHz. The average CPU performance (averaged over all test runs) is 12.33 GCUPS. ... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000033017
Originalveröffentlichung
DOI: 10.1186/1471-2105-13-196
Scopus
Zitationen: 10
Web of Science
Zitationen: 12
Dimensions
Zitationen: 13
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2012
Sprache Englisch
Identifikator ISSN: 1471-2105
urn:nbn:de:swb:90-330174
KITopen-ID: 1000033017
Erschienen in BMC Bioinformatics
Verlag Springer Fachmedien Wiesbaden
Band 13
Heft 1
Seiten 196
Schlagwörter Alignment kernel, Dynamic programming, PaPaRa, OpenCL, SSE, SIMD, SIMT, GPU
Nachgewiesen in Scopus
Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page