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 [3]. 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 [1]. 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 [4] 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 [5].

Selected Related Publications

  • [DOI] M. Geilen and T. Basten, “Requirements on the execution of kahn process networks,” in Programming languages and systems, Berlin, Heidelberg, 2003, p. 319–334.
    [Bibtex] 
    @InProceedings{GB03,
author="Geilen, Marc
and Basten, Twan",
editor="Degano, Pierpaolo",
title="Requirements on the Execution of Kahn Process Networks",
booktitle="Programming Languages and Systems",
year="2003",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="319--334",
doi={10.1007/3-540-36575-3_22},
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.",
isbn="978-3-540-36575-4"
}
  • [DOI] M. Geilen and T. Basten, “Kahn process networks and a reactive extension,” in Handbook of signal processing systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds., Cham: Springer international publishing, 2019, p. 865–906.
    [Bibtex] 
    @Inbook{GB19,
author="Geilen, Marc
and Basten, Twan",
editor="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Leupers, Rainer
and Takala, Jarmo",
title="Kahn Process Networks and a Reactive Extension",
bookTitle="Handbook of Signal Processing Systems",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="865--906",
isbn="978-3-319-91734-4",
doi="10.1007/978-3-319-91734-4_24",
url="https://doi.org/10.1007/978-3-319-91734-4_24"
}

References

[1] G. Kahn, “The semantics of a simple language for parallel programming,” in Information processing 74: proceedings of the IFIP congress 74, stockholm, sweden, august 1974, 1974, p. 471–475.
[Bibtex]
@InProceedings{Kah74,
author = {G. Kahn},
title = {The Semantics of a Simple Language for Parallel Programming},
booktitle = {Information Processing 74: Proceedings of the {IFIP} Congress 74, Stockholm, Sweden, August 1974},
year = {1974},
editor = {J.L. Rosenfeld},
pages = {471--475},
publisher = {North-Holland, Amsterdam, Netherlands},
}
[2] G. Kahn and D. B. MacQueen, “Coroutines and networks of parallel processes,” in Ifip 77, 1977, p. 993–998.
[Bibtex]
@INPROCEEDINGS{KM77,
author={Kahn, G. and D.B. MacQueen},
booktitle={IFIP 77},
title={Coroutines and Networks of Parallel Processes},
year={1977},
volume={},
number={},
pages={993--998},
publisher = "North-Holland, Amsterdam",
}
[3] [doi] E. A. Lee, “The problem with threads,” Computer, vol. 39, iss. 5, pp. 33-42, 2006.
[Bibtex]
@ARTICLE{Lee06,
author={Lee, E.A.},
journal={Computer},
title={The problem with threads},
year={2006},
volume={39},
number={5},
pages={33-42},
doi={10.1109/MC.2006.180}
}
[4] [doi] M. Geilen and T. Basten, “Kahn process networks and a reactive extension,” in Handbook of signal processing systems, S. S. Bhattacharyya, E. F. Deprettere, R. Leupers, and J. Takala, Eds., Cham: Springer international publishing, 2019, p. 865–906.
[Bibtex]
@Inbook{GB19,
author="Geilen, Marc
and Basten, Twan",
editor="Bhattacharyya, Shuvra S.
and Deprettere, Ed F.
and Leupers, Rainer
and Takala, Jarmo",
title="Kahn Process Networks and a Reactive Extension",
bookTitle="Handbook of Signal Processing Systems",
year="2019",
publisher="Springer International Publishing",
address="Cham",
pages="865--906",
isbn="978-3-319-91734-4",
doi="10.1007/978-3-319-91734-4_24",
url="https://doi.org/10.1007/978-3-319-91734-4_24"
}
[5] [doi] M. Geilen and T. Basten, “Requirements on the execution of kahn process networks,” in Programming languages and systems, Berlin, Heidelberg, 2003, p. 319–334.
[Bibtex]
@InProceedings{GB03,
author="Geilen, Marc
and Basten, Twan",
editor="Degano, Pierpaolo",
title="Requirements on the Execution of Kahn Process Networks",
booktitle="Programming Languages and Systems",
year="2003",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="319--334",
doi={10.1007/3-540-36575-3_22},
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.",
isbn="978-3-540-36575-4"
}