Presents a symbolic analysis that characterizes the regions of memory accessed by procedures in divide and conquer C programs. The algorithm formulates the analysis problem as a system of symbolic inequality constraints, reduces the system of constraints to a linear program, then solves the linear program. The solution to the linear program provides symbolic bounds for the accessed memory regions. In conjunction with a pointer analysis for C programs, this analysis enables the compiler to automatically parallelize recursive divide and conquer programs that use pointers and pointer arithmetic to access dynamically allocated blocks of memory.
Uses pointer analysis and a variety of abstract interpretations to extract symbolic bounds for regions of accessed memory blocks. The results are used to automatically parallelize recursive divide and conquer programs.
Commutativity Analysis:
A New Analysis Framework for Parallelizing Compilers
Martin C. Rinard
Pedro C. Diniz
Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pp. 54-67
Philadelphia, Pennsylvania, May 1996
Presents a new analysis technique, commutativity analysis, for automatically parallelizing computations that manipulate dynamic, pointer-based data structures. Commutativity analysis views the computation as composed of operations on objects. It then analyzes the program at this granularity 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. We have used this system to automatically parallelize several complete scientific computations; the results provide evidence that commutativity analysis can serve as the basis for a successful parallelizing compiler.
Shows that commutativity analysis is sound.