Each source of waiting time is expressed as the difference between two execution paths, which may themselves include steps representing other waiting relationships. We want a characterization for waiting time in terms of computational paths only, therefore we must express every instance of waiting time in an execution path with an appropriate characterization that does not include waiting time.
For every waiting time basic block W on an execution path E,
we replace W with the two execution paths
and
that characterize the waiting time.
Assume
is longer than
.
Then for each step S in
, we add S to E,
either increasing the cumulative duration of S if it is already in E,
or adding a new step S to E if not previously present.
For each step S in
, we change the sign of the duration for step S,
and then add it to E.
As an example of this process, consider the execution presented in Figure 4. Process 0 synchronizes with process 1, which then synchronizes with process 2, which later synchronizes with process 0. The waiting time represented by A3 is the difference in the two paths taken by process 0 and process 2: (C1 + C2 + C3) - (A1 + A2). But C2 itself represents waiting time, and is equal to (B1 + B2 + B3) - (C1). Again, B2 is waiting time, and is represented as A1 - B1, which does not involve any waiting time.
Figure 4: Execution trace requiring expansion of waiting time.
We process trace events in order, so we first characterize B2 as A1 - B1. We then characterize C2 as (B1 + B2 + B3) - C1. Since B2 is a waiting time block, we replace it in this characterization for C2 with the two paths A1 and B1. We add a step for A1 to the characterization for C2. A step for B1 is already present in the characterization for C2, so we simply reverse the sign of its duration and add it to the characterization for C2, effectively cancelling the B1 step already present. The result for C2 is A1 + B3 - C1.
We repeat this process for A3, which we first characterize as (C1 + C2 + C3) - (A1 + A2). We replace C2 in this characterization with A1 + B3 - C1, which results in (A1 + B3 + C3) - (A1 + A2). This characterization can be simplified by removing the redundant step A1 on the two paths; our algorithm for identifying and removing redundant steps is presented next.