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