Kahn Process Networks

Process Networks is a Model of Computation (MoC) that was originally developed for modeling distributed systems but has proven its convenience for modeling signal processing systems. Process Networks are also called Kahn Process Networks after G. Kahn who first introduced them in his thesis (see [Kahn, 1974]). It is a natural model for describing signal processing systems where infinite streams of data are incrementally transformed by processes executing in sequence or parallel. Nevertheless, and as pointed out by [Lee and Park, 1995], this model of computation does not require multitasking or parallelism and usually neither infinite queues; it is in fact usually more efficient than comparable methods in functional languages. Process Networks have found many applications in modeling embedded systems as it is typical for embedded systems to be designed to operate infinitely with limited resources.

Figure 1.4: A Kahn Process Network

Commercial systems like SPW from Alta Group of Cadence, COSSAP from Synopsys, the DSP Station from Mentor Graphics, Hypersignal from Hyperception or Simulink by Mathworks and research software like Khoros from the University of New Mexico and Ptolemy from the Univ. of California at Berkeley are all based on variants of the Process Network model. Departing from the original Process Networks by Kahn, a number of more specific models have been derived. In this section we will give an introduction to the basic Kahn's Process Networks and will leave the more specific models for next sections.

Process Networks are directed graphs where nodes represent Processes and arcs are infinite FIFO queues that connect these processes (see figure 1.4). Writing to a channel is non blocking (it always succeeds immediately) but reading is blocking. If a process tries to read from an empty input it is suspended until it has enough input data and the execution context is switched to another process or level. A process may not ``test'' channel for presence of data. At any given point a process is either ``enabled'' or ``blocked'' waiting for data on one of its channels. It can not be waiting for data on one or another input channel.

In Kahn Process Networks processes produce tokens (data elements) that are sent along a communication channel and consumed by the destination process. Communication channels are the only way processes may exchange information. KPN systems are determinate: the history of tokens produced/consumed does not depend on execution order. A stream is a finite or infinite sequence of data elements or tokens X=[x1,x2...] where xi is a particular token. A process is in this sense a functional mapping from input to output streams.

As pointed out by [Parks, 1995] a parallelism can be made with Turing Machines: a Process Network can be seen as a set of Turing machines connected with one-way tapes, each machine operating on its own tape. Because of the ``halting problem'' we cannot tell in a finite time whether an arbitrary Turing machine program will halt, and the same is true for Process Networks. Two properties of Process Networks are related to this problem: termination and boundness. These properties are undecidable in finite time for the general case but, under some restrictions, we can study and classify PN before execution.

According to [Webb et al., 1999] interesting properties of process networks that make them a suitable model for computation are:

• Each process is a sequential program that consumes tokens from its inputs queues and produces tokens to the output queues.
• Each queue has one source and one destination.
• The network has no global data
• Each process is blocked when it tries to read from a a channel with insufficient data. The process resumes when there is enough data again.
• Although writing is generally non-blocking, blocking can be used to be able to use bounded queues.
• Concurrency can be implemented safely.
• Scheduling is transparent to the user
• Hierarchy or scalability.