HAWKEYE: Effective Discovery of Dataflow Impediments to Parallelization.

Omer Tripp, Greta Yorsh, John Field, Mooly Sagiv

In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2011 (OOPSLA'11)

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 undertaking, 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 field-based 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.

Click here to access the paper: PDF.