1.6 Mapping

The implementation of read, write, select, and execute actions are a concern of a system designer. Note that different read, write, select, and execute actions may be implemented in different ways, for instance, because some actions are executed in hardware and other actions are executed in software.

One of the design decisions is to determine the size of the fifos in order to obtain an implementation in finite memory. Deadlock can occur if they are too small, because the size of the fifos limits the set of reachable schedules. Going from unbounded to bounded fifos changes Axiom 1.5.1 such that for all channels it holds that at any time a write action and a read action are not blocked simultaneously, the number of produced tokens minus the number of consumed tokens is bounded by the size of the channel, and the functionality is first-in-first-out. Formally, this is denoted as follows.

Axiom 1.6.1   Let $(p,m(p))$ be a channel of size $s$. Then the following invariants hold

• $(n(p) = 0) \vee (n(m(p)) = 0)$,
• $0 \leq c(p) - c(m(p)) \leq s$, and
• $\forall_{0 \leq i < c(m(p))} (v(m(p),i)=v(p,i)).$

The read and write actions can be implemented such that the number of communicated tokens can exceed the size of the fifo. To this end, these actions have to be preempted when the number of committed tokens is not present or does not fit in the fifo.

Another design decision is the implementation of the notion of `eventually' in the select function. For process networks that cannot be scheduled off-line, for instance due to data-dependent functionality, we have chosen to strengthen the expression $\Diamond (N_s+n_s \leq c(m(p_s)))$ in the postcondition of the select function to $c(p_s)+n_s \leq c(m(p_s))+n(m(p_s))$. We obtain the number of committed tokens $n(m(p_s))$ through the number of tokens of the read and write actions, i.e., the initiation of a read or write action of $n$ tokens sets a commitment that decreases during transfer of the tokens. As a result the scheduling horizon is limited to one communication action, i.e., a select action takes one incomplete read or write action into account. Again this introduces deadlock if the size of the fifos is too small. Note that if the process network is a dataflow process network, then the firing rules can be implemented with select actions. In that case the read and write actions do not have to stall because the firing rules satisfy Axiom 1.6.1.

The above-mentioned design decisions are used in the YAPI run-time library that is used by application designers to simulate the functionality of a process network on a workstation. Other YAPI implementations, in particular those proposed in COSY [22] and SPADE [20], target mixed hardware and software realizations in systems-on-chip. In the initial stage of the design process, these implementations are abstract performance models to allow fast design space exploration. Subsequently, these performance models are refined into cycle-accurate models to allow final implementation.