Report ID
1995-13
Report Authors
Martin Rinard and Pedro Diniz
Report Date
Abstract
This paper introduces a new analysis technique, commutativity analysis, forautomatically parallelizing programs written in a sequential, imperativeprogramming language. Existing parallelizing compilers preserve the datadependences of the original serial program. They analyze the program at thelevel of individual reads and writes to single words of memory to generateparallel code that preserves the relative order of reads and writes to the sameword. Commutativity analysis, on the other hand, 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. While the resulting parallel program mayviolate the data dependences of the original serial program, it is stillguaranteed to generate the same result. This paper presents commutativityanalysis and shows how to exploit the extracted information to automaticallygenerate parallel code.
Document
1995-13.ps193.57 KB