HAWKEYE: Effective Discovery of Dataflow Impediments to Parallelization
Abstract
Parallelization transformations are an important vehicle for
improving the performance and scalability of a software system. Utilizing concurrency requires that the developer first
identify a suitable parallelization scope: one that poses as a
performance bottleneck, and at the same time, exhibits considerable available parallelism. However, having identified a
candidate scope, the developer still needs to ensure the correctness of the transformation. This is a difficult underaking,
where a major source of complication lies in tracking down
sequential dependencies that inhibit parallelization and addressing them.
We report on HAWKEYE, a dynamic dependence-analysis
tool that is designed to assist programmers in pinpointing
such impediments to parallelization. In contrast with fieldbased dependence analyses, which track concrete memory
conflicts and thus suffer from a high rate of false reports,
HAWKEYE tracks dependencies induced by the abstract semantics of the data type while ignoring dependencing arising
solely from implementation artifacts. This enables a more
concise report, where the reported dependencies are more
likely to be real as well as intelligible to the programmer