Floorplanning

  • Floorplanning
  • Floorplanning als Optimierungsproblem
  • Abschätzung der Optimierungsziele
  • Slicing Floorplan
  • Schnittbaum, umgekehrte polnische Notation(UPN)
  • Algorithmen (1): Simulated Annealing
  • ...Pseudo-Code
  • ...Akzeptanz
  • ...Überwinden lokaler Minima
  • ...Anwendung auf das Floorplanning-Problem
  • Algorithmen (2): Graphen-Dualisierung
  • Vom Graph zum Floorplan
  • Algorithmen (3): Lineare Optimierung
  • Lineare Optimierung (2)
  • Lineare Optimierung (3)
Startseite
Lineare Optimierung (3)     Floorplanningproblem alsnichtlineares Optimierungsproblem: min A = min X * Y Linearisierung durch Vorgabeeiner festen Gesamtbreite X: Alle Zelle-Koordinaten sindpositiv. min Y xi + wi ≤ X yi + hi ≤ Y yi + hi ≤ yj + H * (1 + pij - qij)yj + hj ≤ yi + H * (2 - pij - qij) xi + wi ≤ xj + W * (pij + qij) pij, qij = 0 oder 1 xj + wj ≤ xi + W * (1 - pij + qij) für alle 1 ≤ i ≤ nbzw. 1 ≤ i < j ≤ n xi, yi ≥ 0 Alle Zellen liegeninnerhalb der Layoutfläche. Zellen dürfen sichnicht überlappen.

Für einen gültigen Floorplan müssen die folgenden Bedingungen zutreffen:

1. Alle Zelle-Koordinaten sind positiv, d.h. 0 <= xi und 0 <= yi

2. Jede Zelle befindet sich vollständig innerhalb des den Floorplan umgebenden Rechtecks mit Breite X und Höhe Y, d.h. xi + wi <= X und yi + hi <= Y.

3. Keine zwei Zellen überlappen sich.

Ziel ist es, die Fläche A=X*Y des Floorplans zu minimieren. Dies ist jedoch eine nichtlineare Bedingung. Eine Möglichkeit ist es, die Breite X festzuhalten und die Höhe Y zu minimieren. Insgesamt folgt dann für den linearen Optimierungsalgorithmus der angegebene Satz von Bedingungen.

Erlaubt man den Zellen eine flexible Form, so sind hi und wi ebenfalls unbestimmte Variablen, für die weitere Gleichungen eingeführt werden können. Auch die Abschätzung der Verdrahtungslänge kann durch einen Satz von geeigneten Gleichungen berücksichtigt werden.

Neben den vorgestellten Verfahren werden für das Floorplanning auch noch genetische Algorithmen, Min-Cut- basierte Algorithmen, Cluster-Verfahren und andere verwendet. Diese werden auch bei der Platzierung eingesetzt.