LIP6 2002/024
- Reports
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 - 10/11/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
- Keywords : Buffer minimization, scheduling, deadlocks
- Publisher : Francois.Dromard (at) nulllip6.fr
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.