LIP6 2002/024

• Rapports de recherche
  Etude d'un problème de minimisation de buffer pour la conception de systèmes embarqués
• A. Munier-Kordon, J.-B. Note
• 18 pages - 11/10/2002- document en - http://www.lip6.fr/lip6/reports/2002/lip6.2002.024.pdf - 216 Ko
• Contact : Alix.Munier (at) nulllip6.fr
• Ancien Thème : ASIM
Soient n tâches composées chacunes d'un ensemble d'opérations séquentielles et un ensemble de buffers B: chacun d'eux est défini entre deux tâches Ti-_Tj, possède un poids w(b) et est géré comme une file FIFO. Un ensemble d'opérations de Ti (resp. Tj) écrivent (resp. lisent) une donnée dans le buffer b. Les lectures et écritures dans les buffers génèrent des contraintes de précédence entre les opérations. La limitation de la taille des buffers génère un autre ensemble de contraintes de précédence, et il peut y avoir apparition de circuit entre les opérations. Dans ce cas, il y a un verrou mortel. Le but est alors de déterminer la taille D(b) de chaque buffer b de sorte que la somme w(b)D(b) sur l'ensemble des buffers soit minimale et que le graphe de précédence soit sans circuit. Nous montrons que ce problème est polynomial pour 2 tâches en utilisant un algorithme de flots. Nous montrons également qu'il est NP-difficile au sens fort pour 3 tâches.
• Mots clés : Minimisation de buffers, ordonnancement, verrous mortels
• Directeur de la publication : Francois.Dromard (at) nulllip6.fr