Automatic Parallelization of Scheme Programs using Static Analysis

Scriptie/masterproef: Master's Thesis


Automatic parallelization is an attractive option in light of the current proliferation of multicore hard- ware. This dissertation presents a brute-force technique for the automatic parallelization of sequen- tial, higher-order Scheme programs containing side-effects. We will attempt to parallelize binding expressions inside nested let expressions by introducing a parallel let variant let||. To determine whether this is safe, we use dependency analysis. To facilitate the transformation to a parallel program, we can construct and transform a dependency graph.
If we want to determine dependencies between expressions in programs, we must analyze that program. Program analysis can be realized using abstract interpretation, because it provides a frame- work that allows us to collect information about a program without actually running it. The results produced by abstract interpretation are necessarily approximations because we are dealing with unde- cidable problems. Nevertheless our analyses are conservative and the results reflect all the possibilities that can arise at runtime.
In order to approximate dependencies that may arise when expressions invoke procedures in a higher-order program, we use the interprocedural dependence analysis by Might and Prabhu [19]to approximate dependencies that may arise when expressions invoke procedures in a higher-order pro- gram. The result of that analysis is an abstract resource dependency graph relating addresses and invocations. This information, together with the dependency information that is lexically apparent from the source code, allows us to determine whether it is safe to parallelize expressions in a program.
Our approach is brute-force in the sense that static analysis answers the safety question concerning parallelization, but we never investigate whether it is useful. We parallelize at every opportunity. To validate this approach and to see how it performs in practice, we ran several automatically parallelized benchmarks on parallel hardware. The evaluator we developed and use is Streme. It features paral- lelization primitives with intentional semantics. Our experimental results show that some programs with high levels of recursion indeed get a performance boost, while others do not or receive a perfor- mance penalty. The most promising future work comprises adding heuristics to guide the process of automatic parallelization.
Datum Prijs2010
BegeleiderTheo D'Hondt (Promotor) & Coen De Roover (Advisor)

Citeer dit