Waiting time arises whenever one processor
waits at a synchronization point for another processor.
We can define the cause of waiting time between two processors
to be the differences between the execution paths followed by the processors
since the last time the two processors synchronized and one waited for
the other, hence both processors were known to be at the same place
at the same time.
To capture such an explanation requires that we record the execution
paths of processors, and compare them whenever differences
cause one processor to wait for another.
Waiting time analysis [7] identifies each occurrence of waiting time in the execution trace, and the set of basic blocks traversed by each processor leading up to a synchronization point. We divide a processor's execution path into synchronization intervals, where the intervals are delimited by synchronization points between the same pair of processors. An occurrence of waiting time can be explained by the events in the synchronization interval that immediately precedes the waiting time.
Only the differences in execution between two processors can produce waiting time; any execution steps performed by both processors within a synchronization interval cancel each other out and do not contribute to waiting time. Thus, the simplification step compares two execution paths and removes any steps that exist on both paths. The result is an explanation for a given occurrence of waiting time, which consists of two execution paths; one representing the computation of the processor that was forced to wait at a synchronization point (and excluding any steps performed by both processors), and the other representing the computation of the processor that caused the waiting time (again excluding any steps performed by both processors).
Since each synchronization operation in the program may be performed many times, an explanation for the total waiting time associated with an operation must combine the explanations for each instance of the operation. The combination strategy employed by waiting time analysis ignores the processors involved, and also any sequencing information in the execution paths. The result is an explanation that identifies the dominant code path followed by whichever processor caused the waiting time, ignoring any parts of the execution that didn't directly contribute to the waiting time.
These explanations can be visualized by showing the source code executed by both processors during a synchronization interval, again ignoring any code executed by both processors (since it could not contribute to waiting time). An example of such a visualization is given in Figure 2. The figure identifies the code executed by the slower processor on the right, and the relative time spent on each code segment. The code executed by the processor that waits is given on the left. In cases where one processor does everything the other processor does and more, the left side of the figure would be empty.
Figure 3: Protocol analysis for Ocean -
This figure describes the access pattern to one of the pages
of the variable multi. Each column header describes a node
in the communication graph, detailing the line where the page was accessed
(R for request, I for invalidation, and W for preceding writes), and the
type of sharing pattern (as indicated by the color of the header).
The entries quantify the relative frequency of transitions between
nodes in the graph.
The pop-up window contains per-processor information associated with
node 1, describing which other processors accessed the page and the
type of access (R, W, or both, according to the color code).