Authors: Lawrence Rauchwerger, Nancy M. Amato, David A. Padua

Venue: Proceedings of the 9th International Conference on Supercomputing
DOI: 10.1145/224538.224553
Link to Publication

Abstract:
"In this paper we give a new run-time technique for finding an optimal parallel execution schedule for a partially parallel loop, i.e., a loop whose parallelization requires synchronization to ensure that the iterations are executed in the correct order. Given the original loop, the compiler generates inspector code that performs run-time preprocessing of the loop’s access pattern, and scheduler code that schedules (and executes) the loop iterations. The inspector is fully parallel, uses no synchronization, and can be applied to any loop. In addition, it can implement at run-time the two most effective transformations for increasing the amount of parallelism in a loop: array privatization and reduction parallelizatiort (element–wise). We also describe a new scheme for constructing an optimal parallel execution schedule for the iterations of the loop." 

@inproceedings{Rauchwerger-rmfppp-1995, 
 address = {New York, NY, USA}, 
 author = {Rauchwerger, Lawrence and Amato, Nancy M. and Padua, David A.}, 
 booktitle = {Proceedings of the 9th International Conference on Supercomputing}, 
 doi = {10.1145/224538.224553}, 
 isbn = {0897917286}, 
 location = {Barcelona, Spain}, 
 numpages = {10}, 
 pages = {137–146}, 
 publisher = {Association for Computing Machinery}, 
 series = {ICS '95}, 
 title = {Run-Time Methods for Parallelizing Partially Parallel Loops}, 
 url = {https://doi.org/10.1145/224538.224553}, 
 year = {1995} 
}