Ein robuster Rahmen für hierarchisches Floorplanning mit integrierter globaler Verdrahtung

Wir präsentieren einen algorithmischen Rahmen für hierarchisches Floorplanning mit integrierter globaler Verdrahtung. Hierbei erweitern wir bewährte hierarchische Lösungsstrategien und stimmen sie in einem homogenen Rahmen aufeinander ab. Die Basis des Verfahrens bildet der Cut-tree, der eine rekursive Zerteilungsstruktur des auszulegenden Schaltkreises beschreibt. Sowohl der Floorplan als auch die globale Verdrahtung werden mittels effizienter Baumdurchläufe durch den Cut-tree konstruiert. Zur Lösung von Teilproblemen verwenden wir mächtige Optimierungsmethoden wie Matching, ganzzahlige Programmierung und Netzwerkfluß. Mithilfe der Integration der globalen Verdrahtung in das Floorplanning basieren die Optimierungen nicht mehr auf ungenauen Netzlängenabschätzungen, sondern auf dem genauen Verlauf der Netze. Auf diese Weise lassen sich neben der Fläche auch andere Kostenkriterien, z.B. Timing-Aspekte, während des Floorplannings genau berücksichtigen. Der Rahmen erweist sich in dem Sinne als besonders robust, als Lösungsalgorithmen für die Teilprobleme leicht erweiterbar oder austauschbar sind, ohne daß die allgemeine Lösungsstrategie verändert werden muß.