Uni-Logo
English       Login
Rechnerarchitektur
        Startseite         |         Institut für Informatik         |         Technische Fakultät
 

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

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


Beteiligte Mitarbeiter

Universität Halle
Paul Molitor, Prof. Dr.
Lehrstuhl für Rechnerarchitektur
Bernd Becker, Prof. Dr.
Frank Schmiedle, Dr.-Ing.
Rolf Drechsler, Prof. Dr.
Kooperationspartner

Universität Halle
Christian Matuszewski, Dipl.-Inf.
Robby Schönfeld, Dipl.-Inf.
Lehrstuhl für Rechnerarchitektur
Andre Markert
Daniel Unruh


Projektbeschreibung

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



Software

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.



Publikationen
N. Goeckel, G. Pudelko, Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
A Hybrid Genetic Algorithm for the Channel Routing Problem
IEEE International Symposium on Circuits and Systems, pp. IV:675-IV:678, Atlanta, 1996
N. Goeckel, Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
GAME: A Software Environment for Using Genetic Algorithms in Circuit Design
International Conference on Applied Computer Systems, Szczecin, Poland, 1997
N. Goeckel, Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
A Multi-Layer Detailed Routing Approach based on Evolutionary Algorithms
IEEE International Conference on Evolutionary Computation, pp. 557-562, Indianapolis, 1997
Frank Schmiedle, Dr.-Ing., Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
Exact Routing using Symbolic Representation
IEEE International Conference on Circuits and Systems, pp.VI:394-VI:397, Orlando, 1999
Christian Matuszweski, Frank Schmiedle, Dr.-Ing., Robby Schönfeld
Routing with Genetic Algorithms
Albert-Ludwigs-University Freiburg, Technical Report 125, 1999
Frank Schmiedle, Dr.-Ing., Daniel Unruh, Bernd Becker, Prof. Dr.
Exact Switchbox Routing with Search Space Reduction
ACM International Symposium on Physical Design, pp. 26-32, San Diego, 2000
Frank Schmiedle, Dr.-Ing., Rolf Drechsler, Prof. Dr., Bernd Becker, Prof. Dr.
Exact Routing with Search Space Reduction
IEEE Transactions on Computers, 52(6), 2003
Frank Schmiedle, Dr.-Ing.
Exakte Verdrahtung mit symbolischen Methoden
Dissertation, Logos Verlag, 2003