next up previous
Next: Implementation of Waiting Time Up: Waiting Time Analysis Previous: Removing Redundant Steps

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 tex2html_wrap_inline541 (which is an execution path) for an equivalence class C, and an execution path P, we determine whether tex2html_wrap_inline547 as follows. For each step S that appears in both tex2html_wrap_inline541 and P, we compute the relative contribution of S to tex2html_wrap_inline541 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 tex2html_wrap_inline541 and P is the difference between the relative duration of S in tex2html_wrap_inline541 and P. We sum the relative distances over all steps S that appear in both tex2html_wrap_inline541 and P to determine the relative distance between tex2html_wrap_inline541 and P. If this distance is below our threshold value, then tex2html_wrap_inline547 and we must augment the cumulative characterization for C, tex2html_wrap_inline577 , which is also an execution path. For each step in P that is also in tex2html_wrap_inline577 , we add the duration of that step to the duration for the corresponding step in tex2html_wrap_inline577 . For each step in P that is not in tex2html_wrap_inline577 , we add that step to tex2html_wrap_inline577 , with the same duration as in P.

We can see the motivation for this merging process in our original example program in Figure 2. 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 of the waiting time at line 3.


next up previous
Next: Implementation of Waiting Time Up: Waiting Time Analysis Previous: Removing Redundant Steps

Wagner Meira
Tue Mar 19 14:59:26 EST 1996