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:
@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
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
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
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
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
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
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:
Please cite as
References
The Theory of Parsing, Translation, and Compiling
Prentice-Hall, 1972
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
Dynamic programming parallel implementations for the knapsack problem
INRIA, 1993
Dynamic Programming
Princeton University Press, 1957
Programming parallel algorithms
Communications of the ACM 39, ACM, New York, NY, USA, March 1996
Parallel Dynamic Programming
Ph.D. thesis, Indiana University, 1994
The Parallel Evaluation of General Arithmetic Expressions
Journal of the ACM 21, ACM, New York, NY, USA, April 1974
Introduction to Algorithms
The MIT Press, 2009
Parallel algorithms for fast computation of normalized edit distances
Eighth IEEE Symposium on Parallel and Distributed Processing, IEEE, 1996
Parallelism in random access machines
Proceedings of the tenth annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1978
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
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Cambridge University Press, 1997
Parallele Algorithmen
Springer, 1983
On the parallel complexity of solving recurrence equations
Algorithms and Computation, Springer Berlin / Heidelberg, 1994
A complexity theory of efficient parallel algorithms
Theoretical Computer Science 71 (1), 1990
Java-Thread-Affinity
Open source project, 2012
Automatically Tuned Dynamic Programming with an Algorithm-by-Blocks
Parallel and Distributed Systems (ICPADS), 2010 IEEE 16th International Conference on, IEEE, dec. 2010
Couillard: Parallel Programming via Coarse-Grained Data-Flow Compilation
September 2011
Monotonicity and the principle of optimality
Journal of Mathematical Analysis and Applications 88 (2), 1982
Optimizing the parallel computation of linear recurrences using compact matrix representations
Journal of Parallel and Distributed Computing 69 (4), 2009
Parallel complexity theory
Pitman, 1987
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
On efficient parallel computations for some dynamic programming problems
Theoretical Computer Science 59 (3), 1988
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
Dynamic programming and principles of optimality
Journal of Mathematical Analysis and Applications 65 (3), 1978
Portable Parallel Branch-and-Bound Library: User Manual
University of Paderborn, 1996