Dr. Ing. Frank Padberg

In this thesis we focus on parallelizing dynamic programming programs. There exist many parallel solutions for specific recurrence-relations and application problems, yet only few publications deal with research towards parallel dynamic programming in general

The main goal of this thesis is to automatically parallelize DP-programs written in R. More specifically, our primary goal is to develop a tool which automatically recognizes structures of dynamic programming in R code and transforms them into parallel versions using data-parallel list skeletons.

Our tool is embedded into the ALCHEMY framework, which allows researchers to experiment with different parallelization techniques for R. A secondary goal of this thesis is to evaluate feasibility and performance of a known parallelization approach experimentally, using a set of dynamic programming R programs.