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