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!


There are multiple versions of the thesis. All differences are cosmetic in nature; there are none in the content.

Download colored screen version
Screen version, colored
Download colored print version
Print version, colored
Download colorless screen version
Screen version, grayscale
Download colorless print version
Print version, grayscale
Automated Parallelisation of Dynamic Programming Recursions - Raphael Reitzig