Many of the overheads associated with parallelization ultimately manifest themselves as waiting time (WT); a processor is idle while it waits for another. One way to improve application performance is to reduce each source of overhead, which often requires that we identify the causes of waiting time.
Most performance metrics and tuning techniques are designed to assist the programmer in finding the most profitable opportunities for optimizations that reduce computation time, and only indirectly address waiting time. Standard profiling techniques (such as gprof [11]) identify where the program spends the greatest percentage of its time, suggesting a focus for code optimizations. More recent profiling techniques designed specifically for parallel programs (such as normalized processor time profiling [4]) suggest code optimizations that have the most impact on parallel program performance. Critical path analysis [14] isolates the one execution path that dominates the running time of the program, ensuring that code optimizations along that path contribute to improved execution time. While all of these techniques are valuable in performance tuning, and in some cases actually measure waiting time, they do not identify the causes of waiting time.
There are tools designed to measure the frequency of operations that produce waiting time, and other related statistics that help infer the cause of waiting time. For example, Davis and Hennessy [7] developed a tool to monitor synchronization events, including the frequency of synchronization, the execution delay encountered, the time between synchronization operations, and the number of processes concurrently attempting to access a lock. Although such a tool pinpoints the sources of waiting time and may quantify the effect of waiting time on overall performance, it doesn't isolate the cause of waiting time, and therefore only indirectly suggests how to alleviate waiting time overhead.
In most cases the programmer must infer the causes of waiting time from other metrics. This inference process is both difficult and error-prone, especially when the average case behavior and worst-case behavior of a code segment vary significantly. For example, execution profiles for two code segments within a loop may indicate the two segments take the same amount of time overall, and yet each iteration of the loop may yield very different execution times for the two segments, resulting in unexplained waiting time at the end of each iteration of the loop. Furthermore, profiles may indirectly suggest that waiting time is due to load imbalance within a loop, even though that imbalance is offset by imbalance in another loop (as when successive loops operate on the upper and lower triangle of a matrix).
Waiting time can be introduced at any synchronization point,
including locks, barriers, and message exchanges.
We can define (both symbolically and quantitatively)
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.
This definition of causality comes from the knowledge that
both processors began execution at the same place at the same time,
executed for exactly the same amount of time,
and then attempted to synchronize and one processor
was forced to wait for the other.
We assume that all processors execute instructions at the same rate,
and therefore attribute the difference in time required to reach
the synchronization point to differences
in the instructions that were executed.
In order to understand the cause of waiting time between two processors at a particular synchronization point in the program, we compare the execution paths of the two processors between that synchronization point and the last point at which those processors were known to be at the same place at the same time (as recorded in an event trace), and determine why one path is longer than the other (thereby causing the waiting time). Anything the two paths have in common is removed as a potential cause of waiting time, leaving only the differences between the two paths as an explanation for waiting time. Since a synchronization statement may be executed multiple times, there may be several such explanations for each source of waiting time, corresponding to alternative execution paths. Taken together, these explanations are the cause of waiting time at one particular synchronization point in the program.
Consider the program in Figure 2 when executed on three processors (P0, P1, and P2). There are two potential sources of waiting time, corresponding to the barriers at lines 3 and 7. As seen in the execution trace in Figure 3, processor 0 waits at line 3, processor 1 waits at line 7, and processor 2 waits at both. Comparing the execution paths between the barrier at line 3 and the barrier at line 7 shows that all processors execute lines 3, 4, and 6, but only P0 executes line 5. Similarly, comparing the execution paths between the barrier at line 7 and the barrier at line 3, all processors execute lines 7, 8, and 9, but only P1 executes line 10. Waiting time analysis identifies line 5 as the sole cause of waiting time at line 7, and line 10 as one cause of waiting time at line 3 (since line 3 can also be reached without passing through lines 9 and 10).
Figure 3: Execution trace of example program.
This example illustrates several points regarding waiting time analysis. First, waiting time analysis complements profiling, which focuses attention on the code that dominates the execution. Profiling techniques (or even critical path analysis) emphasize the importance of the loops at lines 6 and 8, which dominate the execution time, but don't contribute to waiting time. Second, the source code line at which we observe waiting time may be distant from the actual cause of the waiting time. Standard trace analysis techniques would require the programmer to analyze detailed traces of the execution prior to the waiting time event, without providing any guidance as to the cause of the waiting time. Third, it is possible to identify the sources of waiting time without presenting an entire execution trace; in the example above we fully characterized the waiting time of processor 1 at line 7 as the execution time of line 5 on processor 0.
The rest of this section describes the steps taken to compute the cause of each source of waiting time in an execution.