Commutativity Analysis: A New Framework for
Parallelizing Compilers
Martin Rinard and Pedro Diniz
Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110
Abstract
This paper presents a new analysis technique, commutativity analysis, for
automatically parallelizing computations that manipulate dynamic, pointer-based
data structures. 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 final 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.
We have implemented a prototype compilation system that uses commutativity analysis
as its primary analysis framework. We have used this system to automatically
parallelize two complete scientific computations: the Barnes-Hut N-body solver
and the Water code. This paper presents performance results for the generated
parallel code running on the Stanford DASH machine. These results provide
encouraging evidence that commutativity analysis can serve as the basis for
a successful parallelizing compiler.