Program > By author > Zaourar Lilia

Wednesday 26
Graphs, flows, combinatorial algorithms and approximation
Sébastien Morais
› 16:20 - 16:40 (20min)
› Bât B - TD 43
Ratio de performance d'algorithmes de bin packing en deux dimensions pour des tests de mémoires
Lilia Zaourar  1, *@  , Youen Lesparre  2@  , Alix Munier  2, *@  
1 : Centre d'énergie atomique  (CEA LIST)  -  Website
CEA/ DRT/LIST
CEA, LIST, Embedded Real Time Systems Laboratory, F-91191 Gif-sur-Yvette -  France
2 : Laboratoire d'Informatique de Paris 6  (LIP6)  -  Website
Université Pierre et Marie Curie (UPMC) - Paris VI, CNRS : UMR7606
4 Place JUSSIEU 75252 PARIS CEDEX 05 -  France
* : Corresponding author

Le test de circuits est de nos jours un véritable défi industriel. Un ou plusieurs testeurs externes
envoient au composant à tester des données (les vecteurs de test) et analysent sa réponse. Ce processus
pose plusieurs problèmes d'optimisation combinatoire originaux et intéressants. Celui qui nous
intéresse ici est le regroupement des mémoires en lots d'une puissance maximale fixée. Ceux-ci seront
testés de manière séquentielle de sorte à réduire le temps de test global.

Ce problème correspond à une version non classique du Bin-Packing en deux dimensions : le test d'une
mémoire est associé à un rectangle de longueur le temps de test, et de hauteur la puissance développée.
La hauteur d'une Bin est la somme des hauteurs des rectangles qui la composent. Une hauteur maximale
est fixée. La longueur d'une Bin est la longueur maximale d'un rectangle. L'objectif est de minimiser la
somme des longueurs des Bins.

Ce problème inclus le Bin-Packing classique : il est donc NP-difficile. Une borne inférieure simple du
temps de test global est obtenue en utilisant la programmation linéaire. Elle permet de montrer que
l'algorithme Next Fit decreasing (avec l'ordre décroissant sur les longueurs des Bins) a un ratio de
performance de 2.

Dans cet exposé, nous démontrons que la borne inférieure utilisée précédemment pouvait être deux
fois plus petite que l'optimum. Nous introduisons alors une généralisation de la fonction de poids de
Dosa utilisée en Bin-Packing classique. Elle nous permet de montrer un ratio de performance proche de
1.7 pour une extension du First-Fit avec ordre décroissant sur la largeur d'abord, puis la hauteur. Ces
travaux sont complétés par des expérimentations sur plusieurs instances issues à la fois de benchmarks
académiques et industriels.


Online user: 1