Floorplanning

aus Wikipedia, der freien Enzyklopädie

Floorplanning ist ein Begriff aus dem Bereich der Optimierung. Er wird heute hauptsächlich im Fachgebiet Leiterplattendesign und Chipentwurf verwendet. Er bezeichnet die geplante optimierte Verteilung von Funktionsgruppen oder Bauteilen in einem System, so dass die Verbindungs-, Transport- oder Signalwege ein Optimum annehmen. Das Optimum muss in diesem Fall nicht das Minimum sein, wird dieses aber oft erreichen. Beispiele sind:

• Optimierung der Leitungsbahnen auf einer Leiterplatte
• Optimierung der Signalwege bei einem integrierten Schaltkreis auf einem Halbleitersubstrat
• Optimierung der Aufteilung der Maschinen in einer Halle einer Fabrik in Bezug auf den Ablauf einer Produktionslinie (hier kommt der Begriff auch her)
• Optimierung der Aufteilung der Regale und Waren auf den Regalen in einer Verkaufseinrichtung

Beim Chipentwurf unterscheidet man Floorplanning in frühen und späten Entwurfsphasen. Nach Verhaltens- und Strukturentwurf leitet Floorplanning den physikalischen Entwurf ein, der mit der Layoutsynthese abschließt. Wesentliche Floorplanning-Aufgaben sind die Platzierung (Planung der Zellformen und der Zellpositionen) und die Globalverdrahtung.

Bei letzterem werden die Verdrahtungsflächen und die Zuordnung von Netzsegmenten zu diesen festgelegt. Dieses geschieht mittels Graphenalgorithmen, zum Beispiel mittels Dijkstra-Algorithmus oder Steinerbaumalgorithmen. Die Aufgabe ist dabei vor allem die Minimierung der Gesamtnetzlänge, Minimierung der Gesamtfläche für die Kanalverdrahtung, Minimierung der maximalen Pfadverzögerungszeit oder Kombinationen dieser Kriterien.

Da viele dieser Teilaufgaben np-vollständig sind, ist das Auffinden optimaler Lösungen in angemessener Rechenzeit nicht möglich und es werden Approximationsalgorithmen und heuristische Algorithmen verwendet.

[Bearbeiten] Siehe auch

• Autoplacer

[Bearbeiten] Literatur

• Mathematical Methods of Operations Research, Vol. 56(1), 2002, S. 3-27.
• Jens Lienig: Layoutsynthese elektronischer Schaltungen. Grundlegende Algorithmen für die Entwurfsautomatisierung. Springer, Berlin 2006, ISBN 3-540-29627-1.