Olivier MARCHETTI
Université PARIS VI
LIP6 - Pôle ASIM

Titre : Analyse et résultats sur le problème du dimensionnement des 
        mémoires sur des systèmes embarqués.

Mots clefs : Réseaux de Pétri, Graphes d'événements généralisés, Vivacité,
             Dimensionnement, Optimisation.


La réalisation d'un système embarqué passe par la modélisation des
différents processus qui le composent et des buffers qui stockent les
données inter-processus. Cette modélisation peut se faire via un graphe
d'événements généralisé (Classe particulière des Réseaux de Pétri)
où les transitions modélisent les processus du systèmes et les places
représentent les buffers. En raison du cout actuel des mémoires,
dimensionner les buffers de manière optimale est un problème crucial.
Il convient donc de déterminer un dimensionnement optimal des buffers
tout en garantissant l'absence de blocage du système lié à un éventuel
sous-dimensionnement.

L'absence de blocage dans ce type de système se caractérise par la
propriété de vivacité du graphe d'événements associé. Nous présentons
pour cette classe de réseaux de Pétri une transformation polynomiale
permettant d'obtenir une condition suffisante de vivacité calculable
en temps polynomial.

Après avoir caractérisé la notion de limitation d'une place (i.e.
dimensionnement d'une mémoire), nous exposerons un algorithme polynomial
qui étant donné un graphe d'événements généralisé où chaque place est 
limitée à sa capacité théorique minimale construit un marquage initial 
de telle sorte que la propriété de vivacité soit vérifiée.