TY - JOUR
T1 - Finding large-grain parallelism in loops with serial control dependencies
AU - Dietz, Henry G.
PY - 1988
Y1 - 1988
N2 - An automatic parallelization technique, control precomputation is discussed, whereby arbitrary sequential loops, including those with serializing control dependencies (i.e., general while loops) and/or irreducible flow graphs, may be transformed to permit relatively large-grain asynchronous parallel execution. The basic concept is for the compiler to isolate inherently sequential operations from the remainder of the loop, thereby enabling the remaining operations to be parallelized. Since there is a cost associated with splitting loops, not all loops can be profitably parallelized in this way. Compared to pipelining, however, this technique effectively reduces synchronization overhead by grouping high-frequency synchronization points within a single process; the reduction in synchronization overhead is approximately proportional to the parallelism width of the machine.
AB - An automatic parallelization technique, control precomputation is discussed, whereby arbitrary sequential loops, including those with serializing control dependencies (i.e., general while loops) and/or irreducible flow graphs, may be transformed to permit relatively large-grain asynchronous parallel execution. The basic concept is for the compiler to isolate inherently sequential operations from the remainder of the loop, thereby enabling the remaining operations to be parallelized. Since there is a cost associated with splitting loops, not all loops can be profitably parallelized in this way. Compared to pipelining, however, this technique effectively reduces synchronization overhead by grouping high-frequency synchronization points within a single process; the reduction in synchronization overhead is approximately proportional to the parallelism width of the machine.
UR - http://www.scopus.com/inward/record.url?scp=0024138053&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024138053&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0024138053
SN - 0190-3918
VL - 2
SP - 114
EP - 121
JO - Proceedings of the International Conference on Parallel Processing
JF - Proceedings of the International Conference on Parallel Processing
ER -