Verdrahtung

  • Verdrahtung
  • Randbedingungen
  • Verwandte Probleme
  • Verdrahtungsverfahren
  • Verdrahtungsreihenfolge
  • Globalverdrahter
  • Modellierung
  • Datenstrukturen zur Modellierung(1)
  • Datenstrukturen zur Modellierung(2)
  • Regionszuweisung
  • Detailverdrahtung
  • Kanalverdrahter: Kanalmodell
  • Left-Edge-Algorithmus
  • "Greedy" Kanalverdrahter
  • Beispiel Left-Edge-Algorihmus
  • Switchboxverdrahtung: Beispiel
  • Wellenfrontverdrahter
  • Ausbreitung einer Welle
  • Verbesserung des Speicher-/Laufzeitbedarfs
  • Bewertung: Wellenfrontverfahren
  • Liniensuchverfahren
  • Hightower- und Mikami-Verfahren
  • Bewertung: Liniensuchverfahren
  • Linienexpansionsverfahren
  • Bewertung: Linienexpansionsverfahren
Startseite

Um das Verdrahtungsproblem zu vereinfachen, wird es in Global- und Detailverdrahtung aufgeteilt. Die Globalverdrahtung ist der erste Schritt bei der Verdrahtung. Sie wird für die grobe Steuerung der späteren detaillierten Verdrahtung genutzt.

Die Globalverdrahtung selbst kann in zwei Abschnitte unterteilt werden:

  1. Modellierung
  2. Regionszuweisung

Begonnen wird mit der Modellierung der Fläche für die Globalverdrahtung. Die gesamte freie Fläche wird in kleine Bereiche, so genannte Regionen, geteilt und in einem Graphen abgebildet.

Im zweiten Schritt werden jedem Netz Regionen zugewiesen. Ausschließlich in diesen Regionen wird das Netz vom Detailverdrahter verdrahtet. Gleichzeitig mit der Zuweisung wird die Congestion (Anhäufung) der Regionen überprüft.

Das Problem der Globalverdrahtung ist mit dem Problem der Verbindungssuche in Kommunikationsnetzen verwandt.