A Buffer Minimization Problem for the Design of Embedded Systems

A. Munier-Kordon, J.-B. Note

LIP6 2002/024: Rapport de Recherche LIP6 / LIP6 research reports
18 pages - Octobre/October 2002 - Document en anglais.

Get it : 211 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Architecture des Systèmes Intégrés et Micro-Électronique

Titre français : Etude d'un problème de minimisation de buffer pour la conception de systèmes embarqués
Titre anglais : A Buffer Minimization Problem for the Design of Embedded Systems

Résumé : 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.

Abstract : 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.

Mots-clés : Minimisation de buffers, ordonnancement, verrous mortels

Key-words : Buffer minimization, scheduling, deadlocks

Publications internes LIP6 2002 / LIP6 research reports 2002

Responsable Éditorial / Editor :Francois.Dromard@lip6.fr