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.