Debugging with Ariadne typically proceeds in a top down manner. Initial coarse models are further refined until the error is located. The investigated models themselves are simple, reducing the possibility of a modeling error, and allowing for better characterization of mismatches. To investigate a match, Ariadne provides query facilities. In the case of Binary Image Compression program, the user may want to know the following characteristics of a successful match.
Did the number of processors initiating an exchange get halved at each subsequent iteration?
Did all exchanges take place between paired processors?
Were the sets of processors initiating an exchange in different iterations disjoint?
For a correct execution, the answer to the first three questions should be ``Yes'', and the last query should return an empty set. All functions in Ariadne ``walk'' match trees. Currently available functions can count the occurrences of a particular event type, identify processes satisfying a given predicate, check whether given predicates hold among a group of abstract events. An exhaustive list of such functions are given in []. The user can build new functional queries simply by defining a value for the function at nodes in the tree.
Different levels of the match tree correspond to different levels of user abstraction. Often the user needs to verify different assertions at different levels of abstraction. To facilitate this, Ave treats its match tree visualization as a spreadsheet interface. A flat two-dimensional spreadsheet contains active cells with data values, and it allows a new value to be computed for a destination cell by selecting data cells and applying a transformation via a formula on the data of the selected cells. Cells are selected by by specifying their relative location by a coordinate transformation from the anchor cell. Ave presents a tree-structured spreadsheet, where each node corresponds to an abstract event, each containing a a complex data structure. The data structure at each node can be augmented by new data values. The elements of the complex data structure are called attributes of the abstract event. As in the case of flat spreadsheets, in order to compute a new attribute based on attributes of other nodes, the user needs to select the relevant source nodes. These nodes are selected by giving their relationship (parent, child, sibling, descendant, and ancestor) with the anchor node. The more general relationship descendant and ancestor can be used to identify a single or a set of nodes uniquely.
A spreadsheet interface for performance debugging has been proposed and implemented by Sarukkai and Gannon [38]. However, instead of process interaction, they use the static control flow structure to achieve coarse grained filtering. Events are selected by walking down the static control flow graph, and then issuing temporal queries on a historical database. Ave uses the user-defined abstraction to handle the multi-dimensional temporal aspect, and the resulting match tree to select relevant events. Ave thus provides a closer coupling between the dynamic program behavior and the user defined abstractions.
Example: Binary Image Compression (Continued) Figure 9 shows the presence of a possible synchronization error in the execution. Before investigating what may cause such failure of synchronization, the user needs to verify that such failure is not an artifact of the coarseness of the model. The model in Figure 6 does not specify explicitly the number of processors taking part in each iteration, and the chain description used can match two behaviors - the expected one where messages are exchanged between two processors, as shown in Figure 10(a), and an unintended one shown in Figure 10(b).
To verify that the precedes failure is not an artifact of coarse grain modeling, the user had to verify the four assertions listed earlier in the section.
The first assertion can be checked by computing,
for each of the compr events, an attribute
that is the number of processors that participated on the
match.
with compression foreach compr compute size = count(proc);
In a correct execution, this attribute should be halved
at each subsequent iteration. This is a temporal pattern best
illustrated with a line plot. Ave allows the user to choose the
plotting style, by clicking on the menu button in the
window named Drawing Canvas.
with compression show size(compr) wrt compr;
The Ave output shows that the expected assertion held true.
For the second assertion, we need to verify that the process
identifier of the second R event in each chain is the same as
the first W event. This can be done with
with compression foreach proc
compute diff = eq(pid(leaf(first)), pid(leaf(last)));
with compression show diff(proc) wrt compr;
where first and last are keywords in Ariadne that
refer to the first and last members of any list, and pid is a
keyword signifying the process-identifier of an event.
The attribute diff can take only two values: 0 and 1. For display,
Ave partitions the abstract events into equivalence classes based on the
attribute value and maps the equivalence classes to different colors.
For this example, the computed attribute should have the same value 1.
A scatter plot display of the attribute is shown in
Figure 12.
Note as the number of iterations increase, such scatter plot techniques
become non-scalable. For instance if there were 128 iterations instead
of 5, how do we maintain scalability? The power of the spreadsheet can
be made to accommodate such cases: one can compute
another attribute idiff for each compr event that takes a value 1
if all its children proc nodes have the value 0, and a value 0
otherwise. This attribute idiff can then be plotted.
All the primitive events in the match tree form the
leaf level of hierarchy, and they can be indexed by their position
in the match. The commands are simple.
with compression foreach proc
compute diff = pid(leaf(first)) - pid(leaf(last));
with compression foreach compr compute idiff =
eq(diff(proc), 0);
with compression show idiff(compr) wrt compression;
that produces the display shown in Figure 13 for the
current example with 5 iterations. It can be seen clearly, that this
display occupies much less space than that of Figure 12.
But in case of error, it can only identify the iteration that
contains the erroneous exchange - the user needs to investigate
further to get a more detailed feedback.
If the behavior we were modeling was a pipelined version of the
algorithm, for example, we may want to go even further.
with compression foreach proc
compute diff = pid(leaf(first)) - pid(leaf(last));
with compression foreach compr compute idiff =
eq(diff(proc), 0);
with compression foreach compression compute cdiff =
eq(idiff(proc), 0);
with compression show cdiff(compression) wrt compression;
that will, in our case, produce a single point in the scatter plot.
Although the display is the most scalable, in case of an error it does
not even identify the iteration where the erroneous exchange takes place.
There is a trade off between scalability and preciseness of the error feedback. Ave allows the user to select the scalability/preciseness ratio, starting with the most scalable display initially, and progressively adding more detail.
In our case, this would mean the third description, followed by the plot of the attributes cdiff, idiff and diff.
The third assertion can be verified by checking whether the sets of processors taking part in different iterations are disjoint or not. Ariadne gives an internal label of proc to each processor at the p-chain level; and a function disjoint that given a list of sets indicates whether the sets are disjoint or not.
with compr foreach compr compute pset = pid(proc);
with compr foreach compr
compute disj = disjoint(pset(compr));
At this point the user is convinced that the coarse grain pattern
description has indeed matched the correct behavior, and the
precedes failure is not an artifact of the corse level behavior
specification. The failure is thus most likely due to a synchronization
error. Ariadne's modeling highlights the error at the level of user
abstraction, but does not indicate the source code portion that is
responsible for it. To do so, we need to set a consistent global
breakpoint immediately before the error occurs.
