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

Venue: International Journal of Parallel Programming
DOI: 10.1007/BF02577866
Link to Publication

Abstract:
"Current parallelizing compilers do a reasonable job of extracting parallelism from programs with regular, well behaved, statically analyzable access patterns. However, they cannot extract a significant fraction of the available, parallelism if the program has a complex and/or statically insufficiently defined access pattern, e.g., simulation programs with irregular domains and/or dynamically changing interactions. Since such programs represent a large fraction of all applications, techniques are needed for extracting their inherent parallelism at run-time. 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 perform as run-time preprocessing of the loop's access pattern, and scheduler code that schedules (and executes) the loop interations. The inspector is fully parallel, uses no sychronization, and can be applied to any loop (from which an inspector can be extracted). 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 parallelization (elementwise). The ability to identify privatizable and reduction variables is very powerful since it eliminates the data dependences involving these variables and" 

@article{Rauchwerger-asmfrl-1995, 
 author = {Rauchwerger, Lawrence and Amato, Nancy M. and Padua, David A.}, 
 bdsk-url-1 = {https://doi.org/10.1007/BF02577866}, 
 da = {1995/12/01}, 
 date-added = {2020-11-02 22:20:42 -0600}, 
 date-modified = {2020-11-02 22:20:42 -0600}, 
 doi = {10.1007/BF02577866}, 
 id = {Rauchwerger1995}, 
 isbn = {1573-7640}, 
 journal = {International Journal of Parallel Programming}, 
 number = {6}, 
 pages = {537--576}, 
 title = {A scalable method for run-time loop parallelization}, 
 ty = {JOUR}, 
 url = {https://doi.org/10.1007/BF02577866}, 
 volume = {23}, 
 year = {1995} 
}