Run-Time Parallelization and Scheduling of Loops. Revision
Abstract
This paper studies run-time methods to automatically parallelize and schedule iterations of a do loop in certain cases, where compile-time information is inadequate. The methods presented in this paper involve execution time preprocessing of the loop. At compile-time, these methods set up the framework for performing a loop dependency analysis. At run-time, wavefronts of concurrently executable loop iterations are identified. Using this wavefront information, loop iterations are reordered for increased parallelism. The authors utilize symbolic transformation rules to produce: (1) inspector procedures that perform execution time preprocessing and (2) executors or transformed versions of source code loop structures. These transformed loop structures carry out the calculations planned in the inspector procedures. They present performance results from experiments conducted on the Encore Multimax. These results illustrate that run-time reordering of loop indices can have a significant impact on performance. Furthermore, the overheads associated with this type of reordering are amortized when the loop is executed several times with the same dependency structure.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1990
- Accession Number
- ADA223323
Entities
People
- Joel H. Saltz
- Kay Crowley
- Ravi Mirchandaney