Globales Layout integrierter Schaltkreise

Innerhalb dieses Projektes wurde ein vereinheitlichter Zugang zu zwei grundlegenden Phasen im Layout-Prozess integrierter Schaltkreise entwickelt.

Herkömmlich wird der Layout-Prozess integrierter Schaltkreise in verschiedene Phasen geteilt. Der übliche Weg das Layout-Problem zu lösen ist, sich zuerst um die Komponente der Platzierung zu kümmern, und dann denn ungefähren Weg der Verbindungsdrähte in der Global-Routing-Phase zu bestimmen. Auf diese Phase kann eine räumliche Verdichtung folgen, nach der eine ausführliche Routing-Phase den genauen Weg der Verbindungsdrähte bestimmt. Eine geometrische Verdichtungsphase vorher kann den Platzbedarf des Layouts senken.

Diese hierarchische Herangehensweise wird benutzt, weil in der Praxis alle Varianten des Layout-Problems NP-schwierig sind. Andererseits sind die einzelnen Phasen des Layout-Prozesses stark miteinander verknüpft. Wenn zum Beispiel die Platzierung durchgeführt wird, muss das Ziel der Minimierung der Verdrahtungsfläche oder der Wirability-Maximierung schon im Blickfeld sein.

Das Ziel dieses Projektes ist die Formulierung und Untersuchung von Global-Routing-Problemen in der Laufzeit von ganzzahligen Programmen und die Integration der Platzierungs-Phase in dieses System. Die gleichzeitige Lösung von Platzierung und Global-Routing nennen wir globales Layout integrierter Schaltkreise, weil es das gesamte Layout der Schaltung bestimmt. Optimierungsfunktionen berücksichtigen Gebiets- und Zeit-Ergebnisse.

Die Aufgabenstellung von Global-Routing basiert auf einer angemessenen Definition so genannter Routing-Graphen. Die Knoten der Routing-Graphen repräsentieren Teilgebiete des gesamten Routing-Gebietes und werden gekennzeichnet mit ihren Kapazitäten, die angeben, wie viele Drähte das Gebiet aufnehmen kann. Unter Benutzung dieser Abstraktion lässt sich Global-Routing auf eine Menge unabhängiger Steiner-Tree-Probleme zurückführen, eines für jede benötigte Verbindung zwischen Pins der elektronischen Komponenten (solch eine Verbindung wird Netz genannt). Der Weg, auf dem sich ein solches Netz durch den Routing-Graphen bewegt wird Route genannt.

Im Umgang mit dem globalem Layout sind die elektronischen Komponenten noch nicht auf der Chip-Oberfläche befestigt. Stattdessen bilden die Komponenten ein so genanntes Gate-Netzwerk , welches in einen Layout-Graphen bestehend aus Slots (mögliche Orte für elektronische Komponenten) und Kanälen (die für Routing-Drähte benutzt werden können), eingebettet werden muss. Also ist es die Aufgabe von globalem Layout, die elektronischen Bauteile Slots zuzuordnen, so dass der Aufwand für das Global-Routing minimiert wird.

Verschiedene ganzzahlige Programmformulierungen des Global-Routing-Problems sind vorgeschlagen worden. Unsere Forschungen haben die theoretische Analyse von Polyedern dieser ganzzahligen Programme genauso wie Heuristiken und Lokale Suche auf dem Gerüst der beteiligten Polyeder einbezogen. Verschiedene Argorithmus-Typen wie Simulated Annealing und Genetische Algorithmen wurden für die heuristische Lösung von Global-Routing-Problemen angepasst. Um niedrigere Grenzen für den Wert der optimalen Lösung zu erhalten wenden wir Methoden wie die Lagrange-Relaxation und Benders-Decomposition an. Ein Zugang über Branch-and-Bound zusammen mit diesen Grenzen ermöglicht es uns, optimale oder annähernd optimale Lösungen für alle getesteten Probleme zu finden. Die Methoden sind in unserem Global-Layout-Tool ERIDANUS integriert.