Kahn Process Networks and a Reactive Extension - Signal Processing Systems - page 1057

and in [ 38 ] for I/O automata. The operational semantics in terms of I/O automata is
very much like the semantics in Sect. 3 , except that in the I/O-automata semantics,
FIFOs are not modeled explicitly; it is assumed that they are implicit in the transition
system of the processes at the lowest level. This means that the processes will
accept any input at any given time. Composition of networks is then achieved with
synchronous communication. By making channels and their FIFOs more explicit
one can reason about realizations including memory management (FIFO capacities).
KPN is often informally regarded as the upper bound of a hierarchy of data-flow
models, although technically speaking it is not entirely obvious how to compare
data-flow processes based on firing rules with either the denotational or operational
semantics of KPN. The relationship between both types of models is elaborated
in [ 36 ] .
Scheduling and resource management, possibly in a distributed fashion are
important subjects for realizing KPN implementations or simulators. Scheduling
process networks using statically bounded channels is an important contribution
towards this aim by Thomas Parks [ 43 ] , introducing an algorithm that uses bounded
memory if possible. Based on this scheduling policy, a number of tools and libraries
have been developed for executing KPNs. Y API [ 31 ] is a C++ library for designing
stream-processing applications. Ptolemy II [ 33 ] is a framework for codesign using
mixed models of computation. The process-network domain is described in [ 24 ] .
The Distributed Process Networks of [ 55 ] form the computational back end of
the Jade/PAGIS system for processing digital satellite images. [ 49 ] covers an
implementation of process networks in Java. [ 1 ] is another implementation for
digital signal processing. Common among all these implementations is a multi-
threading environment in which processes of the KPN execute in their own thread
of control and channels are allocated a fixed capacity. Semaphores control access to
channels and block the thread when reading from an empty or writing to a full
channel. This raises the possibility of a deadlock when one or more processes
are permanently blocked on full channels. A special thread (preempted by the
other threads) is used to detect a deadlock and initiate a deadlock resolution
procedure when necessary. This essentially realizes the scheduling policy of [ 43 ] .
The algorithm of Parks leaves some room for optimization of memory usage by
careful selection of initial channel capacities (using profiling) and clever selection
of channels when the capacity needs to be increased; see [ 3 ] . [ 3 ] also introduces
causal chains, also used in this chapter to define deadlocks.
It is argued in [ 20 ] as discussed in Sect. 6 that a run-time scheduler for KPN
should include local deadlock detection. Such deadlock detection has subsequently
been implemented in a number of KPN implementations [ 2 , 15 , 27 , 41 ] . To optimize
the process it can be organized in a distributed fashion [ 2 ] or in a hierarchical
way [ 27 ] .
The desire to express non-deterministic behavior and event-based communica-
tion has led to additions to pure data-flow models. Examples are the probes of
[ 31 , 39 ] . Martin [ 39 ] describes an extension of the data-flow model with so-called
probes, the possibility to test whether a channel has data available for reading. This
can be a powerful construct, but it destroys the property of determinacy; the behavior