next up previous
Next: Examples of Waiting Time Up: Waiting Time Analysis and Previous: Implementation of Waiting Time

Visualization with Carnival

 

Carnival presents performance profiles and waiting time analysis in the context of the source code. It helps the user quickly identify where in the source code a program spends the majority of its execution time, and where in the code important sources of parallel overhead are introduced.

The primary Carnival display window (Figure 5a) is divided into two parts. The source code (with line numbers) is presented on the right; information about each scope in the source code appears on the left. The line numbers are presented in a 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. Users can quickly identify places in the code where the most time is spent by scrolling down the line numbers looking for the darkest portion of the scale.

The left side of the display identifies the scopes in the program. A scope can be a loop, a subroutine, a block of code identified as parallel overhead, a block of code identified as computation, or the whole program. A scope is uniquely characterized by the line numbers at the beginning and end of the scope. A grey scale bar is drawn from the beginning to the end of every scope; the intensity of the scale indicates the cumulative execution time (across all processors) spent in that scope. Unlike the grey scale used for line numbers, this scale includes the time spent in nested scopes; therefore, the outermost scope always has the darkest bar. Clicking on the vertical bar for a scope produces the per-processor percentage of the scope's execution time in a pop-up window (Figure 5c). In order to facilitate the navigation in the main window, a Profile Map (Figure 5e) is also provided. This map presents the horizontal and grey scale vertical bars in a condensed form with cumulative time spent in each scope, its location, and its processing category. By using this Profile Map, the user can easily identify the important scopes of the application, and access them by clicking on the corresponding horizontal bar of the map, which causes the main window to scroll to that scope.

The colors in the horizontal bar at the top of each scope describe a breakdown of the execution time spent in the scope into categories. Clicking on the bar produces a histogram of the overhead categories in a pop-up window (Figure 5g).

Two additional pop-up windows are used for waiting time analysis. The WT Map (Figure 5f) provides a global perspective of all sources of waiting time; the Characterization Map (Figure 5d) presents an explanation for a single source of waiting time in terms of the two execution paths involved.

 

  figure174


Figure 5: Carnival visualization of Cholesky

The WT Map lists each source of waiting time, the line number at which waiting occurred, the operation involved (receive or barrier), and the percentage of the total waiting time associated with that operation. This map is used to navigate within the source code window and to initiate waiting time analysis. Clicking on an entry in the WT Map causes the main display window to shift to the relevant portion of the source code, and the WT Map presents statistics about each cause of that waiting time. These statisics include the percentage contribution of each cause to the total waiting time experienced at that statement, as well as the total waiting time explained by each cause.

Clicking on a characterization in the WT Map produces an explanation for that waiting time in the Characterization Map. Color-coded operations for the longer of the two paths are presented on the right side of the window, operations for the shorter path are on the left. The number of occurrences of each operation is given, as is the percentage of the waiting time associated with each operation. Clicking on an operation shifts the source code window to the relevant portion of the code.

To illustrate the use of Carnival for performance visualization and tuning, we present an example analysis of a master-slave parallel implementation of dense Cholesky factorization. Given matrix A, a dense symmetric positive definite matrix distributed among the processors in a row-wise blocked fashion, the program computes a lower triangular matrix B with positive diagonal elements such that tex2html_wrap_inline609 . The computation is divided into n iterations (n is the matrix dimension), where during each iteration k a processor: (1) receives column k from all other processes; (2) divides column k by the square root of A[k][k]; (3) updates local column k+1; (4) sends column k+1 to all other processes; and (5) updates column k+2 to n in parallel with the communication. Before and after the outermost loop, the master synchronizes with the slaves using a barrier. We executed a PVM implementation on a tex2html_wrap_inline597 matrix using four processors on the SGI Challenge. The Carnival visualization is shown in Figure 5.

The primary display window (Figure 5a) shows the source code on the right and execution time profiles for each nested scope on the left. In this example, the colored bar associated with the outermost scope (Figure 5b) shows a significant amount of waiting time (the dark blue portion of the bar). Clicking on the colored bar for that scope produces the pop-up window with a color histogram for each category of execution time, and the processor efficiency for that scope (Figure 5g). As seen in the figure, efficiency is only 35%, and waiting time accounts for about one third of the total cumulative execution time.

The WT Map (Figure 5f) shows that there are three sources of waiting time: (1) the master-slave synchronization barrier before the main loop accounts for a minuscule portion of total waiting time, (2) a receive operation inside the main loop accounts for a little less than 38% of all waiting time, and (3) the master-slave barrier after the main loop accounts for 62% of all waiting time. Clicking on a colored bar within the WT Map produces the corresponding source code in the primary display window.

Each of these sources of waiting time is explained by one or more characterizations. We can iterate over the characterizations for a specific source of waiting time (in order of their relative contribution) by clicking on the colored bar in the WT Map, which produces an explanation in the Characterization Map. In our example, we focus on the cause of waiting time at the final barrier. There are three explanations (or characterizations) for waiting time at this barrier. The first of these characterizations (Figure 5d) shows that most of the waiting time at the final barrier is caused by extra time spent in communication operations (18%) and in the multi-column update loop (70%). Since the number of occurrences of each operation is also presented, we can distinguish between a difference in the number of operations versus a difference in the time spent on the same operations. In particular, we can identify load imbalance in a loop caused by having one processor execute more iterations than another, as is the case in this example. Checking the other two characterizations for waiting time at the final barrier shows that all three characterizations differ only in the relative contribution of load imbalance to the overall waiting time at the barrier.

We confirm load imbalance in the multi-column update loop by checking per-processor profiles for that scope. Figure 5c shows that processor 3 spends more time in the loop than the other processors, being responsible for 56% of the time in the loop. It is easy to see that this imbalance results from the triangular nature of the loop coupled with the blocked distribution of the matrix.


next up previous
Next: Examples of Waiting Time Up: Waiting Time Analysis and Previous: Implementation of Waiting Time

Wagner Meira
Tue Mar 19 14:59:26 EST 1996