Was ich gern gewusst hätte, bevor ich einen Autorouter entwickelt habe

„Wichtige Lektionen, um den schnellsten automatischen Leiterbahnrouter (Autorouter) der Welt zu bauen“

A*-Algorithmus überall einsetzen

• A* ist der mächtigste und flexibelste Algorithmus für Suchprobleme
• Er lässt sich nicht nur auf einfachen 2D-Grids, sondern auf viele unterschiedliche Probleme anwenden
• A* ist eine „informationsgestützte Suche“, die im Vergleich zu BFS schneller und effizienter zuerst Knoten in Zielnähe untersucht
• Bereits verwendeter DFS- oder BFS-Code kann in den meisten Fällen durch A* ersetzt werden
• Zur Leistungssteigerung wurde eine Technik verwendet, bei der mehrere A*-Instanzen ausgeführt und den Konfigurationen mit besserer Performance mehr Ressourcen zugewiesen werden

Der Algorithmus ist wichtiger als die Programmiersprache

• Es gab überhaupt kein Problem damit, den Autorouter in Javascript zu entwickeln
• Der Kern der Optimierung besteht darin, die Anzahl der Wiederholungen zu reduzieren
• Wichtiger als die Sprachperformance ist, „wie kluge Algorithmen wie schnell gebaut werden können“
• Javascript eignet sich weniger für rohe Geschwindigkeit als für smarte Algorithmen

Spatial Hash Indexing ist effizienter als Baumstrukturen

• Baum-basierte Datenstrukturen wie Quadtree sind im Allgemeinen langsam
• Ein Spatial Hash Index hasht die Positionen von Objekten und verarbeitet räumlich nahe Objekte gruppiert
• Hash-basierte Strukturen bieten eine Suchleistung nahe O(1)
• Damit es effektiv ist, muss die Cell-Größe gut gewählt werden, was aber nicht besonders schwierig ist

Raumaufteilung und Cache sind 1000-mal wichtiger als der Algorithmus

• Selbst komplexe Leiterplatten haben meist wiederkehrende Muster
• Wie in der Spieleentwicklung kann die Performance durch das Cachen vorberechneter Ergebnisse drastisch verbessert werden
• Cache-fähige Strukturen und Raumaufteilung werden der Kern zukünftiger Autorouter sein
• Speicherplatz wird schnell günstiger, und selbst einige GB Cache können große Leistungsgewinne bringen

Ohne Visualisierung ist Problemlösung unmöglich

• Für jedes Problem wurden zuerst Visualisierungswerkzeuge gebaut
• Durch Visualisierung ließ sich die Debugging-Geschwindigkeit um mehr als das Zehnfache steigern
• Selbst bei einfachen Algorithmus-Schritten lässt sich durch Visualisierung die Ursache von Problemen schnell erkennen

Die Profiling-Tools von Javascript sind äußerst nützlich

• Im Performance-Tab der Chrome-Entwicklertools lässt sich die Laufzeit pro Codeabschnitt prüfen
• Auch ohne zusätzliches Framework lassen sich Flame Chart, Speichernutzung usw. leicht analysieren
• Ein sehr nützliches Werkzeug für Performance-Debugging

Keine rekursiven Funktionen verwenden

• Rekursive Funktionen sind in der Regel synchron und lassen sich schwer auf A* umstellen
• Iterative Implementierungen sind schneller und erleichtern das Nachverfolgen besuchter Knoten
• In rekursiven Funktionen sind Zustandsänderungen schwierig und ineffizient
• Nach Möglichkeit schleifenbasierte Implementierungen verwenden

Monte-Carlo-Algorithmen möglichst vermeiden

• Auf Zufälligkeit basierende Algorithmen sind nicht deterministisch und schwer zu debuggen
• Domänenspezifische Heuristiken liefern immer eine bessere Performance
• Kein PCB-Designer zeichnet Leiterbahnen zufällig → kein realistischer Ansatz
• Allerdings kann es in der Anfangsphase nützlich sein, um ein Gefühl für das Problem zu bekommen

Algorithmus-Schritte im realen Problemraum verankern

• Wenn Subalgorithmen relativ zum Ursprung normalisiert werden, wird es schwer, den Gesamtfluss zu verstehen
• Durch die Visualisierung der Ein- und Ausgaben jeder Phase lässt sich erkennen, welche Phase Fehler verursacht
• Wichtig ist, das Koordinatensystem konsistent zu halten und den Algorithmusfluss beizubehalten

Iterative Prozesse als Animation visualisieren

• So lässt sich visuell erkennen, wie ineffizient der Algorithmus sucht
• Animationen sind äußerst wirksam, um Wiederholungen zu reduzieren und die Effizienz zu steigern
• Problemfälle lassen sich leicht erkennen (z. B. eine Suche, die in einer Endlosschleife steckt)

Für Kreuzungserkennung reicht Mathematik ohne Grid aus

• Statt ein Grid zu verwenden, ist der Einsatz von Vektormathematik deutlich schneller
• In vielen Fällen sind mathematische Operationen schneller als Speicherzugriffe
• Dank LLMs ist auch die Mathematik zur Kreuzungserkennung leicht implementierbar geworden
• Unnötige Grid-Nutzung ist eine Ursache für Performance-Verlust

Die Lösbarkeit priorisieren, indem die Ausfallwahrscheinlichkeit jeder Phase gemessen wird

• Für jeden Raumaufteilungs-Knoten lässt sich die Ausfallwahrscheinlichkeit abschätzen
• Knoten mit hoher Wahrscheinlichkeit, in späteren Phasen zu scheitern, werden bevorzugt neu aufgebaut oder erneut durchsucht
• Die Ausfallwahrscheinlichkeit lässt sich klar messen und bietet mehr Verbesserungspotenzial als Heuristiken
• Die gesamte Lösbarkeit zu erhöhen kann wirksamer sein, als nur auf Optimierung zu zielen

Mit Weighted A* ist eine 100-fache Beschleunigung möglich

• Normales A* garantiert den optimalen Pfad, ist aber langsam
• Weighted A* sucht gieriger und kann die Geschwindigkeit massiv erhöhen
• Die Implementierung ist möglich, indem einfach das Gewicht in f(n) = g(n) + w * h(n) gesetzt wird
• Selbst wenn die Optimalität etwas leidet, lässt sich das Problem viel schneller lösen
• Eine Technik, die auch in der Spieleentwicklung häufig verwendet wird und einen Blick wert ist

[GN⁺]

Hacker-News-Kommentare

• Das vorschnelle Verwerfen der Monte-Carlo-Methode ist ein großer Fehler

  • Die Monte-Carlo-Methode zeichnet sich dadurch aus, dass man Genauigkeit gegen Geschwindigkeit eintauschen kann
  • Je länger der Algorithmus läuft, desto genauer wird er
  • Umgekehrt kann man auch schnell ungenaue Ergebnisse erhalten
  • Statt alle Pfade zu durchsuchen, wird nur ein zufällig ausgewählter Pfad untersucht
  • Es ist effektiv, Monte Carlo in der innersten Schleife eines Algorithmus zu verwenden
  • Beim Training eines neuronalen Netzes aktualisiert zum Beispiel die äußere Schleife die Parameter des Netzes, während die innere Schleife Pfade durch den Graphen berechnet
  • Mit Monte Carlo kann man die Genauigkeit der inneren Schleife auf eine einzige Iteration reduzieren
  • Dadurch kann man intuitiv eine Strategie aufbauen, die stets die richtige Entscheidung trifft
  • In Schach oder Go kann man Varianten der Monte-Carlo-Baumsuche verwenden, um den optimalen Pfad zu berechnen

• Ich vertrete die Position: "Vertraue keinem Autorouter"

  • Im Bereich eCAD gibt es große Chancen, die Layout-Geschwindigkeit zu erhöhen
  • Wahrscheinlicher ist der Einsatz von Co-Creation-Tools als von vollständigen Automatisierungswerkzeugen
  • Zu Beginn eines Designs ist die Platzierung noch nicht festgelegt, was großen Einfluss auf das Routing hat
  • Auf der Seite konnte ich nicht erkennen, ob die Platzierung Teil des Algorithmus ist
  • Ich bin neugierig auf den Plan für einen in JavaScript geschriebenen AR

• Der Artikel spricht wichtige Punkte zu Visualisierung und Cache-Effekten an

  • Rekursive Algorithmen sind Tiefensuche
  • DFS und BFS können iterativ oder rekursiv geschrieben werden
  • A* ist für die Pfadsuche nützlich
  • BFS untersucht alle benachbarten Knoten, während A* bevorzugt Knoten durchsucht, die dem Ziel näher sind
  • A* ist ein dynamischer Algorithmus, der den kürzesten Pfad mit hoher Sicherheit frühzeitig beenden kann

• Eine hervorragende Diskussion über Autorouting

  • Das Routing selbst ist einfach
  • Komplex wird es, wenn bereits geroutete Verbindungen entfernt werden müssen, um Platz für etwas Neues zu schaffen
  • Ich vermisse den Autorouter von KiCAD

• 95 % des Fokus sollten darauf liegen, die Anzahl der Iterationen zu reduzieren

  • Wenn Performance dann immer noch wichtig ist, sollte man es in einer Low-Level-Sprache neu schreiben
  • numpy, pandas, OpenCV und TensorFlow sind in performanterem C++/Assembler/CUDA implementiert

• QuadTree und allgemeine baumartige Datenstrukturen sind sehr langsam

  • Bäume sind keine Informationsdarstellung der Daten
  • Hashing-Ansätze eignen sich nur dann, wenn Punkte gleichmäßig verteilt sind
  • Zufallsalgorithmen sind nützlich, wenn der Suchraum sehr groß ist

• Fast alles deckt sich mit Heuristiken aus der Spieleentwicklung

  • A*, Lees Algorithmus usw. sind alle großartig
  • Ohne Visualisierung Flood Fill zu schreiben, ist ein Verbrechen
  • Räumliches Hashing passt besonders gut zu meinen Erfahrungen

• "Spatial-Hash-Indexing > Baum-Datenstrukturen" ist in dieser Domäne sinnvoll, sollte aber nicht als weltweite Wahrheit gelten

  • Wenn Punkte nicht gleichmäßig verteilt sind, kann die Hash-Funktion schlecht sein

• Ich erinnere mich an die Schlagwörter aus dem Studium

  • Ich hatte keine Gelegenheit, ausgefallene Algorithmen zu verwenden
  • Stattdessen baue ich UI-Komponenten und REST-APIs

• Als jemand, der nicht direkt mit 2D/3D-Raumproblemen zu tun hat, ist der Wert der Visualisierung die wichtigste Lehre

  • Menschen sind hervorragend darin, Bilder zu verstehen und zu analysieren
  • Die Idee, probabilistische oder brute-forceartige Methoden zu verwenden, um die Form eines Problems zu verstehen, ist wichtig