Many of the overheads associated with parallelism ultimately manifest themselves as waiting time; a processor is idle while it waits for another. Waiting time can be introduced at any synchronization point, such as locks and barriers, or whenever a request is issued by one processor that is served by another (e.g., page faults served remotely).
Consider two processors A and B that synchronize at a barrier, execute for some period of time, and then synchronize again at the barrier. Assume A arrives at the barrier before B. We can define the cause of waiting time suffered by processor A to be the differences in the execution paths of processor A and B since the last time they synchronized at the barrier. In order to understand why A must wait for B, we compare the execution paths of the processors leading up to the synchronization point, and determine why one path is longer than the other. 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. These differences may represent code segments that were executed by one processor but not the other, or communication operations that were required by one processor but not the other.
Waiting time analysis is an automated technique that generates explanations for waiting time in an execution. (See [11] for a detailed description of waiting time analysis and its use in message-passing systems.) The implementation analyzes execution trace files, recording each occurrence of waiting time, and the set of basic blocks traversed by each processor leading up to a synchronization point. The result of this process is (1) a global execution-time profile of the program, which describes how much time is devoted to various forms of overhead (e.g., load imbalance, contention, insufficient parallelism) that result in idle processors; (2) a waiting time profile for each basic block in the program, which helps to identify portions of the source code that deserve special attention; and (3) an explanation for each source of waiting time in terms of the basic blocks that must be modified to reduce it.
Waiting time analysis complements profiling, which focuses attention on the code that appears to dominate the execution, but which cannot capture or quantify indirect effects on waiting time. Since the source code line at which we observe idle time may be distant from the actual cause, we need both waiting time analysis and performance profiles to isolate and understand the behavior.