Run-Time Parallelization and Scheduling of Loops
Abstract
This paper extends the class of problems that can be effectively compiled by parallelizing compilers. This is accomplished with the doconsider construct which would allow these compilers to parallelize many problems in which substantial loop-level parallelism is available but cannot be detected by standard compile-time analysis. The authors describe the experimentally analyze mechanisms used to parallelize the work required for these types of loops. In each of these methods, a new loop structure is produced by modifying the loop to be parallelized. Also presented are the rules by which these loop transformations may be automated in order that they be included in language compilers. The main application area of our research involves problems in scientific computations and engineering. The workload used in the experiments includes a mixture of real problems as well as synthetically generated inputs. From extensive tests on the Encore Multimax/320, the authors have reached the conclusion that for the types of workloads we have investigated, self-execution almost always performs better than pre-scheduling. Further, the improvement in performance that accrues as a result of global topological sorting of indices as opposed to the less expensive local sorting, is not very significant in the case of self-execution.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA203950
Entities
People
- Dough Baxter
- Joel H. Saltz
- Ravi Mirchandaney
Organizations
- Yale University