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, 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.
Type de document :
[Research Report] RR-6289, INRIA. 2007, pp.26
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 14 septembre 2007 - 11:58:16
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:47:35


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers