Finding large-grain parallelism in loops with serial control dependencies

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.