next up previous
Next: Cause-Effect Analysis Up: Cause-Effect Analysis of Parallel Previous: Cause-Effect Analysis of Parallel

Introduction

Many performance phenomena arise during execution of parallel programs that are due to the runtime environment or the precise order of events during execution. Examples of such phenomena include the amount of time spent waiting at a synchronization point, the frequency and time spent on shared data references, and the frequency of transaction aborts and retries. Since these phenomena cannot be predicted or analyzed statically, analysis techniques that seek to understand these phenomena are usually based on execution-time profiles or runtime traces of execution.

Performance debugging or tuning requires that we first identify phenomena that adversely affect performance, understand the cause of those phenomena, and modify the program to remove the cause. Although profiles and traces can be used to identify phenomena of interest, significant additional effort is required to find the causes of the phenomena or to identify appropriate program modifications. The inference process required to explain phenomena in terms of root causes (that is, implementation decisions) is particularly complex in cases where the phenomena of interest are created by events that are distant in both time and space.

There are many tools that help the programmer in assessing performance phenomena. The integration of Fortran D and Pablo [1] correlates static information (e.g., data dependences) and dynamic measurements. Paradyn [13] identifies both synchronization and shared-memory bottlenecks, and provides profiles and information about sharing patterns. MTool [4] and MemSpy [6] focus on memory operations, quantifying their influence on execution time and identifying the relevant portions of code and data structures. Although all of these tools give some insight into the causes of performance phenomena, the programmer is still responsible for the inference process that leads from observed effects to root causes.

Some tools focus on a limited form of causality information. StormWatch [3] is a visualization tool for memory system protocols that captures relationships between individual memory events, thus exposing causality in memory operations. Another tool, a performance debugger implemented by Rajamony and Cox [10], automatically detects unnecessary and excessive synchronization by verifying data accesses between synchronization intervals.

In this paper we introduce a general framework for automating the inference process that relates observed performance phenomena to underlying causes, which we call cause-effect analysis. This framework, which has been implemented in the Carnival performance visualization tool [7], uses performance profiles to quantify classes of phenomena (such as idle cycles, communication overhead, and load imbalance) and abstractions of execution traces to explain them. The output of this process is a compact representation (in terms of execution events) and an appropriate visualization for the cause of each phenomenon (in terms of the source code).

Many different types of phenomena can be analyzed using this framework, and we describe three of them in this paper: (1) idle time due to synchronization, (2) protocol operations in a software distributed shared memory system, and (3) transaction aborts. We describe the implementation of each of these analysis techniques, and present examples of the application of the techniques.

   figure71
Figure: Carnival profiles for SOR - The main window at the top contains the source code (with line numbers) on the right; information about each scope in the source code appears on the left. The line numbers are presented in grey scale, where the intensity of the scale represents the percentage of execution time (summed across all processors) spent on a given line of source code. The color bars on the far left are operation profiles, where the color indicates the operation (with a key at the top of the window), and the width indicates duration. The bottom window contains a map of all waiting time in the program. The left number is the percentage of all waiting time produced by that line of code, the color bar indicates the operation type that resulted in waiting time, and the remaining columns indicate the line number, basic block, and operation identifier. At the bottom are color-coded boxes for each explanation for waiting time at line 20 (Barrier_0_odd_1); the first explanation covers 96% of the waiting time that occurs at this barrier, and is attributed to load imbalance (LI).


next up previous
Next: Cause-Effect Analysis Up: Cause-Effect Analysis of Parallel Previous: Cause-Effect Analysis of Parallel

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