Modeling in Ariadne

We ran the Ariadne Visualization Engine (AVE) and did event based modeling.

geos [~/ts/newbic]% ave &

We modeled the behavior of the binary image compression algorithm using user level events of Merge and Tree (NoMerge) and the runtime system specific event of Barrier synchronization.

add etype U;
add utag PCXX_user_event1;
(* event1 is start *)
add utag PCXX_user_event2;
(* event2 is tree *)
add utag PCXX_user_event3;
(* event3 is merge *)
add utag PCXX_user_event4;
(* event4 is end *)
add utag PCXX_begin_barrier;
add int other level Elemid to U;
(* load the trace file *)
load newbic8.trace;
(* set definition *)
set procset = {0..7};

(* chain definition *)
ch Merge = U_PCXX_user_event3 wrt [U_PCXX_user_event3 U_PCXX_user_event2 U_PCXX_begin_barrier];
ch NoMerge = U_PCXX_user_event2 wrt [U_PCXX_user_event3 U_PCXX_user_event2 U_PCXX_begin_barrier];

ch Barrier = U_PCXX_begin_barrier wrt [U_PCXX_user_event3 U_PCXX_user_event2 U_PCXX_begin_barrier];

pch CompressLevel = Barrier* ( (+Merge  NoMerge+) )* Barrier  onsome procset;
(* p-chain definition *)

(* match statement *)
match BIC = CompressLevel* ;

Matching imposes a tree structure on the matched subgraph that corresponds to the model's structure. It is this match tree that is displayed by AVE in the figure. For scalability, it is automatically compressed both horizontally and vertically: horizontally by eliding sibling nodes and vertically by pruning levels. The horizontal compression is straightforward: omitted siblings are represented by a single slider. In our example, the match tree included 8 instances of the COMPRESSLEVEL p-chain but only the first and last are explicitly shown in the initial picture. Vertical compression is achieved by pruning subtrees below each p-chain. The pruned subtrees are partitioned into equivalence classes and represented by an icon labeled with a pair of integers that summarizes the partitioning: the first element is the total number of chain subtrees represented and the second is the number of equivalence classes of those trees. In the example, the leftmost box is labeled with 8,1 which indicates that 8 processes initiated a COMPRESSLEVEL event and all of them matched the same p-chain pattern. The pop-up window below (obtained by clicking on the icon) gives a further description of this subtree: a pattern matching 5 barrier events, followed by 16 compression events (either MERGE or NOMERGE), followed by another barrier was matched on processes 0 through 7. This is as expected. In the first step of the compression, each process handles 32 leaf nodes of the image, performing 16 compression operations. In the last step, only one process is active as evidenced by the 1,1 label on its node.

So far, our output was as expected. Ariadne's models, however, are quite coarse and it is often useful to investigate a match further using its query facilities. In this case, because we knew that the resulting compressed image was too small, we were suspicious that erroneous, extra MERGE events were occurring. To check this, we wanted to determine the number of elements executing MERGE events in each COMPRESSLEVEL. So, we defined an additional attribute, MERGELTS, for MERGE nodes and displayed the number of merges at each compress level.

with BIC foreach Merge compute MergeElts = Elemid(U_PCXX_user_event3);
with BIC foreach NoMerge compute NoMergeElts = Elemid(U_PCXX_user_event2);
with BIC foreach CompressLevel compute MergeSet = MergeElts(Merge);
with BIC foreach CompressLevel compute NoMergeSet = NoMergeElts(NoMerge);
with BIC foreach CompressLevel compute NumMerges = sizeof(MergeSet(CompressLevel));
with BIC show NumMerges(CompressLevel) wrt CompressLevel;

These plots were not as expected. At each level in the bintree, only those nodes that were successfully merged at the previous level are available for merger; thus, the number of successful merges at any level should be no more than half the number from the previous step. We see a problem. 32 events were compressed at the third level but this is more than half of the 63 that had been compressed at the second level. There were too many MERGEs on the third level.We next investigated the possibility that some of the mergers were invalid because one of the siblings represented a subtree where compression had already failed at a lower level. This would result in a NOMERGE event being followed by a subsequent MERGE event on the same element. To check this, we first computed

  
with BIC foreach CompressLevel compute MergeFlag = disjoint(MergeSet(CompressLevel), NoMergeSet(left(CompressLevel)));
with BIC show MergeFlag(CompressLevel) wrt CompressLevel;