Communication-Sensitive Static Dataflow for Message Passing Applications

Опубликовано 6 сентября 2016, 18:00

Message passing is a very popular style of parallel programming, used in a wide variety of applications and supported by many APIs, such as BSD sockets, MPI and PVM. It's importance has motivated significant amounts of research on optimization and debugging techniques for such applications. Although this work has produced impressive results, it has also failed to fulfill its full potential. The reason is that while prior work has focused on runtime techniques, there has been very little on compiler analyses that understand the properties of parallel message passing applications and use this information to improve application performance and debuggers quality. In this talk I present a novel compiler analysis framework that extends dataflow to parallel message passing applications on arbitrary numbers of processes. It works on an extended control-flow graph that includes all the possible inter-process interactions of any numbers of processes. This enables dataflow analyses built on top of this framework to incorporate information about the application's parallel behavior and communication topology. The overall parallel dataflow framework can be instantiated with a variety of specific dataflow analyses as well as abstractions that can tune the cost/accuracy of detecting the application's communication topology. The proposed framework bridges the gap between prior work on parallel runtime systems and sequential dataflow analyses, enabling new transformations, runtime optimizations and bug detection tools that require knowledge of the application's communication topology. The framework has been instantiated with two different symbolic analyses that can detect different types of communication patterns, enabling dataflow analyses on a wide variety of real applications.