CPA-CPL: Automatic Parallelization Using Semantic Commutativity Analysis

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.