\input zb-basic
\input zb-ioport
\iteman{io-port 05772059}
\itemau{Steffen, Peter; Giegerich, Robert; Giraud, Mathieu}
\itemti{GPU parallelization of algebraic dynamic programming.}
\itemso{Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 8th international conference, PPAM 2009, Wroclaw, Poland, September 13--16, 2009. Revised selected papers, Part II. Berlin: Springer (ISBN 978-3-642-14402-8/pbk). Lecture Notes in Computer Science 6068, 290-299 (2010).}
\itemab
Summary: 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.1\times $ to $25.8\times $ on a Nvidia GTX 280 through the CUDA libraries.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-14403-5\_31}
\end