Platzierung

  • Platzierung
  • Platzierung als ..Optimierungsproblem
  • ..Zuordnungsproblem I
  • ..Zuordnungsproblem II
  • Optimierungskriterien
  • ..Fläche I
  • ..Fläche II
  • ..Timing
  • ..Congestion
  • ..Weitere
  • Verdrahtungslängenabschätzung
  • ..Bounding Box
  • ..Kette
  • ..Spannbaum
  • ..Steinerbaum
  • Klassen von Platzierungsverfahren
  • Platzierungsverfahren
  • ..Clusterverfahren
  • ..Clusterverfahren: Beispiel
  • ..Min-Cut
  • ..Min-Cut: Beispiel
  • ..Quadratische Optimierung
  • ....Feder-Masse-Modell
  • ....Energie-Berechnung
  • ....Kräftegleichgewicht
  • ....Initialplatzierung
  • ....Abstoßende Kräfte
  • ....Dichtefunktion
  • ....Beispiel
  • ....Legalisierung
  • ..Simulated Annealing
  • ..Genetische Algorithmen
  • ....Beispiel
  • ....Operatoren
  • ......Crossover
  • ......Mutation
  • ......Selektion
  • Bewertung der Verfahren
Startseite
Platzierung als Optimierungsproblem Gegeben: Zellen mit Verbindungen untereinander Gesucht: Überlappungsfreie Anordnung der Zellen, so dass automatische Verdrahtung gewährleistet ist Optimierungsziel: Gesamtverdrahtungslänge LGesamt = li Σ i Feste Plätze auf der Layoutfläche: -> Kombinatorisches quadratisches Zuordnungsproblem

Die Platzierung stellt ein Optimierungsproblem in der Regel mit Nebenbedingungen dar. Gegeben sei eine Anzahl von Zellen, die auf einer vorgegebenen Fläche platziert werden sollen. Die gefundene Anordnung soll eine automatische Verdrahtung des Systems ermöglichen. Optimierungsziel ist die Gesamtverdrahtungslänge. Damit kann einerseits die Fläche minimiert werden, andererseits die Performance, da kürzere Leitungen kürzere Verzögerungszeiten bedingen. Zusätzlich können Verzögerungszeitvorgaben für einzelne Leitungen in Form von Nebenbedingungen angegeben werden.

Setzte man vereinfachend voraus, dass für die Platzierung lediglich feste Plätze auf der Layoutfläche zur Verfügung stehen, kann Platzierung als ein kombinatorisches quadratisches Zuordnungsproblem gesehen werden. Darunter versteht man die Anordnung von n Zellen auf n verschiedene Positionen.