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.

Download


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:

GPL3

Please cite as

@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
  • Phillip Gnassi Bradford
    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
    Java-Thread-Affinity
    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
  • Radu Rugina, Martin Rinard
    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
    University of Paderborn, 1996