GPU Parallelization of Algebraic Dynamic Programming

Abstract : Algebraic Dynamic Programming (ADP) is a framework to encode a broad range of optimization problems, including common bioinformatics problems like RNA folding or pairwise sequence alignment. The ADP compiler translates such ADP programs into C. As all the ADP problems have similar data dependencies in the dynamic programming tables, a generic parallelization is possible. We updated the compiler to include a parallel backend, launching a large number of independent threads. Depending on the application, we report speedups ranging from 6.1x to 25.8x on a Nvidia GTX 280 through the CUDA libraries.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00438219
Contributor : Mathieu Giraud <>
Submitted on : Thursday, December 3, 2009 - 8:06:25 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Tuesday, October 16, 2012 - 3:15:08 PM

File

CP54.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00438219, version 1

Collections

Citation

Peter Steffen, Robert Giegerich, Mathieu Giraud. GPU Parallelization of Algebraic Dynamic Programming. Parallel Processing and Applied Mathematics / Parallel Biocomputing Conference (PPAM / PBC 09), Sep 2009, Wroclaw, Poland. ⟨inria-00438219⟩

Share

Metrics

Record views

697

Files downloads

1033