Commutativity Analysis: A New Analysis Framework for ParallelizingCompilers

This paper presents a new analysis technique, commutativity analysis, forautomatically parallelizing computations that manipulate dynamic, pointer-baseddata structures. Commutativity analysis views the computation as composed ofoperations on objects. It then analyzes the program at this granularity todiscover when operations commute (i.e. generate the same final resultregardless of the order in which they execute). If all of the operationsrequired to perform a given computation commute, the compiler can automaticallygenerate parallel code.We have implemented a prototype compilation system that uses commutativityanalysis as its primary analysis framework. We have used this system toautomatically parallelize two complete scientific computations: the Barnes-HutN-body solver and the Water code. This paper presents performance results forthe generated parallel code running on the Stanford DASH machine. Theseresults provide encouraging evidence that commutativity analysis can serve asthe basis for a successful parallelizing compiler.