Given two execution paths that together characterize a source of waiting time, we want to remove from each path any step that occurs in both paths (on the same or different processors) for a comparable duration. Our goal is to maximize the number of steps removed from both paths, without significantly affecting the resulting WT calculation (which is still the difference between the lengths of the two paths). Our approach is to employ a greedy algorithm as follows:
Recall from our example in figure 4.3 that we characterized the waiting time A3 by the two paths (A1 + B3 + C3) - (A1 + A2). Since both paths contain the step A1, we can remove it from both paths, and shorten the characterization for A3 to B3 + C3 - A2. Note that in this case the exact same execution step (A1 in the diagram) appeared on the two paths, due to a substitution of A1 for the waiting time B2. In general, we would expect to apply this optimization in cases where two steps refer to the same basic block and processor state, but different processors and slightly different durations.
By applying this optimization to a characterization just before presentation to the user, we can offer a simple representation of waiting time for use in diagnosis, while ensuring that an accurate representation for both execution paths is available during analysis or modeling steps.