Le 14/12/2012 par alm :
Titre : Etude d'un algorithme approché pour le test de mémoires
Description du sujet : Tout circuit intégré sortant d'une chaîne de production est testé de manière automatique. Pour cette opération, un testeur extérieur envoie des données au circuit, et compare les réponses obtenues à celles attendues. Un ensemble de composants dédiés à la réalisation de cette phase de test est en général rajouté au circuit. Une partie des traitements est alors effectuée directement par la puce, accélérant de manière significative le processus industriel. Le problème d'optimisation combinatoire considéré ici est issu directement du problème de test des mémoires d'un circuit [1].
Soient n mémoires M1 · · · Mn représentées par les couples d'entiers Mi = (ti, pi) ou ti est le temps de test de la mémoire et pi la puissance consommée lors de la procédure de test. Pour tout ensemble A ⊆ {1, · · · , n}, le temps nécessaire pour tester toutes les mémoires de A en parallèle est TA = maxi∈A ti et la puissance dissipée sur la puce est PA = sum_{i∈A} pi. Le problème consiste à construire une partition A1, · · · , Ak de l'ensemble des indices de mémoires {1, · · · , n} de sorte que la durée de test T = sum^k{j=1} TAj soit minimale, tout en garantissant que la puissance maximum maxj∈{1,··· ,k} PAj reste inférieure à une valeur fixée Pmax.
Si les mémoires ont toutes le meme temps de test, le problème est alors équivalent au problème du Bin-Packing. Il est donc NP-difficile. Le but de notre étude est de développer des algorithmes approchés efficaces pour le résoudre partant de l'abondante littérature sur le Bin-Packing [3].
Un premier algorithme d'approximation basé sur la stratégie Next Fit Decreasing a été étudié dans [2]. On montre que le ratio d'approximation est de 2. Cet algorithme a été également implémenté et évalué expérimentalement sur des données issues de problèmes industriels.
L'objectif de ce stage est de reprendre cette étude et de développer une stratégie plus élaborée de sorte à améliorer si possible le ratio de performance obtenu. Une comparaison expérimentale entre les différents algorithmes ap- prochés est également à envisager durant ce stage.
Compétences requises : De bonnes connaissances en algorithmique et en optimisation combinatoire sont indispensables, ainsi que la maîtrise d'au moins un langage de programmation (C/C++, Java, Python, OCaml...).
Conditions du stage : Le stage doit avoir lieu au département SoC du LIP6, 4 place Jussieu, 75252 Paris cedex 05. Sa durée est de 5 à 6 mois et sera gratifié (approx. 417 Euros/mois). Il sera co-encadré par Alix Munier Kordon et Lilia Zaourar Koutchoukali.
Pour candidater : envoyer un CV à Alix.Munier@lip6.fr et Lilia.Zaourar@gmail.com
BIbliographie[imgs=][/imgs] :
[1] L. Zaourar, Y. Kieffer, A.Wenzel. A Complete methodology for determi- ning memory BIST optimization under sharing constraints. IEEE Asia Symposium on Quality Electronic Design,pages :4653, 2011.
[2] L. Zaourar , A. Munier Kordon. An approximation algorithm for tes- ting memories of an integrated circuit. International Workshop on Bin Packing and Placement Constraints, 2012.
[3] E. G. Coffman, Jr., M. R. Garey and D. S. Johnson. Approximation Al- gorithms for Bin Packing : A Survey. In Approximation algorithms for NP-Hard Problems, ed. Dorit S. Hochbaum,46-93, University of Califor- nia, Berkeley, CA 94720-1777, 1996.
Le 15/01/2013 par alm :
Le stage est maintenant pourvu; il est par conséquent inutile de candidater.
Bien cordialement
Alix Munier Kordon
