Reitzig, Raphael
Automated Parallelisation of Dynamic Programming Recursions
Master’s thesis,
2012
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.
You can download all benchmark data that was used in the thesis here. All code used in making the thesis is available on Github; there is one repository for the Java prototypes and one for the Scala compiler plugin.
You have a machine on which you think the algorithms would behave differently? Please run your own benchmarks and let us know!
Download
There are multiple versions of the thesis. All differences are cosmetic in nature; there are none in the content.
Screen version, colored |
Print version, colored |
Screen version, grayscale |
Print version, grayscale |
-
Print versions use a two-sided layout whereas screen versions have highlighted links within the document.
-
The grayscale versions have different graphics and color settings in order to improve readability on monochromatic displays, printed in grayscale and for individuals with color-perception disabilities.