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