GPU Parallelization of Algebraic Dynamic Programming

Peter Steffen, Robert Giegerich, Mathieu Giraud
Bielefeld University, Faculty of Technology, Germany
In Parallel Processing and Applied Mathematics, Vol. 6068 (2010), pp. 290-299


   title={GPU Parallelization of Algebraic Dynamic Programming},

   author={Steffen, P. and Giegerich, R. and Giraud, M.},

   journal={Parallel Processing and Applied Mathematics},





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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: