We characterize the waiting time between two processors as the difference between the execution paths followed by the processors between two synchronization points where one processor waited for the other. An execution path is a sequence of steps by a single processor; each step represents the execution of a basic block by that processor, and is characterized by the state of the processor during that step and the duration of the step. We use unique identifiers for each basic block in the program to represent the code being executed. The processor state can be either waiting or one of several types of computation, including parallel computation, parallelization overhead, communication and synchronization setup, and system calls.
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.
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 (i.e., expand it) 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 doesn't use waiting time steps, provided the execution does not contain a circular wait (i.e., deadlock). Thus, we can produce characterizations for waiting time in terms of computational steps only, as shown in Section 3.2.
Given two execution paths that result in waiting time, we remove any equivalent steps that appear in both paths and contribute equal amounts to each path. By eliminating these redundant steps, we isolate the differences between the two execution paths. Our goal here is to maximize the number of steps removed from both paths, without significantly affecting the difference between the lengths of the two paths. The result is one characterization for waiting time at a particular synchronization point. We adopted a greedy heuristic for removing redundant steps, which is described in Section 3.3.
Any synchronization statement that introduces waiting time may be executed multiple times, and the execution paths preceding different executions of that statement may or may not be the same. The explanation for total waiting time at a single statement must capture these different execution paths (e.g., the two paths leading to the barrier at line 3 in Figure 2, one coming from line 1 and the other coming from line 9). To do so, we construct a characterization for each instance of waiting time and then merge equivalent characterizations for the same statement into one. Thus, as we process the execution trace, we create equivalence classes of execution paths, as described in Section 3.4.
It is important to note that waiting time analysis
does not capture processor stalls due to the memory system,
since it is impractical to monitor every processor stall in software.
Thus, on shared-memory machines,
waiting time analysis considers synchronization loss only,
and not the time lost due to remote memory accesses.
Differences in computation time caused by remote memory accesses
on one processor that are local memory accesses on another
may ultimately produce waiting time,
but waiting time analysis will attribute the waiting time
to a difference in the computation times of the two processors
without explicitly recognizing the role of remote accesses.
Similarly, if two processors do not execute instructions at the same
rate, waiting time analysis will identify the two execution paths
leading up to a synchronization point in their entirety,
without explicitly identifying the role of processor speed.
The following subsections describe additional details of the algorithms used in waiting time analysis.