CAREER: Commutativity Analysis: A New Analysis Framework for Automatically Parallelizing Object-Oriented Computations

随着面向对象语言（如Java和C++）的广泛接受，以及小规模共享内存多处理器作为企业计算支柱的采用，面向对象计算的自动并行化变得越来越重要。使面向对象程序的自动并行化复杂化的一个关键问题是不规则链接数据结构（如列表、树和图）的普遍使用。该项目将研究一种全新的分析技术，交换性分析，旨在自动并行化操纵链接数据结构的面向对象计算。 该项目将专注于实用技术，例如自调优代码的生成，或动态更改其行为以适应执行环境变化的代码，以及减少同步开销的优化。它还将调查先进的分析，如相对交换性分析，使自动并行计算，建立链接的数据结构，和复制分析，使对象的动态复制，以消除串行化。总体目标是开发技术，使并行机软件开发的成本和难度显着降低。 教育贡献包括学生参与研究和开发程序分析的新课程。

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.***