Schichtzuweisung auf Schaltkreisfeldern

Bernd Kiefer

Diplomarbeit, Universität des Saarlandes, Lehrstuhl Prof. Hotz Saarbrücken, Feb. 1989

In dieser Arbeit wird ein Algorithmus vorgestellt und untersucht, der den Algorithmus zur Kontaktminimierung bei der Einbettung von Schaltkreisen in zwei Schichten auf den Fall von Schaltkreisfeldern (d.h. Feldern gleichförmiger Schaltkreise) erweitert.

In der Arbeit wird gezeigt, unter welchen Nebenbedingungen man einen Teilchip aus dem Feld isoliert optimieren kann und mit wenigen (hoechstens vier) verschiedenen lokalen Lösungen zu einer wesentlich besseren globalen Lösung kommt als bei der isolierten Optimierung ohne Nebenbedingungen und der offensichtlichen Erweiterung dieser Lösung.

Die erforderlichen Nebenbedingungen werden durch das Aufwickeln des Schaltkreises auf einen Torus (oder bei Schaltkreisketten auf einen Zylinder) erzwungen. Die Erweiterung basiert auf einem Algorithmus zur Layoutberechnung für Schaltkreisfelder von K. Mehlhorn und W. R\"ulling. Postscript DVI