Options
2001
Doctoral Thesis
Titel
Ganzzahlig lineare Programmierung bei der globalen Verdrahtung integrierter Schaltkreise
Abstract
Diese Dissertation beschäftigt sich mit dem Problem der globalen Verdrahtung integrierter Schaltkreise. Wir schlagen zwei Formulierungen auf der Basis ganzzahlig linearer Programmierung vor. Der so genannte explizite Ansatz minimiert die Auslastung der Verdrahtungskanäle über eine explizit gegebene Menge von Verdrahtungsvarianten für jedes der zu verdrahtenden Netze. Beim impliziten Ansatz hingegen sind alle Steinerbäume auf den Terminalen eines Netzes zulässige Verdrahtungsvarianten. Eine Diskussion der Vor- und Nachteile beider Ansätze ergibt, dass der explizite Ansatz in der Praxis zu bevorzugen ist. Daher steht der explizite Ansatz im Rahmen dieser Dissertation im Vordergrund. Wir diskutieren die zu Grunde liegende Polyedertheorie für beide Ansätze. Unsere Methoden zur Lösung des expliziten Ansatzes basieren auf lokaler Suche, sequenzieller Verdrahtung, genetischer Verdrahtung und randomisierten Verfahren. Zur Berechnung unterer Schranken wenden wir die Methoden der linearen Relaxation, der linearen Dualität sowie der Lagrange Relaxation an. Es zeigt sich, dass, beim expliziten Ansatz, das lineare Dual und das Lagrange Dual äquivalente lineare Programme repräsentieren. Eine Analyse zur Schärfe der unteren Schranken ergibt, dass die Differenz zwischen den Kosten der optimalen ganzzahligen Lösungen und den Kosten der optimalen nicht-ganzzahligen Lösungen in der Praxis nur wenige Spuren beträgt. Auf der anderen Seite lassen sich Instanzen konstruieren, bei denen diese Differenz extrem hohe Werte annimmt. Die Analyse zur Schärfe der unteren Schranken führt auch zum Konzept der linearen Vorverarbeitung. Hierdurch wird eine beträchtliche Zahl von unattraktiven Verdrahtungsvarianten exkludiert. Wir untersuchen verschiedene Varianten der linearen Vorverarbeitung. Eine von ihnen, die so genannte duale Vorverarbeitung, besitzt die Eigenschaft, dass optimale Lösungen generell erhalten bleiben. In der Praxis trifft dies jedoch für alle Varianten zu. Mit Hilfe der linearen Vorverarbeitung ist es effizient möglich, Instanzen für den expliziten Ansatz mit vielen tausend Netzen optimal oder zumindest beweisbar nahezu optimal zu lösen. Alle vorgeschlagenen Methoden sind in dem Software-Paket Eridanus implementiert. Wir präsentieren experimentelle Ergebnisse. Bei der globalen Verdrahtung ist die Platzierung der Bauteile fest vorgegeben. Eine Verallgemeinerung des Problems, die wir als globale Auslegung bezeichnen, erlaubt eine variable Platzierung der Bauteile. Eine explizite Formulierung des Problems sucht eine vielversprechende Platzierung der Bauteile über eine explizit gegebene Menge von Platzierungsvarianten. Wir zeigen, dass die Ergebnisse für den expliziten Ansatz auf diese Formulierung übertragbar sind.
;
This thesis investigates the global routing problem for integrated circuits. We introduce two formulations on the basis of integer programming. The so-called explicit approach minimizes the load of the channels among an explicitly given set of routing alternatives for each net that has to be connected. In contrast, the implicit approach makes all Steiner trees on the terminals of a net feasible. A discussion of the merits and disadvantages of both approaches proposes that the explicit approach is more attractive for practical reasons. Thus we prefer the explicit approach in this thesis. We discuss the polyhedral theory related to both approaches. Our methods for solving the explicit approach employ local search, sequential routing, genetic routing, and randomized procedures. Our methods for computing lower bounds are based on linear relaxation, linear duality, and Lagrange relaxation. We show that, for the explicit approach, the linear dual and the Lagrange dual represent equivalent linear programs. An analysis on the tightness of the lower bounds indicates, that the difference between the cost of the optimal integer solutions and the cost of the optimal fractional solutions is only a small number of tracks in practice. On the other hand, we can construct examples where this difference is extremely large. Moreover, the analysis of the tightness of the bounds leads to the concept of linear preprocessing by which we exclude a large number of high-cost solutions. We introduce various versions of linear preprocessing, one of which, the so-called dual preprocessing, generally preserves the opportunity of obtaining optimal solutions. In practice all of them do so. Linear preprocessing enables us to efficiently solve problem instances of the explicit approach with many thousand nets provably optimal or at least provably close to optimal. All methods proposed have been implemented in the software-package Eridanus. We present computational results. The global routing problem assumes the placement of the chip components to be fixed. An extension of the problem, which we call global layout, allows the placement to be variable. An explicit formulation of the problem searches for a promising placement among an explicitly given set of placement alternatives. We show that the results for the explicit approach can be extended to this formulation.
ThesisNote
Zugl.: Bonn, Univ., Diss., 2000