next up previous contents
Next: Removing Redundant Steps Up: Overview of WT Analysis Previous: Expanding Waiting Time in

Merging Equivalent Execution Paths

Two execution paths are equivalent if they traverse roughly the same code, and spend the same proportion of time in each code segment. We do not require exact equivalence (where two paths execute exactly the same basic blocks, in the same order, for the same duration) because we believe that the analysis a programmer would normally perform when considering multiple execution paths does not require exact equivalence. Thus, the heuristics used to define equivalence are guided by our intuition as to what constitutes roughly equivalent execution paths.

While processing an execution trace we create equivalence classes of execution paths. On encountering a new path leading up to a waiting time event, we compare the path to the set of equivalence classes previously recorded to see if it belongs in one of those classes. If the path does not match any existing equivalence class, a new class is created with that path as both the representative of the class and the current best characterization for the class. Subsequent paths are compared to the representative for each class to see if they belong in the same equivalence class. If a path matches the representative (according to the equivalence criteria described below), it is merged with the characterization for that equivalence class.gif

Given a representative R (which is an execution path) for an equivalence class E, and an execution path P, we determine whether tex2html_wrap_inline1773 as follows. For each step S that appears in both R and P, we compute the relative contribution of S to R and P as the duration of that step in the execution path divided by the duration of the path. gif The relative distance for step S between the two paths R and P is the difference between the relative duration of S in R and P. We sum the relative distances over all steps S that appear in both R and P to determine the relative distance between R and P. If this distance is below our threshold value, then tex2html_wrap_inline1773 and we must augment the characterization for E ( tex2html_wrap_inline1779 ). For each step in P that is also in tex2html_wrap_inline1779 , we add the duration of that step to the duration for the corresponding step in tex2html_wrap_inline1779 . For each step in P that is not in tex2html_wrap_inline1779 , we add that step to tex2html_wrap_inline1779 , with the same duration as in P.

We can see the motivation for this merging process in our original example program in figure 4.1. In that program the barrier at line 3 is executed 100 times. The first time the barrier is executed there may or may not be any waiting time, depending on whether all processes started executing the main program simultaneously. The other 99 times the barrier is executed, waiting time depends on the time process 1 takes to execute lines 9-10. Thus, we will see 99 characterizations for waiting time at line 3 that are essentially equivalent, and would be merged by the above process. Even if the program introduced small variations in the computation time of the loops at line 6 and 8, we would still produce a characterization that isolated the loop at line 10 as the cause of most waiting time at line 3.


next up previous contents
Next: Removing Redundant Steps Up: Overview of WT Analysis Previous: Expanding Waiting Time in

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