CPA-CPL: Automatic Parallelization Using Semantic Commutativity Analysis

在几乎整个计算历史中，顺序计算速度的提高一直是计算能力增加的主要来源。顺序计算一次只执行一项任务。但计算领域现在遇到了基础计算基础上的基本限制，这些限制消除了这种性能改进的源泉。相反，该领域必须使用并行计算机，这些计算机通过同时执行多个任务来获得更高的性能。获得这些性能优势的一个关键挑战是开发能够正确协调同时执行的多个任务的活动的并行软件的难度。这项研究通过研究编译技术的开发来解决这一难题，该技术旨在将一次执行一项任务的顺序软件自动转换为同时自动执行多项任务的并行软件。研究重点是处理链接数据结构(如列表、图形和树)的现代面向对象计算。它建立在最近这些数据结构的验证实现的可用性的基础上，以推理更一般的抽象数据结构状态，而不是数据结构实现在运行时操纵的具体对象和引用。然后，开发人员可以使用抽象数据结构状态来指定任何并行计算必须满足的等价条件。预期的结果是，分析技术将能够使用等价条件来自动生成并行软件，该并行软件可以产生与相应的顺序软件不同但等价的结果。这种额外的自由度承诺将大大拓宽能够进行自动分析以实现更快并行执行的计算范围。

For virtually the entire history of computing, improvements in the speed of sequential computations, which execute only a single task at a time, have been the primary source of increased computing power. But the computing field is now encountering fundamental limits on the underlying computing substrate that eliminate this source of performance improvement. The field must instead work with parallel computers, which obtain increased performance by performing multiple tasks at the same time. A key challenge to obtaining these performance benefits is the difficulty of developing parallel software that can correctly coordinate the activities of multiple tasks that execute at the same time. The research addresses this difficulty by investigating the development of compilation techniques designed to automatically translate sequential software that performs a single task at a time into parallel software that automatically performs multiple tasks at the same time.The research focuses on modern object-oriented computations that manipulate linked data structures such as lists, graphs, and trees. It builds on the recent availability of verified implementations of these data structures to reason with the more general abstract data structure state as opposed to the concrete objects and references that the data structure implementations manipulate when they run. The developer can then use the abstract data structure state to specify an equivalence condition that any parallel computation must satisfy. The expected result is that the analysis techniques will be able to use the equivalence condition to automatically generate parallel software that may produce a different but equivalent result as the corresponding sequential software. This additional freedom promises to substantially broaden the range of computations that are amenable to automatic analysis for faster parallel execution.