The thesis we intend to demonstrate is that the automation of the inference process of providing explanations for performance phenomena in parallel programs is possible, and also desirable, since it facilitates both performance diagnosis and modeling.
There are many performance phenomena that require explanation, such as synchronization time, communication overhead, and memory stalls. We must start by identifying the relevant performance phenomena, and then develop techniques that explain them. Also, we must ensure that these techniques can be performed automatically.
Performance understanding techniques can use both dynamic and static information. Examples of dynamic information are execution timings and interactions among processes. Static information includes the location of performance phenomena (i.e., source code), the data structures accessed, and implementation decisions, such as the data distribution.
In order to facilitate the understanding of parallel programs, all this information (i.e., static, dynamic, and explanations) should be accessed easily and at various granularities. Thus, we also propose to integrate all the performance understanding techniques into a single framework that:
We implemented a first prototype of this framework, called Carnival, which is a performance measurement and visualization tool for SPMD message-passing programs. Carnival uses detailed event traces to gather performance information, which it presents both as global summary statistics and as localized performance profiles, facilitating top-down performance analysis. The user interface presents performance information with the source code, creating a link between the observed phenomena and the code. The Carnival framework is described in Chapter 3.
We developed a technique that explains synchronization times in parallel programs, which we call waiting times (WT). Waiting time (where one processor waits for another) arises from a variety of sources in parallel programs, including communication, synchronization, load imbalance, and resource contention. In order to understand waiting time we developed waiting time analysis, which uses traces of program executions to identify root causes of WT and automatically produces a characterization (both descriptive and analytical) for each source of waiting time in a parallel program. These characterizations suggest optimizations to the programmer that reduce parallel overheads and form a basis for performance models that capture the complex interactions among processors. Waiting time analysis is presented in detail in Chapter 4.
We also describe the Lost Cycles Toolkit (LCT), which provides support for generating performance models. LCT is an example of the importance of auxiliary tools in understanding the performance of parallel programs. LCT makes performance modeling accessible to parallel programmers by automating experimental design, performance measurement, modeling, and also providing feedback to the user on the quality of the resulting model.