Many of the overheads associated with parallelization (i.e., communication, synchronization, load imbalance, resource contention, and insufficient parallelism) ultimately manifest themselves as waiting time; 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 [Graham et al. 1982]) 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 [Anderson and Lazowska1990]) suggest code optimizations that have the most impact on parallel program performance. Critical path analysis [Yang and Miller1988] 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 [Davis and Hennessy1988] 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 does not isolate the cause of waiting time, and therefore only indirectly suggests how to alleviate waiting time overhead.
Waiting time is an example of a performance phenomena that requires explanation. The inference process associated with waiting time 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).
In this chapter, we present a new performance analysis technique that identifies the root causes of waiting time, and produces a characterization (both analytic and descriptive) for each source of waiting time in a parallel program.
Waiting time (WT) can be introduced at any synchronization point, including locks, barriers, and message exchanges. WT between two processors arises from the differences in the execution paths followed by each processor since their last synchronization point (possibly as far back as the start of the execution). In order to understand the causes of a specific instance of WT during an execution, we must examine these execution paths in detail, and determine why one path is longer than another (thereby causing the waiting time). Given an understanding of the cause of waiting time, we can lower it by applying selected optimizations to the longer path.
As an example of this type of waiting time analysis consider the program in Figure 4.1 when executed on three processors (identified as processor 0, 1, and 2). 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 4.2, processor 0 waits at line 3, processor 1 waits at line 7, and processor 2 waits at both. Even though all processors execute the same loop at line 6, they start at different times due to the loop at line 5, which only processor 0 executes. Thus, processor 1 and 2 always wait at line 7, and the duration of the waiting time depends on the value of N (the number of times processor 0 must execute the loop at line 5). Similarly, processor 0 and 2 always wait at line 3 (except the first time), because only processor 1 executes the loop at line 10. The duration of the waiting time for processor 0 and 2 at line 3 depends on M, the number of iterations in the loop at line 10.
As can be seen in Figure 4.2, the time spent waiting at line 7 by processor 1 is due to the different execution paths taken by processor 0 and 1 since their last synchronization point at line 3. This time can be calculated as the difference in time between the execution paths of processor 0 and 1: (L3 + L4 + L5 + L6) - (L3 + L4 + L6) = L5. Similarly, the time spent waiting at line 3 by processor 0 (again, except the first time) is: (L7 + L8 + L9 + L10) - (L7 + L8 + L9) = L10. Furthermore, given a model for the running time of lines 5 and 10 (perhaps as a function of the number of processors or the input size), we can create a model for the waiting time at lines 3 and 7.
Figure 4.2: 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 do not 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.
There are several goals we expect to achieve by characterizing waiting time in this way. We can quantify the waiting time at a particular point in the program in terms of the difference between the execution time of the two paths that produced the waiting time. Also, the waiting time incurred at each point in the program can be defined in terms of the source code that produced it; by highlighting the source code differences between the two execution paths, we can alert the programmer to places in the program that must be changed to reduce the waiting time. Most important, we can model the effects of program or system modifications on the waiting time as the difference between the performance models for two computation paths, which can be developed using known methods such as complexity analysis or static analysis [Fahringer1995, Gupta and Banerjee1992]. These models would allow us to quantify the impact on waiting time of a change in the number of processors or problem size, and ultimately to predict accurately the running time of a program under these varying conditions.
This chapter is organized as follows. We first describe our algorithms for capturing a minimal descriptive characterization of waiting time for each source code statement that introduces delays between processors. We also discuss the overhead of our measurement system and the WT analysis that produces the characterizations. We then apply our analysis to real programs, to illustrate the value of WT analysis in diagnosing performance problems, and to show how to develop models of waiting time that can be incorporated into models of execution time. Finally, we present our conclusions and our ideas for future work.