DIMACS Princeton Colloquium Talk


Commutativity Analysis: A New Analysis Framework for Parallelizing Compilers


Martin Rinard
University of California, Santa Barbara


Room 402, Computer Science (CS) Bldg, 35 Olden St.
Princeton University, Princeton, NLJ


12:00 - 1:30 p.m.
Monday, September 23, 1996


Commutativity analysis is a new analysis framework designed to automatically parallelize object-oriented computations that manipulate pointer-based data structures. It differs from data dependence analysis in that it does not attempt to precisely determine which pieces of computation access which pieces of data. It instead views the computation as composed of operations on objects. It then analyzes the program 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. Even though this parallel code may violate the data dependences of the original serial program, it is guaranteed to generate the same result.

This talk presents the basic concepts behind commutativity analysis and discusses some extensions that we have found necessary for its practical application. It also presents performance results for two automatically parallelized computations running on the Stanford DASH machine. These results provide encouraging evidence that commutativity analysis may be able to serve as the basis for a successful parallelizing compiler.

Document last modified on September 20, 1996