Abstract
Commutativity Analysis: A New Technique for AutomaticallyParallelizing Serial Programs
by: Martin C. Rinard and Pedro Diniz
Abstract:
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.
Keywords:
parallelizing compilers, parallel computation, program analysis
Date:
September 1994
Document: 1994-16
