Commutativity Analysis: A New Technique for AutomaticallyParallelizing Serial Programs

This paper introduces a new analysis technique, commutativity analysis, forautomatically parallelizing programs written in sequential, imperativeprogramming languages. Commutativity analysis aggregates both data andcomputation into larger grain units. It then analyzes the computation at thisgranularity to discover when pieces of the computation commute (i.e. generatethe same 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 approach differs from standardapproaches based on data dependence analysis in that it generates parallelprograms that may violate the data dependences of the original serial program.Commutativity analysis can therefore automatically parallelize programs thatare inherently beyond the reach of any compiler that preserves the datadependences. In this paper we formally define a set of conditions that thecompiler can use to automatically detect commuting operations, prove that ifoperations meet these conditions then their executions commute and show how toexploit the commutativity information to automatically generate parallel code.