Routing (elektronische Designautomatisierung) - Routing (electronic design automation)

In diesem Artikel geht es um das Entwerfen integrierter Schaltkreise als Teil der elektronischen Entwurfsautomatisierung . Weitere Routing-Arten finden Sie unter Routing (Begriffsklärung) .

Im elektronischen Design ist das Kabel-Routing , das allgemein als einfaches Routing bezeichnet wird, ein Schritt beim Design von Leiterplatten (PCBs) und integrierten Schaltkreisen (ICs). Es baut auf einem vorhergehenden Schritt auf, der als Platzierung bezeichnet wird und die Position jedes aktiven Elements eines IC oder einer Komponente auf einer Leiterplatte bestimmt. Nach der Platzierung werden im Routing-Schritt Drähte hinzugefügt, die zum ordnungsgemäßen Verbinden der platzierten Komponenten erforderlich sind, wobei alle Entwurfsregeln für den IC eingehalten werden. Zusammen werden die Platzierungs- und Routing-Schritte des IC-Designs als Ort und Route bezeichnet .

Die Aufgabe aller Router ist gleich. Sie erhalten einige bereits vorhandene Polygone, die aus Stiften (auch als Anschlüsse bezeichnet) an Zellen bestehen, und optional einige bereits vorhandene Verkabelungen, die als Vorrouten bezeichnet werden. Jedes dieser Polygone ist einem Netz zugeordnet , normalerweise nach Name oder Nummer. Die Hauptaufgabe des Routers besteht darin, Geometrien so zu erstellen, dass alle dem gleichen Netz zugewiesenen Terminals verbunden sind, keine den verschiedenen Netzen zugewiesenen Terminals verbunden sind und alle Entwurfsregeln eingehalten werden. Ein Router kann ausfallen, indem keine Terminals angeschlossen werden, die verbunden werden sollen (offen), indem versehentlich zwei Terminals verbunden werden, die nicht verbunden werden sollen (kurz), oder indem eine Verletzung der Entwurfsregeln erstellt wird. Um die Netze korrekt anzuschließen, muss von den Routern außerdem erwartet werden, dass sie sicherstellen, dass das Design dem Timing entspricht, keine Übersprechprobleme aufweist, die Anforderungen an die Metalldichte erfüllt, keine Antenneneffekte aufweist und so weiter. Diese lange Liste oft widersprüchlicher Ziele macht das Routing extrem schwierig.

Fast jedes Problem mit Routing zugeordnet ist bekannt, dass sie unlösbar . Das einfachste Routing-Problem, das als Steiner-Baum- Problem bezeichnet wird und darin besteht, die kürzeste Route für ein Netz in einer Schicht ohne Hindernisse und ohne Entwurfsregeln zu finden, ist NP-hart, wenn alle Winkel zulässig sind, und NP-vollständig, wenn nur horizontale und vertikale Drähte zulässig sind . Es wurde auch gezeigt, dass Varianten des Kanalroutings NP-vollständig sind, sowie Routing, das das Übersprechen , die Anzahl der Durchkontaktierungen usw. reduziert . Router versuchen daher selten, ein optimales Ergebnis zu erzielen. Stattdessen basiert fast das gesamte Routing auf Heuristiken, die versuchen, eine Lösung zu finden, die gut genug ist.

Designregeln variieren manchmal erheblich von Schicht zu Schicht. Beispielsweise können die zulässige Breite und der zulässige Abstand in den unteren Schichten vier- oder mehrmals kleiner sein als die zulässigen Breiten und Abstände in den oberen Schichten. Dies führt zu vielen zusätzlichen Komplikationen, mit denen Router für andere Anwendungen wie das Design von Leiterplatten oder Multi-Chip-Modulen nicht konfrontiert sind . Besondere Schwierigkeiten ergeben sich, wenn die Regeln keine einfachen Vielfachen voneinander sind und wenn Durchkontaktierungen zwischen Ebenen mit unterschiedlichen Regeln wechseln müssen.

Arten von Routern

Eine Leiterplatte als Entwurf auf einem Computer (links) und als Leiterplattenbaugruppe mit Komponenten (rechts) realisiert. Die Platine ist doppelseitig, mit Durchgangsbeschichtung, grünem Lötstopplack und einer weißen Legende. Es wurden sowohl oberflächenmontierte als auch Durchgangslochkomponenten verwendet.

Die frühesten Arten von EDA-Routern waren "manuelle Router" - der Verfasser klickte mit der Maus auf den Endpunkt jedes Liniensegments jedes Netzes. Moderne PCB-Design-Software bietet normalerweise "interaktive Router" - der Zeichner wählt ein Pad aus und klickt auf einige Stellen, um dem EDA-Tool eine Vorstellung davon zu geben, wohin es gehen soll, und das EDA-Tool versucht, Drähte so nahe wie möglich an diesem Pfad zu platzieren, ohne zu verletzen Entwurfsregelprüfung (DRC). Einige fortgeschrittenere interaktive Router verfügen über "Push and Shove" -Funktionen (auch als "Shove-beiseite" oder "Automoving" bezeichnet) in einem interaktiven Router. Das EDA-Tool schiebt andere Netze nach Möglichkeit aus dem Weg, um einen neuen Draht dort zu platzieren, wo der Zeichner ihn haben möchte, und um dennoch eine Verletzung der DRC zu vermeiden. Moderne PCB-Design-Software bietet normalerweise auch "Autorouter", die alle verbleibenden nicht gerouteten Verbindungen ohne menschliches Eingreifen weiterleiten.

Die Haupttypen von Autoroutern sind:

Wie Router funktionieren

Viele Router führen den folgenden Gesamtalgorithmus aus:

  • Bestimmen Sie zunächst einen ungefähren Kurs für jedes Netz, häufig durch Routing auf einem groben Gitter. Dieser Schritt wird als globales Routing bezeichnet und kann optional die Schichtzuweisung umfassen. Globales Routing begrenzt die Größe und Komplexität der folgenden detaillierten Routing-Schritte, die Rasterquadrat für Rasterquadrat ausgeführt werden können.

Für detailliertes Routing ist die häufigste Technik das Aufreißen und Umleiten, auch bekannt als Aufreißen und Wiederholen :

  • Wählen Sie eine Reihenfolge, in der die Netze geroutet werden sollen.
  • Leiten Sie jedes Netz nacheinander weiter
  • Wenn nicht alle Netze erfolgreich geroutet werden können, wenden Sie eine der verschiedenen "Bereinigungs" -Methoden an, bei denen ausgewählte Routings entfernt, die Reihenfolge der verbleibenden zu routenden Netze geändert und die verbleibenden Routings erneut versucht werden.

Dieser Vorgang wird wiederholt, bis alle Netze geroutet sind oder das Programm (oder der Benutzer) aufgibt.

Ein alternativer Ansatz besteht darin, Kurzschlüsse, Verstöße gegen Entwurfsregeln, Hindernisse usw. auf einer ähnlichen Grundlage wie überschüssige Kabellänge zu behandeln, dh als begrenzte Kosten, die (zunächst) reduziert werden müssen, und nicht als absolute Kosten, die vermieden werden müssen. Diese Routing-Methode mit mehreren Durchläufen zur "iterativen Verbesserung" wird durch den folgenden Algorithmus beschrieben:

  • Für jeden von mehreren iterativen Durchgängen:
  • Verschreiben oder passen Sie die Gewichtsparameter einer "Zielfunktion" an (mit einem Gewichtsparameterwert für jede Einheit der überschüssigen Drahtlänge und für jede Art von Verletzung). Beispielsweise kann für den ersten Durchgang eine überschüssige Drahtlänge typischerweise mit hohen Kosten verbunden sein, während Konstruktionsverletzungen wie Kurzschlüsse, Nachbarschaft usw. mit geringen Kosten verbunden sind. In späteren Durchgängen wird die relative Reihenfolge der Kosten geändert, sodass Verstöße kostenintensiv sind oder absolut verboten werden können.
  • Wählen Sie eine Sequenz aus (oder wählen Sie sie nach dem Zufallsprinzip aus), in der die Netze während dieses Durchgangs geroutet werden sollen.
  • "Aufreißen" (falls zuvor geroutet) und jedes Netz der Reihe nach umleiten, um den Wert der Zielfunktion für dieses Netz zu minimieren. (Einige der Routings weisen im Allgemeinen Kurzschlüsse oder andere Designverletzungen auf.)
  • Fahren Sie mit dem nächsten iterativen Durchgang fort, bis das Routing abgeschlossen und korrekt ist, nicht weiter verbessert wurde oder ein anderes Beendigungskriterium erfüllt ist.

Die meisten Router weisen Verdrahtungsschichten zu, die überwiegend "x" - oder "y" -Richtungsverdrahtung tragen, obwohl es Router gegeben hat, die die Notwendigkeit einer solchen Zuordnung vermeiden oder verringern. Jeder Ansatz hat Vor- und Nachteile. Eingeschränkte Richtungen erleichtern das Design der Stromversorgung und die Steuerung des Übersprechens zwischen den Schichten. Durch das Zulassen beliebiger Routen kann jedoch der Bedarf an Durchkontaktierungen verringert und die Anzahl der erforderlichen Verdrahtungsschichten verringert werden.

Siehe auch

Verweise

Weiterführende Literatur

Externe Links