Abstract
Semantic Foundations of Commutativity Analysis
by: Martin Rinard and Pedro Diniz
Abstract:
This paper presents the semantic foundations of commutativity analysis, ananalysis technique for automatically parallelizing programs written in asequential, imperative programming language. Commutativity analysis views thecomputation as composed of operations on objects. It then analyzes the programat this granularity to discover when operations commute (i.e. generate thesame result regardless of the order in which they execute). If all of theoperations required to perform a given computation commute, the compiler canautomatically generate parallel code.This paper shows that the basic analysis and tranformations that form thefoundation of the parallelization technique are sound. It also presentsperformance results from two automatically parallelized programs.
Keywords:
parallelizing compilers, parallel computation, commutativityanalysis, semantics
Date:
May 29, 1996
Document: 1996-09
