Kahn process networks
A Kahn process network (KPN, or process network) is a distributed "model of computation" in which a group of deterministic sequential processes communicate through unbounded first in, first out channels. The model requires that reading from a channel is blocking while writing is non-blocking. Due to these key restrictions, the resulting process network exhibits deterministic behavior that does not depend on the timing of computation nor on communication delays. Kahn process networks were originally developed for modeling parallel programs, but have proven convenient for modeling embedded systems, high-performance computing systems, signal processing systems, stream processing  systems, dataflow programming languages, and other computational tasks. KPNs were introduced by Gilles Kahn in 1974. Execution model. KPN is a common model for describing signal processing systems where infinite streams of data are incrementally transformed by processes executing in sequence or parallel. Despite parallel processes, multitasking or parallelism are not required for executing this model. In a KPN, processes communicate via unbounded FIFO channels. Processes read and write atomic data elements, alternatively called tokens, from and to channels. Writing to a channel is non-blocking, i.e. it always succeeds and does not stall the process, while reading from a  channel is "blocking", i.e. a process that reads from an empty channel will stall and can only continue when the channel contains sufficient data items ("tokens"). Processes are not allowed to test an input channel for existence of tokens without consuming them. A FIFO cannot be consumed by multiple processes, nor can multiple processes write to a single FIFO. Given a specific input (token) history for a process, the process must be deterministic so that it always produces the same outputs (tokens). Timing or execution order of processes must not affect the result and therefore testing input channels for  tokens is forbidden. Process firing semantics as Petri nets. Assuming process "P" in the KPN above is constructed so that it first reads data from channel "A", then channel "B", computes something and then writes data to channel "C", the execution model of the process can be modeled with the Petri net shown on the right. The single token in the "PE resource" place forbids the process from executing simultaneously for different input data. When data arrives at channel "A" or "B", tokens are placed into places "FIFO A" and "FIFO B" respectively. The transitions of the Petri net are  associated with the respective I/O operations and computation. When the data has been written to channel "C", "PE resource" is filled with its initial marking again allowing new data to be read. Process as a finite state machine. A process can be modeled as a finite state machine that is in one of two states: Assuming the finite state machine reads program elements associated with the process, it may read three kinds of tokens, which are "Compute", "Read" and "Write token". Additionally, in the "Wait" state it can only come back to "Active" state by reading a special "Get  token" which means the communication channel associated with the wait contains readable data. Properties. Boundedness of channels. A channel is "strictly bounded" by formula_1 if it has at most formula_1 unconsumed tokens for any possible execution. A KPN is "strictly bounded" by formula_1 if all channels are strictly bounded by formula_1. The number of unconsumed tokens depends on the execution order (scheduling) of processes. A spontaneous data source could produce arbitrarily many tokens into a channel if the scheduler would not execute processes consuming those tokens. A real application can not have unbounded FIFOs and therefore scheduling and maximum capacity  of FIFOs must be designed into a practical implementation. The maximum capacity of FIFOs can be handled in several ways: Closed and open systems. A "closed KPN" has no external input or output channels. Processes that have no input channels act as data sources and processes that have no output channels act as data sinks. In an "open KPN" each process has at least one input and output channel. Determinism. Processes of a KPN are deterministic. For the same input history they must always produce exactly the same output. Processes can be modeled as sequential programs that do reads and  writes to ports in any order or quantity as long as determinism property is preserved. As a consequence, KPN model is deterministic so that following factors entirely determine outputs of the system: Hence, timing of the processes does not affect outputs of the system. Monotonicity. KPN processes are "monotonic". Reading more tokens can only lead to writing more tokens. Tokens read in the future can only affect tokens written in the future. In a KPN there is a total order of events inside a signal. However, there is no order relation between events in different signals. Thus, KPNs are only  partly ordered, which classifies them as an untimed model. Applications. Due to its high expressiveness and succinctness, KPNs as underlying the model of computation are applied in several academic modeling tools to represent streaming applications, which have certain properties (e.g., dataflow-oriented, stream-based). The open source Daedalus framework maintained by Leiden Embedded Research Center at Leiden University accepts sequential programs written in C and generates a corresponding KPN. This KPN could, for example, be used to map the KPN onto an FPGA-based platform systematically. The Ambric Am2045 massively parallel processor array is a KPN implemented in actual silicon . Its 336 32-bit processors are connected by a programmable interconnect of dedicated FIFOs. Thus its channels are strictly bounded with blocking writes.