Das vorgestellte Verfahren optimiert mit Hilfe eines genetischen Algorithmus
sowohl die Plazierung als auch die Verdrahtung bei der Layoutgenerierung.
Möglich ist dieses durch eine geeignete Genotyp-Kodierung als binärer
Schnittbaum, der generiert wird, indem Blöcke bzw. Teil-Layouts zu
Meta-Blöcken und letztendlich zum Gesamtlayout zusammengefa werden.
Bei der Konstruktion dieser Teil-Layouts wird die gesamte, innerhalb
dieses Teils verlaufende Verdrahtung festgelegt.
Der genetische Algorithmus permutiert die Teil-Layouts und ermittelt
dadurch sowohl eine optimale globale Anordnung der Blöcke, als auch
eine günstige Verdrahtung.
Bei der Konstruktion eines Teil-Layouts wird zur Zeit in dem Kanal
zwischen zwei Blöcken für jedes Netz eine Spur reserviert, was in dem
generierten Layout zu grö Verschnittflächen führt.
Eine Verbesserung wäre hier durch eine Kompaktierung im Anschluß an
die Optimierung durch den genetischen Algorithmus zu erreichen.
Dadurch wäre jedoch nicht mehr die Optimalität der gefundenen
Lösung garantiert, da diese im wesentlichen durch die Kompaktierung
bestimmt würde.
Hier soll während der Optimierung durch den genetischen Algorithmus
mit einer schärferen Schranke für die benötigte Kanalbreite
gearbeitet werden, welche möglichst genau den Verdrahtungsplatz abschätzt,
den ein Kanalverdrahtungsverfahren benötigt, was im Anschluß an
den Optimierungslauf die detaillierte Verdrahtung durchführt.
Der exakte Verdrahtungsplatz kann auch schon während der Optimierung
berechnet werden, jedoch ist es sinnvoller, hier weiterhin mit einer
Abschätzung zu arbeiten, um die -- ohnehin schon hohe -- Laufzeit des
genetischen Algorithmus zu reduzieren.
Eine weitere Schwäche der aktuellen Implementation liegt in der Tatsache,
daß durch die hierarchische Konstruktion viele Netze nach
au geführt werden, welche anschlie über den Au des Layouts
zusammengeführt werden müssen.
Um kürzere Verdrahtungswege zu erzeugen, ist es geplant, zusätzlich
zur Layout-Fläche auch die Gesamtverdrahtungslänge bei der Berechnung
der Fitneß zu berücksichtigen, so daß Individuen, welche Layouts mit
kurzen Verdrahtungswegen repräsentieren, während der Optimierung eine
grö ,, Überlebenschance`` haben.
Aufgrund der natürlichen Parallelität der genetischen Algorithmen bietet sich eine Parallelisierung, selbst auf einem massiv parallelen System an, welche ebenfalls im Rahmen dieses Projektes durchgeführt werden soll.