Skip to Main content Skip to Navigation

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, Laboratoire I3S - 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.
Document type :
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, May 26, 2008 - 9:13:46 AM
Last modification on : Saturday, June 25, 2022 - 10:59:00 PM
Long-term archiving on: : Thursday, September 23, 2010 - 4:39:04 PM


Files produced by the author(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⟩



Record views


Files downloads