next up previous contents
Next: Implementation of WT Analysis Up: Overview of WT Analysis Previous: Merging Equivalent Execution Paths

Removing Redundant Steps

 

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:

  1. For each step on one path, find an equivalent step (ignoring the processor) on the other path if it exists.
  2. Sort the list of steps that appear on both paths (from lowest to highest) according to the difference in duration on the two paths.
  3. Remove the steps, in sorted order, from each path as long as the total difference in duration between the two paths remains sufficiently close to the waiting time. We chose 95% as our initial level of tolerance for this algorithm, so we remove blocks only as long as the remaining blocks account for 95% of the actual waiting time.

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.


next up previous contents
Next: Implementation of WT Analysis Up: Overview of WT Analysis Previous: Merging Equivalent Execution Paths

Wagner Meira
Wed Feb 28 15:37:47 EST 1996