Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.
| Identifer | oai:union.ndltd.org:theses.fr/2018GREAM094 |
| Date | 15 October 2018 |
| Creators | Ait ferhat, Dehia |
| Contributors | Grenoble Alpes, Stauffer, Gautier |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0026 seconds