During analysis, the Carnival tools summarize dynamic information and associate this data with the static information collected previously. The result is a Tcl/Tk [Ousterhout1994] interface that presents both static and dynamic data.
The addition of dynamic data produces two kinds of information: (1) a hierarchy of basic blocks, and (2) cumulative timings for each basic block, consisting of the triples basic block identifier, processor identifier, and category.
Basic blocks are determined during the analysis of the execution trace file using only the sequence of scope identifiers. While traversing the trace file, we keep track of the ``stack'' of open scopes and the last scope that was closed. Thus, whenever we enter a scope, we can determine the basic block characteristics easily. Then we check if the block is already defined in the block database. If it is, we use the same block identifier, otherwise, we create a new entry. Table 3.1 presents the database of basic blocks for our example. Simultaneously with the determination of the basic block hierarchy, we accumulate timings, with one accumulator for each triple (block, processor, category).
At the end of the trace file analysis, we have a database of basic blocks and timings for the various triples. For each scope, we must determine cumulative and non-cumulative timings. Cumulative timings for a scope include nested scopes and scopes that are called from the scope or any of its nested components. Non-cumulative timings include only the data corresponding to the scope itself. We use the database of basic blocks to determine the blocks that contribute to the timings of each scope. We determine non-cumulative timings by adding blocks that have the same current scope. Cumulative timings are determined by adding the timings of each block to all scopes in its ``stack'' and its current scope. This process is illustrated in Figure 3.2. Cumulative timings for Scope B, for example, include not only block 2, but also block 7.
Table 3.1: Characteristics of
basic blocks
Basic block timings, the basic block hierarchy, scope location, and source code are the parameters to a visual interface of the program's performance, which is presented in the remainder of this section. The basis of this interface is a set of Tcl/Tk procedures that implement the various displays and handle numerical data.
Figure 3.3: Visualization with Carnival
The primary Carnival display window (figure 3.3a) 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 3.3b).
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 3.3d). In order to facilitate the navigation in the main window, a Profile Map (Figure 3.3c) 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 correspondent horizontal bar of the map, which causes the main window to scrolls to that scope.
The Carnival framework is a valuable performance tool by itself, even without any explanation techniques. It automatically instruments HPF code to generate an event trace with timing information, and processes the event trace for presentation to the user at several levels of detail. Carnival helps a 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 (such as communication and waiting time) are introduced.