Cause-Effect Analysis of Parallel Programs


Cause-effect analysis encompasses a range of techniques that each seek to explain the occurrence of a class of local events or states in terms of events that occurred earlier in the execution. One example of a local state is ``the processor is waiting at a synchronization point'', and the corresponding explanation might describe the execution path of the other synchronizing processor. An example of a local event is ``page fault on page P'' in a DSM system, and the corresponding explanation might describe the series of reads and writes that led to an earlier invalidation, causing the page to be removed from local memory. In each case, there is a specific class of phenomena under study (e.g., idle processor cycles or page faults), whose explanation are in terms of events that preceded the observed phenomena in the execution.

Of course not all events that occur earlier in time are relevant to a particular observed phenomenon. For example, when we are analyzing one class of phenomena (such as aborted transactions), we need only consider events related to that class, and can safely ignore other event types, (such as intermediate computational steps). Also, we need not consider all events related to a given class that preceded the observed phenomenon; typically there is a bounded region of events that can cause a particular effect. For example, in the case of a loop containing barrier synchronization, the time spent waiting at the barrier during one iteration does not depend on events that took place during previous iterations. Similarly, once a page is loaded into local memory, we can safely ignore prior page faults or invalidations when attempting to explain why the page must be reloaded at some future time. In most cases, explanations for performance phenomena are based on a subset of event types within a small, bounded region of the execution.

Typically we focus on one class of phenomena at a time, and seek to understand the entire class. Thus, rather than explain (e.g.) the time spent waiting at a barrier during a single iteration of a loop, we would like to characterize the total amount of time spent waiting at a barrier across the entire execution. Such a characterization can be constructed incrementally by combining the explanations for each individual occurrence of waiting time at the barrier. Our general approach is to create explanations for individual performance phenomena, and then combine explanations for all phenomena that occur at a single location in the source code into a single explanation for that class of phenomena.

There is no single correct explanation for an observed phenomenon; explanations may differ based on the level of detail desired or the programmer insight needed to correct a problem. For example, if two processors repeatedly execute loop iterations and then synchronize at a barrier, the explanation for waiting time on the part of one processor could take several forms. One could simply describe the code that is executed by one processor while the other waits. In this case, the explanation answers the following question: what is one processor doing that prevents it from reaching the barrier while the other waits? Although valid as an explanation of waiting time, this particular explanation may not be helpful, since it will often describe the last thing a processor does before reaching a barrier, and not the part of its execution that caused it to lag behind other processors. Our implementation of waiting time analysis provides a different form of explanation, because it focuses on a different question: how did the execution paths of these two processors differ since the last time they synchronized such that one processor arrived at the barrier before the other? This explanation would identify sources of load imbalance within a loop as the cause of waiting time, rather than another part of the computation that happened to occur while another processor was idle. Our framework is designed to support any definition of cause that can be inferred from an event trace, but it must be recognized that some concepts of cause are more enlightening than others.

With this background, we can now describe our framework for cause-effect analysis more precisely. We first execute the parallel program under study, and collect a detailed trace of the program's execution. Events of interest include computational steps (basic blocks), synchronization operations, communication events, system calls, and any other significant activity that occurs during execution. Each event record in the trace file contains an event type, the processor id, a static scope identifier, and a global timestamp, which may be based on physical or logical clocks. The trace file is used to construct execution-time profiles that help the programmer to identify sources of inefficiency. Based on an analysis of the profiles, the programmer may select one or more cause-effect analysis techniques to be applied to the trace file.

For a given analysis technique (such as waiting time analysis or protocol analysis), we perform the following steps: (1) remove irrelevant events from the trace file using a filter that is specific to the class of phenomena under study, (2) identify events or states that correspond to phenomena to be explained, and produce an explanation for each one in terms of events, (3) simplify (as appropriate) the explanations for each individual instance of a performance phenomena, (4) combine explanations for phenomena that occur at the same place, and (5) create visualizations for the resulting explanations

Our visualizations are created using Carnival, a tool under development at Rochester that supports hierarchical abstraction in the presentation of performance data, maintains links between dynamic measurements and the source code, and provides visualization of cause-effect explanations of performance phenomena.

There are many performance phenomena that can be analyzed using this general framework. Up to now, we have studied three of them: waiting time at synchronization points ( Waiting time analysis ), page faults in a software DSM system ( Communication analysis ), and transaction aborts in a parallel file system ( Transaction analysis ).

The implementation of Carnival has been an ongoing project for more than an year. Currently Carnival comprises about 45000 lines of C and TCL/TK code. We have implemented program tracing for message-passing programs on the IBM SP2, shared-memory programs on the SGI Challenge, Treadmarks programs on clusters of DEC Alphas connected by the DEC Memory Channel, and PVM programs on a network of workstations.

About two thirds of the Carnival code (or 30000 lines) is devoted to the user interface and profile generation. Of the 15000 lines devoted to cause-effect analysis, roughly one half are common to all the techniques (and are encapsulated in a library), with the remaining 7500 lines divided roughly equally among the three techniques we've implemented. We believe that additional techniques can be added easily to our framework, and expect each such technique to require about 2000-3000 lines of code to implement.

Our experiences to date suggest that cause-effect analysis can be extremely useful during performance tuning, and that additional techniques can be added to our infrastructure without too much effort. We plan to continue to develop new analysis techniques and add them to Carnival, and apply our current techniques to more applications.


Publications

Wagner Meira, Jr. Parallel Performance Understanding via Integration of Modeling and Diagnosis Thesis Proposal, University of Rochester, Rochester, NY, 1996.

Wagner Meira, Jr., Thomas J. LeBlanc, and Alexandros Poulos Waiting Time Analysis and Performance Visualization in Carnival Proceedings of the First SIGMETRICS Symposium on Parallel and Distributed Tools , May, 1996, Philadelphia, PA, Pages 1-10.

Wagner Meira, Jr., Thomas J. LeBlanc, Nikolaos Hardavellas and Claudio Amorim Understanding the Performance of DSM Applications Proceedings of the Workshop on Communication and Architectural Support for Network-based Parallel Computing (CANPC' 97), San Antonio, TX, February 1997

Wagner Meira, Jr. and Thomas J. LeBlanc Cause-Effect Analysis of Parallel Program Performance Submitted for publication


Wagner Meira
Thu Jan 9 14:27:55 EST 1997