Kahn-extended Event Graphs

Julien Boucaron 1 Anthony Coadou 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 : Process Networks have long been used as formal Models of Computation in the design of dedicated hardware and software embedded systems and Systems-on-Chip. Choice-less models such as Marked/Event Graphs and their Synchronous Data Flow extensions have been considered to support periodic scheduling analysis. Those models do not hide dependency informations like regular sequential languages: they capture the communication topology through point-to-point channels. Those models are concurrent, formally defined, have a clear semantic but are limited due to static point-to-point channels. Then, further extensions such as Cyclo-Static Data Flow or Boolean-controlled Dataflow (BDF) graphs introduced routing switches, allowing internal choices while preserving conflict-freeness, in the tradition of Kahn Process Networks. We introduce a new model, which we term Kahn-extended Event Graphs (KEG). It can be seen as a specialization of both Cyclo-Static and BDF processes. It consists merely in the addition of Merge/Select routing nodes to former Marked/Event Graphs; but, most importantly, these new nodes are governed by explicit (ultimately periodic) binary-word switching patterns for routing directions. We introduce identities on Merge/Select expressions, and show how they build a full axiomatization for the flow-equivalence between the computation nodes. The transformations carry a strong intuitive meaning, as they correspond to sharing/unsharing the interconnect links. Such interconnect defines each time a precise Network-on-Chip topology, and the switching patterns drive the traffic. One can also compute the buffering space actually required at the various fifo locations. The example of a Sobel edge filter is discussed to illustrate the importance of this model.
Type de document :
[Research Report] RR-6541, INRIA. 2008
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 26 mai 2008 - 09:13:46
Dernière modification le : jeudi 11 janvier 2018 - 16:13:57
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 16:39:04


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00281559, version 3



Julien Boucaron, Anthony Coadou, Benoît Ferrero, Jean-Vivien Millo, Robert De Simone. Kahn-extended Event Graphs. [Research Report] RR-6541, INRIA. 2008. 〈inria-00281559v3〉



Consultations de la notice


Téléchargements de fichiers