Embla - Data Dependence Profiling for Parallel Programming

With the proliferation of multicore processors, there is an urgent need for tools and methodologies supporting paral-lelization of existing applications. In this paper, we present a novel tool for aiding programmers in parallelizing pro-grams. The tool, Embla, is based on the Valgrind frame-work, and allows the user to discover the data dependences in a sequential program, thereby exposing opportunities for parallelization. Embla performs an off-line dynamic analy-sis, and records dependences as they arise during program execution. It reports an optimistic view of parallelizable se-quences, and ignores dependences that do not arise during execution. Moreover, since the tool instruments the machine code of the program, it is largely language independent. Since Embla finds the dependencies that occur for par-ticular executions, the confidence one would assign to its re-sults depend on whether different executions yield different (bad) or largely the same (good) dependencies. We present a preliminary investigation into this issue using 84 different inputs to the SPEC CPU2006 benchmark 403.gcc. The re-sults indicate that there is a strong correlation between cov-erage and finding dependencies; executing the entire pro-gram is likely to reveal all dependencies.