Steiner-Punkt

Ein Steiner-Punkt ist ein zusätzlicher Knoten, der in ein Netzwerk-Routing-Problem eingeführt wird, um die Gesamtleitungslänge unter die eines direkten Baums zu senken, der nur die erforderlichen Anschlüsse verbindet. In der Leiterplattenentwicklung und beim Interconnect-Routing besteht das Ziel darin, eine Reihe von festen Knoten (Bauteilpins, Vias oder Signalpunkte) mit der kürzestmöglichen Gesamtleiterlänge zu verbinden. Ein Steiner-Punkt ist nicht einer dieser erforderlichen Anschlüsse, sondern ein neuer Knotenpunkt an einer optimalen Position, an der mehrere Leitersegmente zusammentreffen und wo sich die Verdrahtung auf eine Weise biegen und teilen kann, die Gesamteinsparungen bringt.

Das Konzept stammt aus der Fermat-Punkt-Geometrie, trägt aber seinen Namen von Jakob Steiners Arbeit über minimale Netze. In der Ebene entstehen an einem Steiner-Punkt, an dem drei Leitersegmente zusammentreffen, bei optimaler Anordnung Winkel von 120 Grad, eine Eigenschaft, die Algorithmen für physikalische Layouts antreibt. Für eine einfache Zwei-Punkt-Verbindung hilft kein Steiner-Punkt; bei drei oder mehr Punkten kann das Hinzufügen eines oder mehrerer Steiner-Punkte die Gesamtlänge in typischen Fällen um 10 bis 15 Prozent reduzieren. Die maximal mögliche theoretische Einsparung über alle Konfigurationen nähert sich 13,4 Prozent an, wenn optimale Steiner-Bäume Minimum-Spanning-Trees ersetzen.

Praktische Anwendung beim Routing und Design

Im Elektronik-Design erscheinen Steiner-Punkte am häufigsten bei der Clock-Tree-Synthese, in Stromverteilungsnetzen und beim Signalrouting auf großen Chips oder High-Speed-Leiterplatten. Ein Router-Softwarepaket berechnet Kandidatenpositionen für Steiner-Punkte, um Netze mit drei oder mehr Anschlüssen zu verbinden. Jeder zusätzliche Steiner-Punkt erhöht die Routing-Komplexität und erfordert sorgfältige Platzierung, um Übersprechen oder kapazitive Kopplung zu vermeiden. In einigen Design-Flows werden Steiner-Punkte auf einem rechtwinkligen Gitter (Manhattan-Geometrie) statt frei in der Ebene positioniert, was die Fertigung vereinfacht, aber den Längenvorteil reduziert.

Das Steiner-Tree-Problem selbst ist NP-schwer, was bedeutet, dass kein bekannter Polynomial-Zeit-Algorithmus es für große Graphen exakt löst. Praktische Routing-Tools nutzen Heuristiken und Approximationsalgorithmen wie Iterated 1-Steiner oder Batched-Steiner-Verfahren, die auf echten Netzen mit Tausenden oder Millionen von Knoten in akzeptabler Zeit laufen. Der Kompromiss zwischen Lösungsqualität und Rechenzeit ist zentral für die Leistung von Design-Tools an fortgeschrittenen Technologieknoten.

Steiner-Punkte müssen von zwischenliegenden Routing-Segmenten unterschieden werden, die sich kreuzen oder die Richtung wechseln, ohne sich zu verzweigen. Ein echter Steiner-Punkt ist ein Knoten, an dem sich die Netz-Topologie ändert; das Entfernen oder Zusammenfassen würde verändern, welche Anschlüsse direkt verbunden sind. In überlasteten Bereichen eines Chips oder einer Leiterplatte können Steiner-Punkte geopfert oder leicht verschoben werden, um Routing-Ressourcen-Einschränkungen zu erfüllen, wobei eine kleine Längeneinsparung für physikalische Machbarkeit akzeptiert wird.