Kahn process networks
Encyclopedia
Kahn process networks is a distributed
model of computation
(MoC) where a group of deterministic sequential processes
are communicating through unbounded FIFO
channels. The resulting process network exhibits deterministic behavior that does not depend on the various computation or communication delays. The model was originally developed for modeling distributed systems but has proven its convenience for modeling signal processing
systems. As such, KPNs have found many applications in modeling embedded systems, high-performance computing
systems, and other computational tasks. KPNs were first introduced by Gilles Kahn
.
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 element
s, or alternatively called token
s, 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. 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.
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 that the process is executed 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.
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.
if it has at most 
unconsumed tokens for any possible execution. A KPN is strictly bounded by 
if all channels are strictly bounded by 
.
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:
Hence, timing of the processes does not affect outputs of the system.
of events inside a signal. However, there is no order relation between events in different signals. Thus, KPNs are only partially ordered, which classifies them as untimed model.
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 a 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.
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
model of computation
Model of computation
In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
(MoC) where a group of deterministic sequential processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
are communicating through unbounded FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
channels. The resulting process network exhibits deterministic behavior that does not depend on the various computation or communication delays. The model was originally developed for modeling distributed systems but has proven its convenience for modeling signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
systems. As such, KPNs have found many applications in modeling embedded systems, high-performance computing
High-performance computing
High-performance computing uses supercomputers and computer clusters to solve advanced computation problems. Today, computer systems approaching the teraflops-region are counted as HPC-computers.-Overview:...
systems, and other computational tasks. KPNs were first introduced by Gilles Kahn
Gilles Kahn
Gilles Kahn was a French computer scientist. He notably introduced Kahn process networks as a model for parallel processing....
.
Execution model
KPN is a common model for describing signal processingSignal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
systems where infinite streams of data are incrementally transformed by processes executing in sequence or parallel. Despite parallel processes, multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
or parallelism
Parallelism
Parallelism may refer to:* Angle of parallelism, the angle at one vertex of a right hyperbolic triangle that has two hyperparallel sides* Conscious parallelism, price-fixing between competitors in an oligopoly that occurs without an actual spoken agreement between the parties* Parallel computing,...
are not required for executing this model.
In a KPN, processes communicate via unbounded FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
channels. Processes read and write atomic data element
Data element
In metadata, the term data element is an atomic unit of data that has precise meaning or precise semantics. A data element has:# An identification such as a data element name# A clear data element definition# One or more representation terms...
s, or alternatively called token
Token
A token is an object of value, and may refer to:* In logic, computational linguistics, and information retrieval, a token is an instance of a type; see Type-token distinction...
s, 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. 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
Petri net
A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
shown on the right. The single token in the PE resource place forbids that the process is executed 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
- Active; the process computes or writes data
- Wait; the process is blocked (waiting) for data
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.
Boundedness of channels
A channel is strictly bounded by if it has at most unconsumed tokens for any possible execution. A KPN is strictly bounded by if all channels are strictly bounded by .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:
- FIFO bounds can be mathematically derived in design to avoid FIFO overflows. This is however not possible for all KPNs. It is an undecidable problem to test whether a KPN is strictly bounded by
. Moreover, in practical situations, the bound may be data dependent. - FIFO bounds can be grown on demand (Parks, 1995)
- Blocking writes can be used so that a process blocks if a FIFO is full. This approach may unfortunately lead to an artificial deadlock unless the designer properly derives safe bounds for FIFOs (Parks, 1995). Local artificial detection at run-time may be necessary to guarantee the production of the correct output (Geilen&Basten, 2003)
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:- processes
- the network
- initial tokens
Hence, timing of the processes does not affect outputs of the system.
Monotonicity
KPN processes are monotonic, which means that they only need partial information of the input stream in order to produce partial information of the output stream. Monotonicity allows parallelism. In a KPN there is a total orderTotal order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
of events inside a signal. However, there is no order relation between events in different signals. Thus, KPNs are only partially ordered, which classifies them as 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
Leiden University
Leiden University , located in the city of Leiden, is the oldest university in the Netherlands. The university was founded in 1575 by William, Prince of Orange, leader of the Dutch Revolt in the Eighty Years' War. The royal Dutch House of Orange-Nassau and Leiden University still have a close...
accepts sequential programs written in C and generates a corresponding KPN. This KPN could, for example, be used to map the KPN onto a FPGA-based platform systematically.
The Ambric
Ambric
Ambric-architecture processors, are developed and marketed by a division of Nethra, a fabless semiconductor company based in Santa Clara, California. Nethra purchased the Ambric technology in early 2009. Ambric the company was founded in 2003 and the current team, all from the original startup,...
Am2045 massively parallel processor array
Massively parallel processor array
A Massively Parallel Processor Array is a type of integrated circuit which has a massively parallel array of hundreds or thousands of CPUs and RAM memories. These processors pass work to one another through a reconfigurable interconnect of channels...
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.