Semantic Foundations of Commutativity Analysis

This paper presents the semantic foundations of commutativity analysis, ananalysis technique for automatically parallelizing programs written in asequential, imperative programming language. Commutativity analysis views thecomputation as composed of operations on objects. It then analyzes the programat this granularity to discover when operations commute (i.e. generate thesame result regardless of the order in which they execute). If all of theoperations required to perform a given computation commute, the compiler canautomatically generate parallel code.This paper shows that the basic analysis and tranformations that form thefoundation of the parallelization technique are sound. It also presentsperformance results from two automatically parallelized programs.