Surveys research in the analysis of multithreaded programs. Identifies two classes of multithreaded programs, parallel computing programs and activity management programs, and discusses analyses that are appropriate for each class. Also discusses issues associated with weak memory consistency models and multithreading.
Presents a combined pointer and escape analysis for Java programs with unstructured multithreading. The algorithm analyzes interactions between threads to obtain precise points-to and escape information for objects accessible to multiple threads. The results are used for synchronization elimination and elimination of dynamic checks associated with the use of region-based memory allocation.
Presents a symbolic analysis that characterizes the regions of memory accessed by procedures in multithreaded Cilk programs. In conjunction with a pointer analysis for multithreaded Cilk programs, this analysis enables the compiler to verify the absence of data races and array bounds violations in multithreaded divide and conquer programs with recursively generated concurrency that use pointers and pointer arithmetic to access dynamically allocated blocks of memory. The results have also been used to automatically parallelize sequential divide and conquer C programs with the same features.
Presents a pointer analysis for Cilk programs with structured, cobegin/coend multithreading. The algorithm analyzes interactions between threads to obtain precise points-to information for pointers accessed and updated by multiple threads. The algorithm handles the full range of constructs in Cilk programs, including pointer arithmetic and recursively generated concurrency.
Synchronization Transformations for Parallel Computing
Pedro C. Diniz and Martin C. Rinard
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of
Programming Languages, pp. 187-200
Paris, France January 1997
Presents an algorithm that moves lock acquire and release operations through multithreaded programs. Adjacent acquire and release operations cancel, reducing the synchronization frequency and overhead.