Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110
Abstract
This paper presents the semantic foundations of commutativity
analysis, an analysis technique for automatically parallelizing
programs written in a sequential, imperative programming language.
Commutativity analysis views the computation as composed of
operations on objects. It then analyzes the program at this
granularity to discover when operations commute (i.e. generate
the same result regardless of the order in which they execute).
If all of the operations required to perform a given computation
commute, the compiler can automatically generate parallel code.
This paper shows that the basic analysis technique is sound.
We have implemented a parallelizing compiler that uses commutativity
analysis as its basic analysis technique; this paper also presents
performance results from two automatically parallelized applications.