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

Kahn Process Networks and a Reactive
Extension
Marc Geilen and Twan Basten
Abstract Kahn and MacQueen have introduced a generic class of determinate
asynchronous data-flow applications, called Kahn Process Networks (KPNs) with
an elegant mathematical model and semantics in terms of Scott-continuous func-
tions on data streams together with an implementation model of independent
asynchronous sequential programs communicating through FIFO buffers with
blocking read and non-blocking write operations. The two are related by the Kahn
Principle which states that a realization according to the implementation model
behaves as predicted by the mathematical function. Additional steps are required
to arrive at an actual implementation of a KPN to take care of scheduling of
independent processes on a single processor and to manage communication buffers.
Because of the expressiveness of the KPN model, buffer sizes and schedules cannot
be determined at design time in general and require dynamic run-time system
support. Constraints are discussed that need to be placed on such system support so
as to maintain the Kahn Principle. We then discuss a possible extension of the KPN
model to include the possibility for sporadic, reactive behavior which is not possible
in the standard model. The extended model is called Reactive Process Networks.
We introduce its semantics, look at analyzability and at more constrained data-flow
models combined with reactive behavior.
M. Geilen ( )
Eindhoven University of Technology, Den Dolech 2, Eindhoven, The Netherlands
e-mail: [e-mail]
T. Basten
Eindhoven University of Technology and TNO-ESI,
Den Dolech 2, Eindhoven, The Netherlands
e-mail: [e-mail]