Statically scheduled Process Networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Statically scheduled Process Networks

Résumé

Les Graphes d'evenement (EG) forment un sous-ensemble strict des Reseaux de Petri. Etant denues de tout choix non-deterministe ils jouent un role fondamental dans la Theorie de l'Ordonnancement. Il a ete etabli dans le passe que, sous des hypotheses naturelles sur la forme structurelle des graphes, on savait construire une version temporisee de tels graphes d'evenement (TEG), qui admettait un ordonnancement finalement regulier (en terms techniques: ultimement k-periodique). Plus recemment il a ete propose d'utiliser ces formulations d'ordonnancement regulier comme types syntaxiques pour la conception de systemes dits N-synchrones. Ce typage reste essentiellement fourni par l' utilisateur. Par ailleurs des extensions aux EGs ont aussi ete proposees dans le passe, afin d'introduire une ``certaine dose'' de controle (if-then-else), mais sans reintroduire toute la generalite des RdP. ceci repose sur des noeuds de controle merge et select, dont les branchements sont entierement commandes par des conditions locales, distinctes des apparitions de valeurs aux canaux d'entree, ce qui est dans la droite tradition des Reseaux de Kahn. Mais ces conditions sont en generale abstraites par cette propriete, ce qui introduit des questions de famine ou de congestion des canaux qui ne peuvent alors etre resolues. Dans ce papier nous introduisons une notion de conditions de branchement k-periodiques sur ces noeuds Merge/Select. Le resultat prinipal est que le probleme de l'egalisation des flots dans ce modele redevient decidable, et qu'on peut y redefinir une notion d'ordonnancement k-periodique qui combine la regularite ``en profondeur'' des latences avec celle ``en largeur'' des branchements alternatifs. Nous nommons ce modele Graphes d'Evenement Kahn-augmentes (KEG). Il y a de nombreuses applications potentielles a ce m odele KEG, en particulier dans le design de Systemes-sur-puce (SoC) comprenant un Reseau-sur-puce (NoC). Dans des cas ou les traffics peuvent etre previsibles (statiquement), le modele permet de representer l'entrelacement des routages afin de partager optimalement des sections de communication et acheminer les donnees sur un mode regulier. Il peut aussi permettre de trouver ces ordonnancements de trafic.
Fichier principal
Vignette du fichier
popl2008RR.pdf (462.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00168757 , version 1 (14-09-2007)
inria-00168757 , version 2 (14-09-2007)

Identifiants

  • HAL Id : inria-00168757 , version 1

Citer

Julien Boucaron, Benoît Ferrero, Jean-Vivien Millo, Robert de Simone. Statically scheduled Process Networks. [Research Report] 2007. ⟨inria-00168757v1⟩
194 Consultations
230 Téléchargements

Partager

Gmail Facebook X LinkedIn More