Floorplanning

Floorplanning ist ein Optimierungsproblem, bei dem Funktionsgruppen oder Bauteile in einem System so anzuordnen sind, dass sich möglichst kurze Verbindungs-, Transport- oder Signalwege ergeben. Eine große Rolle spielt Floorplanning heute im Chipentwurf und Layoutentwurf, wo eine Gesamtschaltung in einzeln zu entwerfende Teilschaltungen aufzuteilen ist.

Beschreibung

Das Optimierungsziel beim Floorplanning ist die Minimierung der Verbindungs-, Transport- oder Signalwege, meist um die Geschwindigkeit oder Größe einer elektronischen Schaltung zu optimieren. Beispiele sind

• Anordnung der Schaltungsblöcke auf einer Leiterplatte,
• Anordnung von Teilschaltungen in einem integrierten Schaltkreis,
• Aufstellung der Maschinen in einer Fabrikhalle für einen Produktionsablauf (ursprüngliche Herkunft des Begriffes) und
• Platzierung 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 leiten Partitionierung und Floorplanning die Layoutsynthese ein. Wesentliche Aufgaben beim Floorplanning sind das Festlegen der Formen und der Anordnung der Schaltungsblöcke (Planung der Blockformen und -positionen) und die Signalbelegung der I/O-Pins (Anschlüsse).

Da viele dieser Teilaufgaben NP-vollständig sind und eine große Lösungsmenge haben, ist die Berechnung optimaler Lösungen in angemessener Zeit nicht möglich und es werden Approximationsalgorithmen und Heuristiken verwendet.

Literatur

• M. F. Anjos, A. Vannelli: An Attractor-Repeller Approach to Floorplanning. In: Mathematical Methods of Operations Research (ZOR). 56, Nr. 1, 2002, S. 3-27, doi:10.1007/s001860200197.
• J. Lienig: Layoutsynthese elektronischer Schaltungen - Grundlegende Algorithmen für die Entwurfsautomatisierung. Springer, Berlin 2006, ISBN 978-3-5402-9627-0.