PPoPP 2008 - Extracting Coarse-Grain Parallelism in General-Purpose Programs

Extracting Coarse-Grain Parallelism in General-Purpose Programs (poster presentation)

Sean Rul, Hans Vandierendonck and Koen De Bosschere

The 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2008)
Salt Lake City, Utah, February 20-23, 2008

Abstract

The success of CMPs and many-core processors hinges on the parallelizability of complex general-purpose programs. We present techniques to detect coarse-grain function-level parallelism in general-purpose programs that can be exploited on CMPs.

We use profile-driven control and data dependence analysis to overcome limitations in static analysis. Dependencies are measured between large regions of code, leading, in practice, to a correct analysis. Nonetheless, manual verification or thread-level speculation systems are needed to guarantee correct execution.

DO-ACROSS parallelism is identified by analyzing the dependences between code regions. Interdependent code regions are recursively merged until the overall loop structure matches a preset template. This template is then used to steer parallelization and to privatize data structures when necessary.

Application of our technique to the MiBench and SPEC CPU2000 benchmarks shows that the profile-based analysis is correct. Significant amounts of outer-loop parallelism are found and lead to a speedup of 5.45 for bzip2 compression on a 32-thread Sun Niagara CMP.

START Conference Manager (V2.54.5)