This paper presents a new analysis technique, commutativity analysis,
for automatically parallelizing computations that manipulate dynamic,
pointer-based data structures. Commutativity analysis views the comput
ation as composed of operations on objects. It then analyzes the progr
am at this granularity to discover when operations commute (i.e. gener
ate the same final result regardless of the order in which they execut
e). If all of the operations required to perform a given computation c
ommute, the compiler can automatically generate parallel code. We have
implemented a prototype compilation system that uses commutativity an
alysis as its primary analysis framework. We have used this system to
automatically parallelize two complete scientific computations: the Ba
rnes-Hut N-body solver and the Water code. This paper presents perform
ance results for the generated parallel code running on the Stanford D
ASH machine. These results provide encouraging evidence that commutati
vity analysis can serve as the basis for a successful parallelizing co
mpiler.