Image Compression: Modeling

We model the behavior of the binary image compression algorithm with user-level events Merge and NoMerge and the runtime system-specific event Barrier synchronization. (See the Ariadne Overview for a description of the modeling language.)

The behavior of a single node is modeled in terms of chains as follows :

(* chain definition *)
ch Merge = U_PCXX_user_event3;
ch NoMerge = U_PCXX_user_event2;
To model the behavior of the nodes across a level of the tree, we first define the successful completion of a barrier synchronization as
ch Barrier = U_PCXX_begin_barrier;
and then model the complete behavior at a single level as
(* p-chain definition *)
pch CompressLevel = Barrier* ( (+Merge  NoMerge+) )* Barrier  onsome procset;
Here, (+A B+) is the Ariadne syntax for the regular expression A or B and * denotes zero or more occurences. The behavior of the entire algorithm is modeled as
(* match statement *)
match BIC = CompressLevel* ;
The match is shown by the Ariadne Visualization Engine.

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.

[Next]