next up previous contents
Next: Applications of WT Analysis Up: Understanding Waiting Time Previous: Removing Redundant Steps

Implementation of WT Analysis

Our implementation of WT analysis uses several independent tools that can be executed in a pipeline fashion. Organizing the tool set in this way has the advantage that WT analysis can be performed on-line in parallel (using one processor per tool), allowing the tools to process information from large-scale parallel programs.

The first step is trace generation. On the IBM SP2 we utilize the UTE trace facility [Wu and Franke1995], which is implemented on top of IBM's AIX trace facility [AIX1994]. We generate execution traces for Fortran programs that are parallelized using FORGE [Forge1995] to produce MPI message-passing programs [Franke et al.1994].

As described in Section 3.3.1, we use the UTE trace facility [Wu and Franke1995] to monitor parallel applications and generate trace files that are post processed. The level of detail in the UTE traces is enormous (and for the most part beyond our control), so the overhead of tracing in this environment is quite large, increasing execution time by a factor of 2-3 in many cases. It is not unusual to see 100 MB trace files on the SP2.

In order to distinguish between the trace information needed for WT analysis and the detailed event traces generated on the SP2, we hand-instrumented PVM programs on the SGI Challenge. In this environment we only generate trace events for those events needed by WT analysis. As a result, tracing is much less intrusive (on the order of 5% execution time overhead) and produces much smaller trace files (by one to two orders of magnitude) than on the SP2.

A separate tool takes in trace file information and translates event information into execution steps. Each pair of matching events (such as the beginning and ending 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.

The next 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 contains a set of execution steps and the cumulative time of each step on the path. The length of a path is bounded by the product tex2html_wrap_inline1809 .

The next 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 (ie, 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.

The tool pipeline is dominated by the first two stages: the translation of events to steps, and 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. Our experience to date suggests that we can process execution steps into waiting time characterizations at the rate of 742 steps per second or better. We can cluster execution paths into equivalence classes at the rate of 52 paths per second, and remove redundant steps from waiting time characterizations at the rate of 47 characterizations per second.

Tables 4.1 and 4.2 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 4.1, 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_inline1811 ; on the SGI the input size is tex2html_wrap_inline1813 . The input size for matrix multiply is tex2html_wrap_inline1815 ; for triangular solver, the input size is tex2html_wrap_inline1813 . We ran Nagurney for 10 iterations on a tex2html_wrap_inline1811 matrix, and the barrier program for 200 iterations. We used 4 processors in each case.

The tables give the following statistics for each application:

   table394
Table 4.1: WT Compression Statistics on SP2 Traces.

  
Table 4.2: WT Compression Statistics on SGI Traces.

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 a large number of 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 would be possible to incorporate this common situation into our heuristics for merging equivalent paths but we have not done so yet.


next up previous contents
Next: Applications of WT Analysis Up: Understanding Waiting Time Previous: Removing Redundant Steps

Wagner Meira
Wed Feb 28 15:37:47 EST 1996