Sujets de RECHERCHE pour les masters M2 :
Année 12-13
TITRE : Ordonnancement et bin packing
Descriptif et objectifs : en construction
Encadrants : Marin bougeret et Rodolphe Giroudeau , Denis Trystram
Mail : marin.bougeret@lirmm.fr et rgirou@lirmm.fr, trystram@lig.fr
TITRE : Etude
du point de vue de la complexité classique/paramétrique et algorithmes
d'approximation avec mesure classique et différentielle pour des problèmes d'ordonnancement.
Descriptif et objectifs :
Les
problèmes d'ordonnancement sont des problèmes combinatoires qui ne sont
pas trop complexes ce qui permet de procéder à une analyse analytique
(classification au sens de la complexité et de l'approximation). Dans
ce stage nous nous intéressons à des problèmes
d'ordonnancement pour lesquels nous ferons une analyse croisée
complexité classique/paramétrique et approximation dans le pire
cas/approximation via la mesure différentielle.
Encadrants : Marin bougeret et Rodolphe Giroudeau
Mail : marin.bougeret@lirmm.fr et rgirou@lirmm.fr
TITRE : Étude de problèmes de compactions de graphes
Descriptif et objectifs :
Nous nous intéressons à la complexité algorithmique des
problèmes de compactions de graphes. Ces problèmes consistent à décider
si l'on peut contracter des ensembles de sommets d'un graphe pour
obtenir un graphe fixe ou bien un graphe ayant certaines propriétés
(par exemple : avoir le moins d'arêtes possibles, avoir un degré
maximum borné, ou toute autre propriété de graphes).
D'un point de vue théorique, ces problèmes (le plus souvent
NP-difficiles) peuvent être vus à la fois comme des problèmes de
partition de graphes, des problèmes d'homomorphismes de graphes ou des
problèmes de modification de graphes.
D'un point de vue pratique, ces problèmes jouent également un rôle
important, comme dans l'ingénierie logiciel, les réseaux de
télécommunications, les calculs distribués… etc.
Le but du stage est dans un premier temps d'étudier la littérature
existante autour de ces problèmes (et notamment les problèmes
classiques qui tournent autour), et dans un deuxième temps de
s'intéresser au problème pour certaines propriété de graphes. Pour
cela, on a à notre disposition plusieurs outils (à utiliser selon
goût…), tels que :
- algorithmes polynomiaux/NP-complétude
- algorithmes d'approximations, schéma d'approximation/bornes inférieures d'approximation
- algorithmes FPT, noyaux/bornes inférieures
- algorithmes exacts exponentiels
- étude dans des classes de graphes particulières.
Encadrants : Rémi Watrigant Marin Bougeret Rodolphe Giroudeau
Mail : remi.watrigant@lirmm.fr, marin.bougeret@lirmm.fr, et rgirou@lirmm.fr
TITRE : Etude du point de vue complexité/approximation et méthodes exactes un problème de test pour la micro-électronique.
Descriptif et objectifs :
La
conception de circuits intégrés en 3D est apparue il y a quelques
années, poussée par deux objectifs principaux : proposer à la fois des
circuits occupant une très faible surface tout en augmentant leurs
performances. La conception 3D répond à ces nouvelles exigences mais
demande aussi de relever de nouveau défis concernant la fabrication de
tels systèmes. Un système 3D est une pile de circuits intégrés
individuels (dies) communiquant au travers d'interconnections
verticales (TSV, Through Silicon Via), percées au travers des circuits.
Ces TSVs contribuent à l'optimisation des performances du système en
présentant des longueurs inférieures aux interconnections nécessaires
pour une intégration du même système en 2D. Plusieurs méthodes
d'intégration sont explorées aujourd'hui dans l'industrie. Une
stratégie possible consiste à empiler des wafers (disque servant de
support à la fabrication de plusieurs dies identiques) avant de les
découper en systèmes 3D individuels (stratégie Wafer-to-Wafer ou W2W).
Cette stratégie a l'avantage de permettre l'intégration d'une plus
grande quantité de TSVs, et donc d'augmenter les performances par
rapport à d’autres stratégies comme avec la D2D par exemple (Die-to-Die
ou D2D: découpage des wafers, tri des dies -fonctionnel vs défaillant-,
empilement des seuls dies fonctionnels). En W2W, tous les étages de la
pile de wafers avant découpage contiennent le même nombre de dies,
chacun pouvant être indexé par ses coordonnées en X,Y sur le wafer. Par
exemple, le die de coordonnée x1,y1 sur le wafer servant de base à la
pile est forcément assemblé avec les dies de mêmes coordonnées x1,y1
sur les wafers des étages supérieurs de la pile. Cette stratégie W2W
présente donc un rendement inférieur à celle du D2D. En effet,
l'assemblage de wafers complets implique que certains dies exempts de
défauts se trouvent assemblés à des dies défectueux car se trouvant aux
mêmes coordonnées sur un autre wafer de la pile. Ceci s'explique par la
répartition, en partie aléatoire, des circuits défaillants sur un Wafer
et par la technique d'assemblage de deux Wafers qui consiste à mettre
en face à face les circuits de même coordonnées sur chacun des Wafers.
Il en résulte qu'après assemblage d'un nombre de Wafer, certaines piles
sont constituées uniquement de circuits sains, celles-ci sont
fonctionnelles ; d'autres intègrent un circuit défectueux, ou plus, et
doivent être supprimées de la production (baisse du rendement). Deux
stratégies peuvent être envisagées pour optimiser le rendement d'une
production W2W. D'une part, l'ajout de couches supplémentaires dans les
piles en assemblant plus de Wafers que nécessaires ; cette redondance
matérielle permet la réparation de couches éventuellement défaillantes
dans la pile [1], [4]. D'autre part, la sélection judicieuse des Wafers
à assembler de façon à maximiser le nombre de piles fonctionnelles
obtenues [3] (« Wafer matching »). Ce critère d'optimisation s'appuie
sur la cartographie de défaillance des Wafers indiquant pour chaque
coordonnée XY si le die correspondant est sain ou défectueux. Notons
que ces deux approches (redondance et « wafer matching ») ne sont pas
contradictoires mais il n’existe pas à notre connaissance de
propositions faites en ce sens.
Quelques solutions ont été proposées dans la littérature pour le
problème du « wafer matching »: Reda et al. [2] proposent un algorithme
optimal pour la sélection des wafers à assembler de façon à maximiser
le rendement de production, mais se limitent à des piles constituées de
2 étages seulement. Ils proposent aussi plusieurs heuristiques pour des
piles d'au moins trois couches. Plus récemment [5], une nouvelle
heuristique a été développée après avoir exploré différents critères
d'optimisation, différents moyens de prise en compte de la totalité des
Wafers d'une production, et différents parcours possible de l'ensemble
des solutions. L'algorithme s'appuie sur un critère d'optimisation
adaptatif. Selon le rendement de chaque Wafer (nombre de dies
fonctionnels/total des dies fabriqués), on choisit, soit de maximiser
le nombre de circuits sains (resp. défectueux) assemblés avec des
circuits sains (resp. défectueux), soit de minimiser le nombre de
circuits sains assemblés avec des circuits défectueux. Les Wafers sont
considérés par lot (e.g. 25 ou 50 wafers sont considérés simultanément
pour chacune des couches de la pile), mais chaque lot se voit réallouer
un nouveau wafer de la production lorsqu'un wafer a été sélectionné
pour assemblage. Cette approche gloutonne ne remet pas en cause les
choix d’assemblage fait à chaque itération.
Notre objectif est de résoudre le problème d'assemblage des wafers pour
un rendement de production optimal en considérant conjointement le
problème d’optimisation du wafer matching et l’ajout éventuel de
couches redondantes.
[1]R.S. Patti.,Three-dimension integrated circuits and the future of
systems-on-chip designs.In Proc IEEE, volume~94, pages 1214--1224, June
2006.
[2]S.Reda, G.Smith, and L.Smith. : Maximizing the functional yield of
wafer-to-wafer 3-d integration. In Proc. IEEE Transactions on Very
Large Scale Integrations Systems, volume~17, pages 1357--1362,
2010.
[3]L.Smith, G.Smith, S.Hosali, and S.Arkalgud. Yield considerations in
the choice of 3d technology. In Proc. IEEE Transactions on Very Large
Scale Integrations Systems, pages 535--537, 2007.
[4]M.Taouil and S.Hamdioui. Layer redundancy based yield improvement
for 3d wafer-to-wafer stacked memories. In Proc. 16 European Test
Symposium, pages 45--50, 2011.
[5]M.Taouil, S.Hamdioui, J.Verbree, and E.J. Marinissen.On maximizing
the compoud yield for 3d wafer-to-wafer stacked ics. In IEEE
International Test Conference, pages 1--10, 2010.
Le défi associé à cette problématique consiste à développer des
algorithmes efficaces en termes de temps de calculs versus qualité de
la solution, i.e. déterminer la meilleure affectation et l'ordre des
tranches de silicium afin de maximiser le nombre de lots valides. Nous
sommes face à un problème d'optimisation avec une combinatoire
très importante. En effet, la plaquette des wafers
composant une pile 3-D peut-être représenté comme un tuple de
longueur K, il existe donc N^k tuples possibles et il existe
N!^k-1 manières de choisir N tuples à partir des N^k tuples
possibles sans répétitions.
Le but de ce stage est double :
*développer des méthodes exactes efficaces
*Classifier les problèmes du point de vue de la complexité et de l'approximation.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr