Automatic parallelization of "inherently" sequential nested loop programs
Date
2011
Authors
Zou, Yun, author
Rajopadhye, Sanjay, advisor
Strout, Michelle, committee member
Bohm, A. P. Willem, committee member
Breidt, F. Jay, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
Most automatic parallelizers are based on detection of independent operations, and most of them cannot do anything if there is a true dependence between operations. However, there exists a class of programs for which this can be surmounted based on the nature of the operations. The standard and obvious cases are reductions and scans, which normally occur within loops. Existing work that deals with complicated reductions and scans normally focuses on the formalism, not the implementation. To help eliminate the gap between the formalism and implementation, we present a method for automatically parallelizing such "inherently" sequential programs. Our method is based on exact dependence analysis in the polyhedral model, and we formulate the problem as a detection that the loop body performs a computation that is equivalent to a matrix multiplication over a semiring. It handles both a single loop as well as arbitrarily nested loops. We also deal with mutually dependent variables in the loop. Our scan detection is implemented in a polyhedral program transformation and code generation system (AlphaZ) and used to generate OpenMP code. We also present optimization strategies to help improve the performance of the generated code. Experiments on examples demonstrate the scalability of programs parallelized by our implementation.
Description
Rights Access
Subject
scan and reduction
recurrence equations
semiring
automatic parallelization
polyhedral model