The role of associativity and commutativity in the detection and transformation of loop-level parallelism
William M. Pottenger · 1998
The study of theoretical and practical issues in automatic parallelization across application and language boundaries is an appropriate and timely task. In this paper, we discuss theory and techniques that wehave determined useful in parallelizing recurrences and reductions in computer programs. We present a framework for understanding such parallelism based on an approachwhich models loop bodies as coalescing loop operators. Within this framework we distinguish between associative coalescing loop operators and associative and commutative coalescing loop operators. We present the result of the application of this theory in a case study of a modern C++ semantic retrieval application drawn from the digital library field.