Kahn process networks [16] is a model of computation that is often used for modeling stream processing applications. In this model, concurrent processes communicate through unidirectional first-in-first-out channels with unbounded capacity. Each of the processes performs sequential computation on its private state space. The computation actions are interleaved with communication actions that read data from input channels and write data to output channels. Read actions are blocking, i.e., a process that reads from an empty channel stalls until the channel has sufficient data to complete the read action. Write actions are non-blocking because the channels have unbounded capacity. A well-known property of a Kahn process network is that it is deterministic, i.e., the stream of data that travels along each channel is determined by the given input data; it does not depend on the order in which the processes are executed. For this reason, an application designer can combine processes that represent stream processing functions into process networks without specifying their order of execution. Moreover, a system designer can exploit the concurrency between the processes by using processing elements that operate in parallel.
In some implementations of Kahn process networks, the blocking read semantic incurs a considerable amount of context switching overhead. Dataflow process networks [15], which are a special case of Kahn process networks, avoid this overhead by transforming the processes into atomic actors that are fired when input data is available. Once an actor has been fired, it cannot stall. If it cannot complete the computation because it requires more input data, then it must save its internal state such that it can resume the computation on the next firing. The literature contains many references to variants of dataflow process networks such as synchronous or static dataflow [7], cyclo-static dataflow [14], and dynamic dataflow [2]. Many commercial vendors offer software packages for modeling signal processing systems based on dataflow process networks. Examples of such packages are SPW [11] and DSP Station [5]. Another example of a software package that is based on the data-flow paradigm is SLAM+C [21] which was developed at Philips Research.
We argue that dataflow process networks are less suited for modeling data-dependent applications because they place the burden of state saving on the application designer rather than on the system designer. Explicit implementation of state saving in a dataflow program is a form of over-specification which can lead to unnecessary computation or communication. The reason for this is that the need for state saving and the implementation of state saving are design decisions. A system designer can avoid the need for state saving by avoiding resource sharing. If a system designer decides to apply resource sharing then an on-line resource scheduler with multi-tasking capabilities can provide automatic state saving. Only in case of resource sharing without multi-tasking capabilities there is a need for explicit state saving. For this reason we resort to the more general model of Kahn process networks which assumes implicit state saving, thereby leaving the use and the implementation of state saving as design decisions to a system designer.
A limitation of Kahn process networks is that they cannot model reactiveness such as user interaction. This is caused by the fact that the absence and the occurrence of non-deterministic events cannot be made known to the processes. Control flow models such as finite state machines provide a solution for this problem by assuming a broadcast mechanism to communicate events in which each actor is sensitive to specific events. These models often contain a global notion of time such that time stamps can be associated with all events which is needed to process them in a correct order. This makes these models less suited for the implementation of computationally intensive applications because the amount of parallelism is limited. Furthermore, the underlying broadcast mechanism of these models is difficult to implement on parallel systems with distributed memory. Examples of software packages supporting control flow modeling are Statecharts [12], Esterel [6], and Polis [1].
The Ptolemy system [10] has been designed to support a heterogeneous mix of models of computation for co-simulation. It attempts to combine the semantics of control and data flow models at their interfaces [3]. Although this is feasible for functional simulation, we argue that this does not allow hardware software co-design because the models of computation are already tuned towards a target implementation. Another approach called Process Coordination Calculus [4] combines data-driven and event-driven processes in a single process network with stream-based, event-based, and register-based communication schemes. A specification consists of a process network and a set of scheduling constraints to ensure deterministic behavior.
To extend the deterministic model of Kahn process networks with non-deterministic events we pursue the approach of Martin [9], who has introduced a communication primitive known as the probe in combination with the model of Communicating Sequential Processes [17]. In this model concurrent processes communicate through unbuffered channels. As a result two communicating processes must complete their communication actions simultaneously. A probe action indicates whether the process on the opposite side of the channel is stalling because it has initiated a communication action that cannot be completed. Martin [13] demonstrates the use of probes to implement channel selection, i.e., selection of one channel out of a set of channels such that the next communication action on the selected channel can be completed. Since channel selection is performed at run-time it allows the modeling of non-deterministic events.
We generalize the notion of probes to buffered channels in order to extend the model of Kahn process networks with channel selection. Although channel selection can be implemented with probe actions, YAPI provides a more abstract operation because we argue that the implementation of channel selection is the concern of a system designer rather than of an application designer. We hide the algorithm that selects a channel when there is more than one candidate from an application designer, because the conditions that determine whether or not a channel is a candidate depend on design decisions such as the scheduling of shared resources, the computation delays, the communication delays, and many more. Since an application designer does not know these design decisions, we do not allow an application designer to control the channel selection algorithm. Therefore, we avoid probe-like constructs in YAPI that allow application designers to implement their own selection algorithm. We claim that the abstraction from these implementation details results in reusable applications that can be mapped onto different target architectures.