Serializing Parallel Programs by Removing Redundant Computation
Marina Ernst · 1994
Programs often exhibit more parallelism than is actually available in the target architecture. This thesis introduces and evaluates three methods -- loop unrolling, loop common expression elimination, and loop differencing -- for automatically transforming a parallel algorithm into a less parallel one that takes advantage of only the parallelism available at run time. The resulting program performs less computation to produce its results; the running time is not just improved via second-order effects such as improving use of the memory hierarchy or reducing overhead (such optimizations can further improve performance). The asymptotic complexity is not usually reduced, but the constant factors can be lowered significantly, often by a factor of 4 or more. The basis for these methods is the detection of loop common expressions, or common subexpressions in different iterations of a parallel loop. The loop differencing method also permits computation of just the change in an expression from iteration to iteration.