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

Bei der Graphen-Dualisierung wird die Schaltung zunächst durch einen Graphen G dargestellt, dessen Knoten die Zellen der Schaltung und die Kanten deren Verbindungen untereinander darstellen. Ein Floorplan kann daraus ermittelt werden, indem der zu G duale Rechteckgraph (DRG) aufgestellt wird. Dieser besteht aus nicht-überlappenden Rechtecken, welche die folgenden Bedingungen erfüllen:

1. Jeder Knoten entspricht einem Rechteck .

2. Für jede Kante ( , ) sind die Rechtecke und adjazent.

Die Graph-Dualisierung führt zur Maximierung von Adjazenzen von Blöcken, die stark (z.B. durch mehtfache Verbindungen) miteinander verbunden sind.