Commutativity analysis

• DOI: 10.1145/231379.231390
• Publication Date: 2003-11-14T16:24:15Z
• Authors: Martin C. Rinard; Pedro C. Diniz
• Keywords: Granularity; Automatic parallelization

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