Chain

Chains are local view of computation, and are primarily used for specifying a sequence of events. The execution graph of a parallel program consists of nodes that signify events and edges that signify two different relationships that could exist between events: one that events are related by the same program order (that they occured on the same process), and the other that events are related by causal order (that they are related by the sending and receiving of messages or some other form of comuunication). In Ariadne, we mostly deal with immediate program order edge and immediate message order edge. Primitive events are the ones that are captured in the trace-file through instrumented message-passing library, and include send, receive and multicast events. User defined events are also allowed. In our regular expression, events are specified using identifiers, while the program order edge is specified by a space, and the immediate casual order is symbolized by the @ symbol. Note program order and causal order are distinguishable only in the chain level where primitive events are involved. At higher levels, we have abstract events and there we do not explicitly distinguish between the program order or causal order edges.

The chain definition has the following syntax:

ch <chain-name> = <chain-expr> [wrt wrt-list];

Formally, a chain is a tree that is to be matched against the execution history graph. Nodes in the tree can represent communication events: ReadEvents denoted by R, or WriteEvents, denoted by either W or M (depending on whether it is a single write or a multicast), Events can be suffixed with explicit tags such as W_pivot and R_elim.

For instance, the user can define a chain

ch msg = W R

po.chain.eps

The matching process for a chain always begins on a single process. It may stay entirely on that process, as in the above examples, or it may migrate to other processes by following a communication arc. An @ occurring between a WriteEvent and a ReadEvent event denotes a migration; matching is suspended on the writing process and initiated on the receiving process. Thus

ch msg = W @ R

co.chain.eps

Similarly,

ch msg_and_write = W @ R W

If an M precedes an @, matching is simultaneously initiated on all receiving processes.

The following chain definition follows a message routed through different processes.

ch msg = W @ R W @ R W @ R

This definition can match 5 different execution graphs as shown below.

route.chain.eps

Note the @ symbols moves the context of the pattern from one process to another. Once matching has been completed on the receiving process(es), it may resume on the writing process where it had been suspended. If this is the case, it is indicated by ``marking'' the point of return before migration with the symbol <:. The symbol :> indicates that the matching should return to the most recent process on which it had been suspended, at the point of suspension. Thus

ch two_bcast = M <: @ R :> M @ R W

mcast.chain.eps

The other directives to the debugger come in the form of filtering and assertions. Often it is the case, that we only would like to consider a subset of events in the trace file for the purpose of behavioral modeling. One way to do it would be filtering the events using event attributes as is done in the context of databases using select statements. We also provide a dynamic select facility at the chain level using the wrt clause.

ch msg = W_north R_south wrt [W_north, R_south];

tells that if the debugger only considers the W_north and R_south events in the trace, then it could see a pattern where a W_north event would be followed along a program order edge by a R_south event. Note that such filtering relaxes the constraint of immediate program order.

This kind of filtering can also be used to check atomicity constraints. Say we expect to see in the program order a W_north event followed by (not necessarily immediately) a R_south event, but without an intervening R_east event. This can be expressed as,

ch msg = W_north R_south wrt [ W_north, R_south, R_east];

Since the filter allows all three event types to be considered for matching, a presence of intervening R_east would led the match to a failure, but the absence will result in a successful match. The figure below shows a section of execution graph that will match the chain description and one that will not.

filter.chain.eps

One can also control the matching based on attributes. One restriction that is imposed to keep the recognition algorithm simple, is that assertions of attributes should only involve events already matched. This ensures that we never discard a event based on some assertion on yet unseen events. The description

ch msg = W_south {x = rpid(W);} R_south {assert spid(R) == x;};

matches a W_south event followed by a R_south event in the same process such that the R event is sent by the process that received the W event. spid and rpid are inherent attributes of each communication events, and refer to the pid of the sender and that of the receiver respectively. A picture of an execution graph is shown below to indicate the filtering that will result during the matching.

assert.chain.eps

As we mentioned before, chain description can be quite coarse. Consider a case, when a process broadcasts a message to all other processes, and depending on the response chooses a recipient for its next message. The user description

ch find_recipient = <: M @ R W @ R :> W @ R;

dag.eps

The first graph is the one that the user expected, and the second graph is a wrong execution where the process does not wait to gather the responses before choosing the actual recipient. Such scatter-gather patterns are common in parallel programs, but cannot be described fully in Ariadne. The reason is simple, we have used augmented regular expression with Push and Pop directives to facilitate specification of trees, however the scatter-gather pattern is a DAG! We will discuss how to handle these kinds of pattern in a two-step matching process, when we discuss the match statement.