Kahn Process Networks and Reactive Process Networks

Kahn Process Networks (KPN) ^[1][2] are a model of concurrent computation on data streams. They combine fully parallel execution with functional determinism, i.e., independent of scheduling order, or relative processing speeds, the produced output streams are uniquely defined. This alleviates common problems in parallel programming, for instance, using threads tpbcite key=”Lee06″]. Kahn Process Networks can be implemented as a collection of sequential programs that do not share any data with each other, but, instead, communicate only by exchanging streams of data in First-In-First-Out order with blocking read operations, i.e., if a process commits to reading data from an input stream it blocks until data arrives on the input. It is not able to select input data based on the time of arrival. FIFO storage is implemented for the channels connecting processes. The FIFOs can be bounded, but only if this does not introduce deadlocks (although in general this is an undecidable problem).

Kahn Process Networks have an elegant mathematical semantics in the form of a function that maps input streams to output streams, defined as a least fixed-point of an overall network function on a complete partial order ^[3]. It is also useful to have an operational mathematical semantics, because it is closer to (the execution of) an implementation of a KPN. Such an operational semantics is presented in ^[4], and it is shown that it corresponds to the denotational semantics.

A drawback of the functional determinism of KPN is that they are prohibited from effectively responding to events, i.e., to unanticipated input, because the blocking read cannot be used for that. The Reactive Process Networks ^[5] model presents an extension of KPN with the ability to respond to events and to separate the event handling from the functional determinate stream processing behavior..

The operational semantics of KPN or RPN can serve as a reference to implementing KPN or RPN. The operational semantics, however, uses unbounded FIFO buffers. It is often convenient to implement FIFO buffers of a fixed size. On the other hand, determining the required size is an undecidable problem. This introduces the need for online buffer memory management and the handling of artificial deadlocks that may arise due to buffers being insufficienty large. Only if such an online memory management strategy is implements carefully, the resulting program behaves as prescribed by the semantics ^[6].

References

1. G. Kahn (1974): The Semantics of a Simple Language for Parallel Programming. In: Rosenfeld, J. L. (Ed.): Information Processing 74: Proceedings of the IFIP Congress 74, Stockholm, Sweden, August 1974, pp. 471–475, North-Holland, Amsterdam, Netherlands, 1974.
2. G. Kahn and D. B. MacQueen (1977): Coroutines and Networks of Parallel Processes. In: IFIP 77, pp. 993–998, North-Holland, Amsterdam, 1977.
3. G. Kahn (1974): The Semantics of a Simple Language for Parallel Programming. In: Rosenfeld, J. L. (Ed.): Information Processing 74: Proceedings of the IFIP Congress 74, Stockholm, Sweden, August 1974, pp. 471–475, North-Holland, Amsterdam, Netherlands, 1974.
4. Marc Geilen and Twan Basten (2019): Kahn Process Networks and a Reactive Extension. In: Bhattacharyya, Shuvra S.; Deprettere, Ed F.; Leupers, Rainer; Takala, Jarmo (Ed.): Handbook of Signal Processing Systems, pp. 865–906, Springer International Publishing, Cham, 2019, ISBN: 978-3-319-91734-4.
5. Marc Geilen and Twan Basten (2019): Kahn Process Networks and a Reactive Extension. In: Bhattacharyya, Shuvra S.; Deprettere, Ed F.; Leupers, Rainer; Takala, Jarmo (Ed.): Handbook of Signal Processing Systems, pp. 865–906, Springer International Publishing, Cham, 2019, ISBN: 978-3-319-91734-4.
6. Marc Geilen and Twan Basten (2003): Requirements on the Execution of Kahn Process Networks. In: Degano, Pierpaolo (Ed.): Programming Languages and Systems, pp. 319–334, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, ISBN: 978-3-540-36575-4.

Selected Related Publications

@inbook{GB19,

title = {Kahn Process Networks and a Reactive Extension},

author = {Marc Geilen and Twan Basten},

editor = {Shuvra S. Bhattacharyya and Ed F. Deprettere and Rainer Leupers and Jarmo Takala},

url = {https://doi.org/10.1007/978-3-319-91734-4_24},

doi = {10.1007/978-3-319-91734-4_24},

isbn = {978-3-319-91734-4},

year  = {2019},

date = {2019-01-01},

urldate = {2019-01-01},

booktitle = {Handbook of Signal Processing Systems},

pages = {865–906},

publisher = {Springer International Publishing},

address = {Cham},

keywords = {},

pubstate = {published},

tppubtype = {inbook}

}

@inproceedings{GB03,

title = {Requirements on the Execution of Kahn Process Networks},

author = {Marc Geilen and Twan Basten},

editor = {Pierpaolo Degano},

doi = {10.1007/3-540-36575-3_22},

isbn = {978-3-540-36575-4},

year  = {2003},

date = {2003-01-01},

urldate = {2003-01-01},

booktitle = {Programming Languages and Systems},

pages = {319–334},

publisher = {Springer Berlin Heidelberg},

address = {Berlin, Heidelberg},

abstract = {Kahn process networks (KPNs) are a programming paradigm suitable for streaming-based multimedia and signal-processing applications. We discuss the execution of KPNs, and the criteria for correct scheduling of their realisations. In [12], Parks shows how process networks can be scheduled in bounded memory; the proposed method is used in many implementations of KPNs. However, it does not result in the correct behaviour for all KPNs. We investigate the requirements for a scheduler to guarantee both correct and bounded execution of KPNs and present an improved scheduling strategy that satisfies them.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{KM77,

title = {Coroutines and Networks of Parallel Processes},

author = {G. Kahn and D. B. MacQueen},

year  = {1977},

date = {1977-01-01},

urldate = {1977-01-01},

booktitle = {IFIP 77},

pages = {993–998},

publisher = {North-Holland, Amsterdam},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

@inproceedings{Kah74,

title = {The Semantics of a Simple Language for Parallel Programming},

author = {G. Kahn},

editor = {J. L. Rosenfeld},

year  = {1974},

date = {1974-01-01},

urldate = {1974-01-01},

booktitle = {Information Processing 74: Proceedings of the IFIP Congress 74, Stockholm, Sweden, August 1974},

pages = {471–475},

publisher = {North-Holland, Amsterdam, Netherlands},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}