A Buffer Minimization Problem for the Design of Embedded Systems
Etude d'un problème de minimisation de buffer pour la conception de systèmes embarqués
Résumé
We consider a set of n tasks, each of them is composed by a set of sequential operations. A set of buffers B is given: each buffer b in B is defined between two tasks Ti-_Tj, has a weight w(b) and is managed as a FIFO structure. Some operations from Ti write data in the buffer b, others from Tj get data in b. The writings and readings on buffers generate precedence constraints between the operations. The limitation of the size of the buffers generates an other set of precedence constraints between them and circuits in this precedence graph may appear. In this case, there is no feasible schedule for the operations. The aim is to find the size of each buffer D(b), b in B, such that the sum of the terms w_(b)D(b), b in B is minimum and there is no circuit in the precedence graph. We prove that this problem is polynomial for 2 tasks using a flow algorithm. We also prove that it is NP-hard in the strong sense for 3 tasks.
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.
Origine : Fichiers produits par l'(les) auteur(s)