next up previous
Next: Visualization with Carnival Up: Waiting Time Analysis and Previous: Merging Equivalent Execution Paths

Implementation of Waiting Time Analysis

We implemented waiting time analysis in Carnival using a pipeline of four independent tools. The first tool in the pipeline takes in trace file information and translates event information into execution steps. Each pair of matching events (such as the beginning and end of a system call) becomes a single execution step with a start and end time. Both event tracing environments exploit a global clock implemented in hardware to record all time information, so the step durations are accurate to within a microsecond.

Another tool takes the execution step information as input and produces as output a pair of execution paths for every instance of waiting time in the execution. Each path is a set of execution steps, so the size is bounded by the product tex2html_wrap_inline593 .

Another tool takes as input the list of waiting time steps and the pair of paths representing each such step, and creates a set of equivalence classes of execution paths (i.e., merges equivalent paths). The output of this tool is a list of waiting time steps expressed in terms of the representative path for an equivalence class. The waiting time step defines the duration of waiting; the representative path defines the percentage of that duration associated with each execution step on the path.

For each instance of waiting time, another tool removes any redundant steps between the pair of paths that characterizes it. This tool also acts as a filter on the set of characterizations, allowing the user to select individual execution steps for analysis.

It is important to note that none of these tools require access to the complete trace file. Only a small part of the dynamic data processed by a tool needs to be accessible at any moment in time. In addition, the amount of memory needed to store the WT characterizations is proportional to the number of distinct execution step triples (processor, code, state), and is not dependent on the length of the execution trace.

This four-stage pipeline is dominated by the first two stages: (1) the translation of events to steps, and (2) the generation of waiting time characterizations from steps. On the SP2 these stages are dominated by the size of the trace files, and can take 30 minutes or more if executed sequentially. The same steps take less than 30 seconds on the SGI. Regardless of the original source of traces, the remaining steps are much more efficient, taking less than 20 seconds each for our example programs. Our experience to date shows that we process execution steps into waiting time characterizations at the rate of 742 steps/sec or better. We cluster execution paths into equivalence classes at the rate of 52 paths/sec, and remove redundant steps from waiting time characterizations at the rate of 47 characterizations/sec.

Table 1 illustrate the problem size and compression efficiency of each tool on the SP2 and SGI Challenge traces. The applications described in the table include the barrier program from Section 3, Cholesky factorization with a cyclic and blocked data distribution, a triangular solver, matrix multiply, and an econometric modeling application (Nagurney). The input size for Cholesky factorization on the SP2 is tex2html_wrap_inline595 ; on the SGI the input size is tex2html_wrap_inline597 . The input size for matrix multiply is tex2html_wrap_inline599 ; for triangular solver, the input size is tex2html_wrap_inline597 . We ran Nagurney for 10 iterations on a tex2html_wrap_inline595 matrix, and the barrier program for 200 iterations. We used 4 processors in each case.

The tables give the following statistics for each application: (1) the number of events in the trace, (2) the number of execution steps in the trace, (3) the total number of execution steps that involved waiting time (TWT), (4) the number of basic blocks that introduced waiting time (SWT), (5) the average number of characterizations per WT triple (AC), (6) the number of different execution paths identified, (7) the average execution path size (PSP) prior to removing redundant steps, and (8) the average path size after removing redundant steps (PSR).

 

  table147


Table 1: WT Compression Statistics.

As can be seen in the case of Blocked and Cyclic Cholesky, the trace files generated on the SP2 are much larger than the trace files generated on the SGI, even though the problem size used on the SP2 is smaller. There is some compression of information in translating from events to execution steps on the SP2 precisely because there is so much extraneous information collected in the trace files on the SP2. Note that there isn't always a 2-to-1 compression between events and steps because two nested events generate more than two steps.

In comparing the columns labeled TWT and SWT we can see that a relatively small number of places in the source code (SWT) introduce waiting time, even though there are a relatively large number of instances of processors kept waiting (TWT). As seen in the column labeled AC, there are several different execution paths leading up to each source of waiting time, but by removing redundant blocks (PSR), each path is relatively short. In fact, comparing columns PSP and PSR shows that removing redundant blocks eliminates from 20-80% of the blocks in the characterization.

There are numerous characterizations for each source of waiting time in Cyclic Cholesky on the SP2 (456.5) and in Blocked Cholesky on the SGI (125.1). In the case of Cyclic Cholesky on the SP2 the many characterizations are caused by variations in message transmission time on each iteration of the main loop. We cannot collapse these characterizations into a small number of equivalence classes because the durations for waiting time are so small that the percentage difference between each characterization appears too large to be captured within one equivalence class. We would expect our tools to filter out characterizations that describe an insignificant (in duration) source of waiting time, so large values for AC in these cases should not necessarily complicate the analysis. In the case of Blocked Cholesky on the SP2, there are many fewer communication operations required by the algorithm, and the loop imbalance in the algorithm accumulates as waiting time at a final barrier in the program. Therefore, a small number of characterizations suffice to capture all sources of waiting time for this program.

The situation is reversed on the SGI, where Blocked Cholesky requires on average more characterizations for each source of waiting time than Cyclic Cholesky. gif Once again, the problem is our inability to merge similar paths into equivalence classes. In this case the paths represent computation and communication within a triangular loop. Each successive iteration of the loop has slightly less computation, but comparable communication, so the ratio of the computation and communication steps in the path is constantly decreasing. Although two successive iterations might fall within the threshold for a single equivalence class, three or more consecutive iterations usually do not. It's possible to incorporate this common situation into our heuristics for merging equivalent paths but we haven't done so yet.


next up previous
Next: Visualization with Carnival Up: Waiting Time Analysis and Previous: Merging Equivalent Execution Paths

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