Routing-Probleme in VLSI-Systemen - Lösungsansätze mit Genetischen Algorithmen

| Beteiligte Mitarbeiter | Kooperationspartner | Projektbeschreibung | Software | Publikationen |

In hochkomplexen VLSI-Systemen - durch technologische Fortschritte prinzipiell möglich geworden - kommt der Realisierung der Verbindungen zwischen den schaltenden Elementen, dem sogenannten Routing, entscheidende Bedeutung zu. Herkömmliche Verdrahtungsalgorithmen liefern bei konkreten, praktisch relevanten Probleminstanzen jedoch vielfach unzureichende Lösungen.
Im Rahmen des Projektes wird untersucht, wie und inwieweit Genetische Algorithmen (GAs) zur Modellierung und Lösung von Routing-Problemen unter Berücksichtigung von Qualität- und Zeitaspekten eingesetzt werden können. Die Entwicklungen orientieren sich an den folgenden Schwerpunkten:

Modellierung der Probleme mit GAs
Es ist zu entscheiden, wie das jeweilige Routing-Problem im GA zu kodieren ist. Auf dieser Kodierung läuft dann der eigentliche GA ab. Durch die entwickelte Software-Umgebung GAME ist die Verwendung verschiedener Kodierungen möglich. Es muss festgelegt werden, wie geeignete Algorithmen zur Selektion, Rekombination und Mutation definiert werden können. Die Performanz eines GA hängt dann entscheidend davon ab, wie effizient sich die Qualität (Fitness-Funktion) der Elemente in der Population berechnen lässt, und wie schnell sich die genetischen Operatoren (Crossing Over, Mutation, ...) durchführen lassen.

Entwicklung von hybriden GAs
Die Performanz von GAs lässt sich nach unseren Erfahrungen gerade im CAD-Bereich durch die Verwendung von problemspezifischem Wissen steigern. Das Zusammenspiel zwischen GAs und klassischen Optimierungswerkzeugen, wie z.B. Greedy Heuristiken und Branch & Bound, ist zu organisieren. Die hier verwendeten problemspezifischen Verfahren werden durch die Software-Bibliothek MaDRE zur Verfügung gestellt.

Heuristik-Lernen
Es soll versucht werden, einerseits die Vorteile des GA-Ansatzes auszunutzen, andererseits aber auch eine zeitlich effiziente Heuristik zu entwickeln. Dabei wird das zu lösende Problem nicht direkt durch den GA behandelt, sondern GAs werden zur Konstruktion von Heuristiken verwendet, die ausgehend von BOMs konstruiert werden und deren Qualität an einem ausgesuchten Satz von Beispielen gemessen wird. Als BOMs werden hier die einzelnen Routing Strategien der Software-Bibliothek MaDRE verwendet

Es wurden für die Projektarbeit Sofwarepakete entwickelt und speziell angepasst. Diese sind im Folgenden aufgelistet:

GAME (Genetic Algorithm Managing Environment):
Die Programm-Bibliothek GAME ist ein modulares Software-System und wurde speziell zum Einsatz von Genetischen Algorithmen für Optimierungsprobleme im Schaltkreisentwurf von der Arbeitsgruppe in Freiburg entwickelt.
(Kontaktadresse: Frank Schmiedle)

MaDRE (Multiple Strategy Detailed Routing Environment)
Die Programm-Bibliothek MaDRE enthält eine Datenstruktur für Routing-Probleme sowie Verdrahtungsalgorithmen für mehrere Verdrahtungsmodelle. Die Basisdatenstruktur wurde von der Arbeitsgruppe in Halle, die Verdrahtungsalgorithmen von den Arbeitsgruppen in Freiburg und Halle entwickelt.
(Kontaktadresse: Christian Matuszewski)

RAVER (Random Violation, Exact Repair)
RAVER implementiert einen Verdrahter, der traditionelle Verdrahtungsmethoden mit
einem exakten Verfahren kombiniert und dabei von den Vorteilen beider Ansätze
profitiert. Dieser Router wurde von der Arbeitsgruppe in Freiburg entwickelt.