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

Beim Floorplanning ist Simulated Annealing das derzeit am meisten verwendete Verfahren. Ein bekannter Floorplanning-Algorithmus basierend auf Simulated Annealing arbeitet dabei mit der umgekehrten polnischen Notation (UPN). Die Startlösung wird im Allgemeinen zufällig generiert. Entscheidend für den Algorithmus sind der Satz der erlaubten Veränderungen und die Kostenfunktion.

Veränderungen:

Ausgehend von einem normalisierten UPN-Ausdruck wird eine neue Lösung, die wiederum eine normalisierte UPN ist, durch eine der folgenden drei Operationen bestimmt:

OP1: Vertausche zwei im Ausdruck adjazente Operanden

OP2: Invertiere eine Kette von Operatoren (* wird zu + und umgekehrt)

OP3: Vertausche einen Operanden mit einem adjazenten Operator, falls das Ergebnis wieder eine normalisierter UPN-Ausdruck ist.

Dieser Satz von Veränderungen ist vollständig, d.h. ausgehend von jedem beliebigen normalisierten UPN-Ausdruck kann jeder beliebige andere über eine Folge dieser Operationen erreicht werden.