Obliterating Obstructions: Detecting Dependencies Disruptive to Parallelisation in Recursive Functions

Mr Adam Barwell, University of St Andrews

To take advantage of increasingly parallel hardware, a simple, safe, and effective method to introduce parallelism is needed. Current approaches can be divided into two broad categories: automatic, and abstraction. Whilst fully automatic solutions mean the programmer need not lift a finger, they tend to target highly specific constructs, rendering them virtually useless in all but a few situations. Conversely, the development of better abstractions and interfaces presents a more general solution, but still requires a level of expertise from the programmer to be effective. This is especially pronounced when a program must be transformed to enable the introduction of parallelism. To reduce the burden this transformation phase places on the proverbial programmer, we propose a method that uses static analysis techniques to identify operations within tail-recursive functions that are obstructive to the introduction of parallelism, and use refactoring techniques to extract and expose potential parallelism in spite of those obstructions.

*Bio*: Studying under Prof Kevin Hammond and Dr Christopher Brown, Adam is a PhD student at the University of St Andrews. He is currently interested in dependency analysis and program transformation techniques, principally to enable the introduction of parallelism to sequential programs. Having cut his teeth on Prolog and Miranda back at UCL, he currently has an odd fixation with Erlang, but is not above tinkering in Haskell or perpetually intending to play with Idris.