Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation

Statically scheduled Process Networks

Julien Boucaron 1 Benoît Ferrero 1 Jean-Vivien Millo 1 Robert de Simone 1
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Event/Marked Graphs (EG) form a strict subset of Petri Nets. They are fundamental models in Scheduling Theory, mostly because of their absence of alternative behaviors (or conflict-freeness). It was established in the past that, under broad structural conditions, behavior of Timed Event Graphs (TEG) becomes utterly regular (technically speaking: “ultimately k-periodic”). More recently it has been proposed to use this kind of regular schedulings as syntactic types for so-called N-synchronous processes. These types remained essentially user-provided. Elsewhere there have been proposals for adding control in a “light fashion” to TEGs, not as general Petri Nets, but with the addition of Merge/Select nodes switching the data flows. This was much in the spirit of Kahn process networks [8, 9]. But usually the streams of test values governing the switches are left unspecified, which may introduce phenomena of congestion or starvation in the system, as token flow preservation becomes an issue. In the present paper we suggest to restrict the Merge/Select condition streams to (binary) k-periodic patterns as well, and to study their relations with the schedules constructed as before for TEGs, but on the extended model. We call this model Kahn-extended Event Graphs (KEG). The main result is that flow preservation is now checkable (by abstraction into another model of Weighted Marked Graphs, called SDF in the literature). There are many potential applications of KEG models, as for instance in modern Systems-on-Chip (SoC) comprising on-Chip networks. Communication links can then be shared, and the model can represent the (regular) activity schedules of the computing as well as the communicating components, after a strict scheduling has been found. They can also be used as a support to help find the solution.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, September 14, 2007 - 11:58:16 AM
Last modification on : Friday, January 21, 2022 - 3:15:49 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:47:35 PM


Files produced by the author(s)


  • HAL Id : inria-00168757, version 2


Julien Boucaron, Benoît Ferrero, Jean-Vivien Millo, Robert de Simone. Statically scheduled Process Networks. [Research Report] RR-6289, INRIA. 2007, pp.26. ⟨inria-00168757v2⟩



Record views


Files downloads