Oliver Marchetti
LIP6 - Paris


Titre :  Problèmes de  débit et de  dimensionnement des mémoires  pour systèmes
        embarqués.

Mots  clefs :  Réseaux de  Petri, Graphes  d'événements  généralisés temporisés, Vivacité,
              Dimensionnement, Débit, Optimisation.



En raison  du coût élevé du  silicium, les méthodes de  conception des systèmes
embarqués  représentent  un  enjeu  industriel  majeur  auprès  des  différents
constructeurs.   L'une des  tâches du  concepteur consiste  alors à  définir un
dimensionnement  des mémoires  d'une application  conférant à  l'application un
certain débit tout en minimisant la surface totale de mémoire.

Nous modélisons  ce problème bi-critère  en utilisant les  graphes d'événements
généralisé temporisés (sous-classe des réseaux de Petri). Nous montrons dans un
premier temps que le problème traité est NP-difficile.

Afin  de contourner  les difficultés  algorithmiques inhérentes  au  modèle des
graphes d'événements généralisés temporisés, nous étudions le problème du débit
maximum intrinsèque.  Ce problème consiste à déterminer un marquage initial des
places du  réseau qui soit minimum  et qui permet aux transitions du graphe
d'atteindre  le  débit  maximum   intrinsèque.  Nous  proposons  un  algorithme
polynomial 2-approché permettant de résoudre ce problème.

Enfin, nous présentons de manière intuitive un algorithme polynomial pour
la résolution du problème du  débit maximum  intrinsèque pour les  circuits de
taille deux.