Floorplanning

Floorplanning (englisch für Grundrissplanung) bezeichnet 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 bei der Layouterstellung im Chipentwurf, wo einzeln zu entwerfende Teilschaltungen innerhalb einer Gesamtschaltung anzuordnen sind.

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)
Platzierung der Regale und der Waren auf den Regalen in einer Verkaufsstelle.

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. Daher werden Approximationsalgorithmen und Heuristiken verwendet. Zudem gibt es vielversprechende Ansätze, die Floorplanning auf Basis von künstlicher Intelligenz erledigen können.

Floorplanning beim Chipentwurf

Nach Verhaltens- und Strukturentwurf leiten Partitionierung und Floorplanning die Layoutsynthese beim Chipentwurf ein. Die Aufgabe des Floorplanning besteht darin, das Ergebnis der Schaltungspartitionierung so aufzubereiten, dass jeder dabei erstellte Block intern platziert und verdrahtet werden kann. Damit sind die drei wesentlichen Ziele beim Floorplanning das Festlegen

der Formen
der Anordnung der Schaltungsblöcke (Planung der Blockformen und -positionen) sowie
der Signalbelegung der externen I/O-Anschlüsse (Pinzuordnung bzw. Pin Assignment).

Literatur

M. F. Anjos, A. Vannelli: An Attractor-Repeller Approach to Floorplanning. In: Mathematical Methods of Operations Research (ZOR). Band 56, Nr. 1, 2002, S. 3–27, doi:10.1007/s001860200197.
J. Lienig: Layoutsynthese elektronischer Schaltungen – Grundlegende Algorithmen für die Entwurfsautomatisierung. 2. Aufl., Springer, Berlin 2016, ISBN 978-36-624-9814-9.

Einzelnachweise

↑ B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. 5. Aufl., Springer, Berlin 2012, ISBN 978-36-422-4487-2, S. 392.
↑ Arne Grävemeyer: KI optimiert Chipdesigns – und künftige KIs. In: heise online. 9. Juli 2021, abgerufen am 9. Juli 2021.
↑ J. Lienig: Layoutsynthese elektronischer Schaltungen - Grundlegende Algorithmen für die Entwurfsautomatisierung. 2. Aufl., Springer, Berlin 2016, ISBN 978-36-624-9814-9, S. 63.

[1] B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. 5. Aufl., Springer, Berlin 2012, ISBN 978-36-422-4487-2, S. 392.

[2] Arne Grävemeyer: KI optimiert Chipdesigns – und künftige KIs. In: heise online. 9. Juli 2021, abgerufen am 9. Juli 2021.

[3] J. Lienig: Layoutsynthese elektronischer Schaltungen - Grundlegende Algorithmen für die Entwurfsautomatisierung. 2. Aufl., Springer, Berlin 2016, ISBN 978-36-624-9814-9, S. 63.