## Automated Parallelisation of Dynamic Programming Recursions

Please refer to the new website in the future. This site may go away.

This thesis discusses whether and how dynamic programming recursions can be computed in parallel such that compilers can parallelise them automatically. We discover that under certain assumptions which permit a rich class of dynamic programming recursions, two kinds of recursions can be computed in parallel while others can not. For those which can, we design and analyse efficient parallel algorithms theoretically. We then implement several prototypes and investigate their performance empirically. Finally, we integrate automatic application of the developed algorithms into a real-world compiler.

 Screen version, colored Print version, colored Screen version, grayscale Print version, grayscale

The black and white versions have different graphics that ensure readability on monochromatic displays, printed in grayscale and for individuals with color perception disabilities. The grayscale screen version works also well on ereaders; you might want to remove the margins for a better experience, though, for example with BRISS. Partial sources can be made available upon request.

Download the source code and data used in the making of this thesis:

@mastersthesis{Reitzig2012,
author = {Raphael Reitzig},
title  = {Automated Parallelisation of Dynamic Programming Recursions},
school = {University of Kaiserslautern},
year   = {2012},
url    = {/pub/mathesis}
}

#### References

• Alfred V. Aho, Jeffrey D. Ullman
The Theory of Parsing, Translation, and Compiling
Prentice-Hall, 1972
• Carlos E. R. Alves, Edson Cáceres, Frank K. H. A. Dehne, Siang W. Song
A Parallel Wavefront Algorithm for Efficient Biological Sequence Comparison
Proceedings of the 2003 international conference on Computational science and its applications, Springer-Verlag Berlin, Heidelberg, 2003
• Rumen Andonov, Fréedéeric Raimbault, Patrice Quinton
Dynamic programming parallel implementations for the knapsack problem
INRIA, 1993
• Richard Bellman
Dynamic Programming
Princeton University Press, 1957
• Guy E. Blelloch
Programming parallel algorithms
Communications of the ACM 39, ACM, New York, NY, USA, March 1996
Parallel Dynamic Programming
Ph.D. thesis, Indiana University, 1994
• Richard P. Brent
The Parallel Evaluation of General Arithmetic Expressions
Journal of the ACM 21, ACM, New York, NY, USA, April 1974
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduction to Algorithms
The MIT Press, 2009
• Ömer Eğecioğlu, Maximilian Ibel
Parallel algorithms for fast computation of normalized edit distances
Eighth IEEE Symposium on Parallel and Distributed Processing, IEEE, 1996
• Steven Fortune, James Wyllie
Parallelism in random access machines
Proceedings of the tenth annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1978
• Matteo Frigo, Charles E. Leiserson, Keith H. Randall
The implementation of the Cilk-5 multithreaded language
Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, ACM, New York, NY, USA, 1998
• Dan Gusfield
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Cambridge University Press, 1997
• Friedel Hoßfeld
Parallele Algorithmen
Springer, 1983
• Oscar Ibarra, Nicholas Trân
On the parallel complexity of solving recurrence equations
Algorithms and Computation, Springer Berlin / Heidelberg, 1994
• Clyde P. Kruskal, Larry Rudolph, Marc Snir
A complexity theory of efficient parallel algorithms
Theoretical Computer Science 71 (1), 1990
• Peter Lawrey
Open source project, 2012
• Jiajia Li, Guangming Tan, Mingyu Chen
Automatically Tuned Dynamic Programming with an Algorithm-by-Blocks
Parallel and Distributed Systems (ICPADS), 2010 IEEE 16th International Conference on, IEEE, dec. 2010
• Leandro A. J. Marzulo, Tiago A. O. Alves, Felipe M. G. França, Vítor Santos Costa
Couillard: Parallel Programming via Coarse-Grained Data-Flow Compilation
September 2011
• Thomas L Morin
Monotonicity and the principle of optimality
Journal of Mathematical Analysis and Applications 88 (2), 1982
• Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, Nicolae Tapus
Optimizing the parallel computation of linear recurrences using compact matrix representations
Journal of Parallel and Distributed Computing 69 (4), 2009
• Ian Parberry
Parallel complexity theory
Pitman, 1987
• Yewen Pu, Rastislav Bodik, Saurabh Srivastava
Synthesis of first-order dynamic programming algorithms
Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications, ACM, New York, NY, USA, 2011
Automatic parallelization of divide and conquer algorithms
SIGPLAN Not. 34 (8), ACM, New York, NY, USA, may 1999
• Wojciech Rytter
On efficient parallel computations for some dynamic programming problems
Theoretical Computer Science 59 (3), 1988
• Georg Sauthoff, Stefan Janssen, Robert Giegerich
Bellman’s GAP - A Declarative Language for Dynamic Programming
Proceedings of 13th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, ACM, 2011
• Moshe Sniedovich
Dynamic programming and principles of optimality
Journal of Mathematical Analysis and Applications 65 (3), 1978
• Stefan Tschöke, Thomas Polzer
Portable Parallel Branch-and-Bound Library: User Manual