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
Kräftegleichgewicht - Kräfte zwischen beweglichen sowie zwischen festen und beweglichen Zellen liefern Energiebetrag E1 = 0,5 xT C x E2 = xT d - Kräfte zwischen festen und beweglichen Zellen liefern zusätzlichen Energiebetrag - Kräfte zwischen festen Zellen liefern zusätzlich konstanten Energiebetrag Etotal = 0,5 xTC x + xT d + const. - Gestamtenergie des Federsystems ergibt sich als C x + d = 0 - Minimieren durch Ableitung und Lösung der Gleichung - Entspricht Kräftegleichgewicht des Federsystems

Zu den bisher beschriebenen Kräften zwischen den beweglichen Zellen treten Kräfte zwischen den festen und beweglichen Zellen sowie zwischen festen Zellen untereinander auf. Diese liefern zusätzliche Energiebeiträge.

Da physikalische Systeme bestrebt sind, den Zustand minimaler Energie anzunehmen, wird das Minimum der potentiellen Energie durch die Ableitung der Matrixgleichung berechnet. Die Ableitung ist C*x+d. Extremwerte lassen sich durch die Nullstellen der Ableitung bestimmen. Physikalisch entspricht die Berechnung der neuen Auslenkungen X einem Kräftegleichgewicht. Man bestimmt also die Position der Masseteilchen, bei der die auf die Masseteilchen wirkenden Kräfte sich aufheben.

Mathematisch betrachtet lässt sich die Kostenfunktion für die quadratische Optimierung mittels einer Matrixgleichung beschreiben. Die Matrix C beinhaltet die Verbindungen zwischen den beweglichen Zellen sowie zwischen festen und beweglichen Zellen, während Verbindungen zwischen beweglichen und festen Zellen zusätzlich Beiträge zu der Matrix d liefern. Das Minimum der Kostenfunktion kann mittels der Gleichung Cx + d = 0 gefunden werden. Diese Gleichung stellt die Ableitung der Kostenfunktion dar. An dieser Gleichung sieht man die Notwendigkeit der festen Zellen für diesen Ansatz. Sind keine festen Zellen vorhanden, so ist der Vektor d ein Nullvektor. Das führt dazu, dass die Platzierung x ebenfalls ein Nullvektor wird. Alle Zellen liegen dann im Ursprung übereinander.