Our approach to waiting time analysis is based
on an examination of the dynamic behavior of programs.
We execute a program under study one or more times,
collecting information about the execution path
of each processor along the way.
We process this dynamic information
to produce a waiting time characterization for each
instance of waiting time that occurs during execution.
We assume event traces of a parallel program's execution
as the starting point for our analysis tools.
These event traces are obtained by executing programs that are
instrumented by Carnival, as described in Section 3.3.1.
We can characterize (and even quantify) the waiting time between two
processors as the difference between the execution paths followed by
the processors since the last time the two processors synchronized. An
execution path is a sequence of steps; each step has a duration and is
represented by a triple that identifies the processor executing the
step, the code being executed by the processor, and the state of the
processor
during that step. This information is obtained by translating the
trace file produced during an application's execution (as described in
Section 3.3.2) into a sequence of steps.
For the purposes of characterizing waiting time, we can represent an execution path as a set of execution steps (rather than a sequence of steps), and the cumulative time spent on each step. In this representation, two steps in an execution path are the same if they involve the same processor, code, and state. This representation is a significant compression of a dynamic event trace, since the size of the representation is proportional to the length of the program, rather than the length of the execution. This representation can be created on-line during execution.
Two paths characterize (or explain) a source of waiting time in terms of the basic blocks whose execution time difference resulted in one processor waiting for the other. If any of the steps on a path represent waiting time on the part of some other processor, we can replace that step with the characterization for its waiting time. Since a characterization for any step representing waiting time can be created when the step is first encountered in the trace, it is always possible to replace a step representing waiting time with a characterization that does not use waiting time steps, provided the execution does not contain a circular wait (ie, deadlock). Thus, we can produce characterizations for waiting time in terms of computational steps only. (The details of how this is done are given below.)
Any synchronization statement that introduces waiting time may be executed multiple times, and the execution paths preceding different executions of the statement may or may not be the same. The characterization for total waiting time at a single statement must capture different execution paths, without repeating equivalent paths. Thus, we merge two characterizations for the same statement into one, provided that the two characterizations are roughly equivalent. Determining rough equivalence requires heuristics that capture the programmer's intuition regarding path equivalence. For example, two paths may be seen as equivalent if they execute the same basic blocks, and spend the same percentage of time in each block of code.
In presenting a characterization for waiting time we exclude (or ignore) any equivalent steps that appear in both paths and contribute equal amounts to each path (so called redundant steps). By eliminating redundant steps we produce a minimal description of the differences between the two execution paths.
We describe each of these steps in more detail in the following subsections.