Automatic parallelization of object-oriented computations is becoming increasingly important with the widespread acceptance of object-oriented languages such as Java and C++, and the adoption of small-scale shared-memory multiprocessors as the mainstay of enterprise computing. A key problem that complicates the automatic parallelization of object-oriented programs is the pervasive use of irregular linked data structures such as lists, trees and graphs. The project will investigate a fundamentally new analysis technique, commutativity analysis, that is designed to automatically parallelize object- oriented computations that manipulate linked data structures. The project will focus on practical techniques such as the generation of self-tuning code, or code that dynamically changes its behavior to adapt to changes in the execution environment, and optimizations that reduce synchronization overhead. It will also investigate advanced analyses such as relative commutativity analysis, which enables the automatic parallelization of computations that build linked data structures, and replication analysis, which enables the dynamic replication of objects to eliminate serialization. The overall goal is to develop techniques that enable a dramatic reduction in the cost and difficulty of developing software for parallel machines. Educational contributions include the involvement of students in the research and the development of a new class in program analysis.***
