Requirements on the Execution of Kahn Process Networks

Key words: Kahn process networks, Kahn Principle, dynamic scheduling, deadlock resolution, multi-processor architectures, media processing, signal processing, streaming

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 [1], 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.

1. T.M. Parks. Bounded Scheduling of Process Networks. PhD thesis, University of California, EECS Dept., Berkeley, CA, December 1995.

(pdf version of the complete paper)

Back to the list of publications.