COMMUTATIVITY ANALYSIS - A NEW ANALYSIS TECHNIQUE FOR PARALLELIZING COMPILERS

This article presents a new analysis technique, commutativity analysis , for automatically parallelizing computations that manipulate dynamic , pointer-based data structures. Commutativity analysis views the comp utation as composed of operations on objects. It then analyzes the pro gram at this granularity to discover when operations commute (i.e., ge nerate the same final result regardless of the order in which they exe cute). If all of the operations required to perform a given computatio n commute, the compiler can automatically generate parallel code. We h ave implemented a prototype compilation system that uses commutativity analysis as its primary analysis technique. We have used this system to automatically parallelize three complete scientific computations: t he Barnes-Hut N-body solver, the Water liquid simulation code, and the String seismic simulation code. This article presents performance res ults for the generated parallel code running on the Stanford DASH mach ine. These results provide encouraging evidence that commutativity ana lysis can serve as the basis for a successful parallelizing compiler.