Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00281559
Contributor : Rapport de Recherche Inria <>
Submitted on : Monday, May 26, 2008 - 9:13:46 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:21 PM
Document(s) archivé(s) le : Thursday, September 23, 2010 - 4:39:04 PM

Files

RR-6541.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00281559, version 3

Collections

Citation

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⟩

Share

Metrics

Record views

403

Files downloads

384