Was ich gern gewusst hätte, bevor ich einen Autorouter entwickelt habe
(blog.autorouting.com)- Die Erfahrung aus rund einem Jahr Entwicklung eines Open-Source-PCB-Autorouters für tscircuit zeigt, dass Designs, die das Suchproblem verringern – etwa A*, Visualisierung, Raumaufteilung und Caching – der Schlüssel zur Performance sind
- Der Fokus der Optimierung liegt eher auf der Reduzierung der Iterationszahl als auf Sprache oder Geschwindigkeit pro einzelner Iteration; selbst in JavaScript kann ein klügerer und cachebarer Algorithmus schneller sein als eine Low-Level-Implementierung
- Bei der Raumsuche kann ein Spatial Hash Index einfacher und schneller sein als generische Bäume wie QuadTree, aber bei falsch gewählter Zellgröße entstehen pro Abfrage hohe Fixkosten
- Eine komplexe Autorouter-Pipeline muss Ein- und Ausgaben pro Schritt visualisieren und Iterationen per Animation überprüfbar machen; rekursive Funktionen und Monte-Carlo-Verfahren sind bei Debugging, Optimierung und Determinismus im Nachteil
- Mit dem Greedy Multiplier von Weighted A* lässt sich ein Teil der Optimalität aufgeben und dafür die Geschwindigkeit stark erhöhen; jeder Schritt sollte die Ausfallwahrscheinlichkeit senken, sodass spätere Schritte das Problem leichter lösen können
A* als Standardwerkzeug für die Suche verwenden
- A* ist kein Algorithmus nur für 2D-Gitter, sondern ein grundlegender Algorithmus für verschiedene Formen der informed search
- BFS durchsucht alle benachbarten Knoten, während A* bevorzugt Knoten erkundet, die dem Ziel näher sind
- Da es ein Distanzmaß außerhalb des Graphen verwendet, zählt es zur informed search
- Rekursive Algorithmen ähneln eher der Tiefensuche (DFS), und Schleifen, die Kandidaten oder Nachbarn ohne Sortierung durchsuchen, ähneln eher BFS
- Wenn man bestehenden Code im Stil von BFS oder DFS auf A* umstellt, führt das oft zu großen Performance-Gewinnen
- Im Autorouter werden mehrere Ebenen von A* verwendet, um passende Hyperparameter für das Problem zu finden
- Jede Autorouter-Konfiguration wird als Kandidat ausgeführt
- Konfigurationen, die mit guten Kosten erste Routing-Erfolge zeigen, erhalten mehr Iterationen
- Das ähnelt einem Meta-A*, das Distanzkosten und Iterationskosten gemeinsam bestraft
Der Algorithmus ist wichtiger als die Sprache
- Der tscircuit-Autorouter ist in JavaScript geschrieben, und in Performance-Diskussionen wird oft zuerst die Sprache kritisiert
- Algorithmische Optimierung lässt sich grob in zwei Achsen aufteilen
- Den Algorithmus klüger machen, indem man die nötige Anzahl von Iterationen senkt
- Die Ausführung jeder einzelnen Iteration beschleunigen
- Wer sich zu stark auf Geschwindigkeitsverbesserungen pro Iteration konzentriert, führt womöglich nur einen falschen Ansatz schneller aus
- Zum Beispiel kann ein Ansatz, für Überlappungsprüfungen alles in ein Gitter zu überführen, unabhängig von der Sprache langsam werden
- Ein kluger Algorithmus in JavaScript kann schneller sein als ein einfacher Algorithmus in niedrigstufig optimiertem Assembler
- Es ist sinnvoll, 95 % der Entwicklungszeit darauf zu verwenden, die Iterationszahl zu senken; eine gute Sprachwahl ist die, mit der man schnell beim klügsten und cachebaren Algorithmus landet
Spatial Hash Index kann besser sein als ein Baum
- Bei mehrdimensionaler Raumoptimierung taucht häufig der QuadTree auf, aber generische Baumdatenstrukturen können langsam sein
- Der QuadTree gilt als Datenstruktur, die in 2D- oder 3D-Räumen die Suche nach nahen Objekten von
O(N)aufO(log(N))reduziert, aber ein Baum ist keine informed representation der Daten - Ein Spatial Hash Index hasht nicht das Objekt selbst, sondern seine Position und speichert es in Zellen oder Buckets naher Objekte
- Dieser Ansatz überträgt den schnellen Hash-basierten Zugriff von HashSet und HashMap auf räumliche Daten
- Räumliches Hashing ist wohl deshalb weniger verbreitet, weil man eine passende Zellgröße wählen muss
- Ist die Zellgröße schlecht abgestimmt, entstehen pro Abfrage hohe Fixkosten
- In der Praxis ist es aber wohl gar nicht so schwer, eine vernünftige Zellgröße zu wählen
Raumaufteilung und Caching verändern die Performance
- Leiterplatten wie das Innere eines iPhones können grob 10.000 bis 20.000 Traces haben, und selbst mit erstklassigen EDA-Tools können Teams Monate lang routen
- Eine wichtige einfache Idee beim Autorouting ist: Was bereits geroutet wurde, wurde auch schon früher einmal geroutet
- Spieleentwickler backen Navigations-Meshes vor, und LLMs komprimieren das Internet für die Suche in ihre Gewichte
- Die nächste Generation von Autoroutern kann Probleme räumlich aufteilen und große Caches mit bereits gelösten Lösungen nutzen
- Wenn 99 % des Autorouting-Problems schon im Cache gelöst sind, wird die Geschwindigkeit des eigentlichen Algorithmus weniger wichtig
- Viele aktuelle Algorithmen konzentrieren sich noch nicht genug auf Cache-Wiederverwendbarkeit und Raumaufteilung
- Die Kosten für Speicher und Caching scheinen schneller zu sinken als die Gewinne durch reine Rechenbeschleunigung; 1 GB Cache zu verwenden, um einen Autorouter 50 % schneller zu machen, erscheint nicht als großes Problem
Probleme direkt sehen: mit Visualisierung und Profiling
- Der Grundsatz, dass man ein Problem ohne Visualisierung nicht lösen kann, ist wichtig
- Nur auf Zahlen zu schauen erschwert das Debugging; erstellt man für kleine Teilprobleme eigene Visualisierungen, versteht man das Problem deutlich schneller
- In der Entwicklung des Autorouters beginnt die Problemlösung oft sogar mit der Visualisierung
- Auch ein Teilalgorithmus zur Suche nach 45-Grad-Pfaden wurde visualisiert; er wird in der Path Simplification Phase verwendet, also fast ganz am Ende des Autorouters
- JavaScript-Profiling-Tools zeigen die insgesamt verbrauchte Zeit jeder Codezeile in Millisekunden an
- Dazu führt man JavaScript im Browser aus und öffnet den Tab Performance
- Es gibt außerdem ein Flame Chart und Funktionen zur Speicherverbrauchsanalyse
- Kurzes passendes Video: youtube short
Rekursion und Monte Carlo vermeiden
- Rekursive Funktionen sollte man in performance-orientiertem Code eher vermeiden
- Sie laufen fast immer synchron und lassen sich daher schwer für Animationen zwischendurch unterbrechen
- Sie sind ihrem Wesen nach DFS und lassen sich nicht leicht in A* umwandeln
- Die Anzahl der Iterationen lässt sich nicht leicht nachverfolgen
- In rekursiven Funktionen wirkt Mutabilität unnatürlich, kann für Performance aber wichtig sein
- Iterationsbasierte Implementierungen können schneller sein, weil sie eine
visitedNodes-Menge pflegen und Knoten schon vor der Erkundung prüfen können - Monte-Carlo-Algorithmen nähern sich einer Lösung über Zufall an, sind aber nicht deterministisch, daher schwer zu debuggen und gegenüber Heuristiken nur selten optimal
- Wenn man weiß, wie Kandidaten zu bewerten sind, aber noch nicht, wie man zuverlässig zur Lösung kommt, kann ein Monte-Carlo-Ansatz helfen, Intuition zu gewinnen
- Sobald man etwas hat, das einer Kostenfunktion nahekommt, sollte man bessere Methoden einsetzen als Zufallstechniken wie Monte Carlo oder Simulated Annealing
- Wenn man empfindlich auf lokale Minima reagiert, kann man Hyperparameter oder komplexere Kostenfunktionen in Betracht ziehen
- So wie ein PCB-Designer nicht zufällig Linien auf eine Leiterplatte zeichnet, sollte man in dieser Domäne bessere Heuristiken finden können
Zwischenalgorithmen im selben Koordinatensystem halten
- Der Autorouter besteht derzeit aus einer Pipeline mit 13 Schritten und etwa 20 Teilalgorithmen
- Gemessen werden Iterationszahlen etwa bei Entscheidungen zur Raumaufteilung oder bei der Pfadvereinfachung an Grenzen unabhängig autorouteter Bereiche
- Wenn man Ein- und Ausgabe jedes Schritts überlagert visualisiert, versteht man den Kontext des aktuell gelösten Problems besser
- Probleme in nachgelagerten Schritten, besonders im high density routing, lassen sich oft beheben, indem man die Ausgabe früherer Schritte verbessert
- Beim Entwurf von Teilalgorithmen ist die Versuchung groß, das Problem in seine einfachste Form zu zerlegen und Koordinaten um
(0, 0)zu normalisieren - Solche Normalisierung oder komplexe Transformationen können es erschweren, schnell zu sehen, wie frühe Ergebnisse spätere Schritte beeinflussen
- Es ist vorteilhaft, den Koordinatenraum über den gesamten Lebenszyklus des Algorithmus konsistent zu halten
- Wer sich jeden Schritt der Reihe nach und mit Zoom ansieht, findet leichter den Schritt, der zu einem fehlgeschlagenen Design Rule Check führt
Iterationsanimation und Gitter vermeiden
- Da die Reduzierung der Iterationszahl entscheidend ist, kann man durch Animation der Algorithmus-Iterationen verschwendete Suche intuitiv erkennen
- Animationen helfen besonders beim Abstimmen des Greedy Multiplier
- Ein Fall, in dem ein einfacher Trace eigentlich sofort scheitern sollte, stattdessen aber endlos außen herum nach einer Lösung sucht, war ohne Animation kaum zu erkennen
- Um zu prüfen, ob sich zwei Traces A und B überlappen, gibt es grob zwei Wege
- Man betrachtet jedes Segment von A und B und prüft auf Schnittpunkte
- Man markiert die Gitterzellen, in denen B liegt, und prüft dann, ob B in den Zellen vorkommt, durch die A verläuft
- Der Gitteransatz kann leicht 1000-mal langsamer sein
- Mit schneller Vektormathematik kann ein Dot Product zur Schnittprüfung zweier Segmente schneller sein als ein Speicherzugriff zur Prüfung einer einzelnen Gitterzelle
- Genau genommen sollte man zur Sicherstellung ausreichender Abstände die Distanz zwischen Segmenten berechnen; das ist etwas komplexer als eine Schnittprüfung, aber nicht grundlegend anders
Ausfallwahrscheinlichkeit und Weighted A*
- In Schritten der Raumaufteilung kann man die Wahrscheinlichkeit, dass ein Schritt beim Lösen scheitert, als Frühindikator messen
- Der Unravel Autorouter verfolgt für jeden Capacity Node in jeder Hauptphase der Pipeline die Ausfallwahrscheinlichkeit
- Jeder Schritt konzentriert sich darauf, diese Ausfallwahrscheinlichkeit etwa durch Rekonstruktion benachbarter Knoten oder Re-Routing zu senken
- Ausfallwahrscheinlichkeiten lassen sich tatsächlich messen, und mit veränderten Algorithmen kann auch die Vorhersage besser werden
- Jeder Schritt kann darauf hinarbeiten, die Fehlerwahrscheinlichkeit in späteren Schritten zu senken
- Statt zu viele Einschränkungen auf einmal einzubringen, ist es besser, zunächst die Lösbarkeit zu priorisieren
- Sobald ein Board überhaupt lösbar ist, ist es oft einfacher, eine bestehende Lösung weiterzuverarbeiten, als von Anfang an sofort die optimale Lösung zu erzeugen
Mit dem Greedy Multiplier zwischen Geschwindigkeit und Optimalität abwägen
- Normales A* garantiert eine optimale Lösung, aber wenn Geschwindigkeit wichtiger ist, kann man
f(n)leicht verändern und Weighted A* verwenden - Gewöhnliches A*:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - Weighted A* löst das Problem gieriger und läuft in der Regel deutlich schneller
- Dieser Ansatz wirkt als Greedy Multiplier, der einen Teil der Optimalität aufgibt und dafür die Performance von A* stark erhöht
- Mehr zu Weighted A* und anderen A*-Varianten gibt es hier: weighted A* and other A* variants here
- Spieleentwickler arbeiten oft an sehr ähnlichen Problemen wie Autorouting-Entwickler; bei der Suche nach relevanter Forschung lohnt sich daher ein Blick in Game-Development-Paper
Ein bald erscheinender Autorouter
- Der Autorouter für tscircuit nähert sich der Veröffentlichung
- Die Arbeit wird als Open Source unter der MIT-Lizenz bereitgestellt
- Gelöstes Autorouting kann große Innovationen in der physischen Welt ermöglichen und ist aus Sicht des Autors ein Schlüsselbaustein für das „vibe-building“ von Elektronikprodukten
- Zugehöriger Account: follow me on twitter.
1 Kommentare
Meinungen auf Hacker News
Ich vertraue Autoroutern im Allgemeinen eher nicht, und dasselbe gilt für die AI-Tools, die in diesen Bereich kommen. Trotzdem lässt sich kaum bestreiten, dass es in eCAD eine große Chance gibt, Teile eines Layouts schnell zu erstellen.
Ich würde wohl eher Co-Creation-Tools nutzen als vollständig automatische Tools. In der frühen Entwurfsphase ist die Platzierung der Bauteile oft noch nicht festgelegt, und die Platzierung hat großen Einfluss auf das Routing. Auf der Seite habe ich nicht gesehen, ob die Platzierung in den Algorithmus einbezogen wird. Tools wie Push-and-Shove oder gelegentlich Autocomplete nutze ich bereits.
Dieser Markt ist klein, die Tools sind fragmentiert, die etablierten Anbieter sind träge Großunternehmen, und die Nutzer sind anspruchsvolle Enthusiasten. KiCad gebe ich auf keinen Fall auf. Dass der Autorouter in JavaScript geschrieben ist, sehe ich an sich nicht besonders kritisch, aber ich frage mich, ob geplant ist, sich an CAD-Anbieter oder das Ökosystem von Open-Source-Tools anzudocken, oder ob hier wieder ein neues Ökosystem entstehen soll, in das man die Leute hineinziehen will.
Wenn er cache-freundlich ist, wird es viel schneller, Bauteile zu verschieben und andere Layouts auszuprobieren. JavaScript ist inzwischen mit kleinen Runtimes wie QuickJS oder Proffor ziemlich portabel, und ich denke, man kann es lokal ausführen und direkt große Caches aufbauen.
Lock-in und Fragmentierung des Ökosystems sollten in EDA alle beunruhigen, aber tscircuit und dieser Autorouter sind Technologien unter einer permissiven MIT-Lizenz; damit kann man sie, was in EDA selten ist, so bauen, dass sie mit allen interoperieren.
Nachdem man Footprints, Platzierung, Constraints und manuell geroutete Netze fixiert hatte, konnte man sehr schnell iterieren.
Seit Cadence in den 90ern SPECCTRA übernommen hat, war bei PCB-Autoroutern ziemlich viel Stillstand, daher ist es erfreulich, dass sich wieder jemand dieses Themas annimmt. Die Leute, die SPECCTRA gebaut haben, sind meiner Erinnerung nach in Richtung VLSI gegangen und nicht zurückgekommen; dort lagen wohl Ruhm und Geld. Eine Zeit lang könnte es auch ein Patent-Minenfeld gewesen sein, und vielleicht ist es das immer noch.
Autoplacement war schon damals ein extrem schwer zu beherrschendes Problem und scheint es heute noch zu sein, aber ein generativer AI-Ansatz könnte gut passen. Eine gute generative AI-basierte Erstplatzierung von Bauteilen kann die Gesamtzeit verkürzen. Das größte Problem ist, starrköpfige Leute davon zu überzeugen, dass etwas auch dann gut genug sein kann, wenn es nicht perfekt ist.
Die Versuche, Schaltpläne als Code zu machen, finde ich etwas befremdlich. Als Backend-Format wäre es schön, wenn das gut funktioniert; besonders Fortschritte wie bei jitx, bei denen Designregeln auf Ebene von App Notes und Datenblättern in Bauteilmodelle codiert werden, sehen gut aus. Alle Datenblätter in der für kommerzielle Designs nötigen Tiefe zu lesen, ist deutlich mehr Arbeit, als man denkt, und Junior Engineers diesen Prozess lernen zu lassen ebenso; Automatisierung ist hier also nützlich.
Allerdings scheinen diese Ansätze in der Vorstellung verwurzelt zu sein, Schaltpläne seien Dateneingaben für das Layout, eine Art Quellcode. Schaltpläne sind aber auch Entwurfsdokumente mit einer sorgfältig gewachsenen visuellen Sprache, die auch für Menschen zugänglich sein sollten, die keine EDA-Suite installiert haben. Wer mit Schaltplänen im Adafruit-/Sparkfun-/Shenzhen-Stil gelernt hat, bei denen explizite Verdrahtung minimiert ist, erkennt den Wert guter Schaltpläne vielleicht nicht.
Ein weiterer Punkt ist die Tendenz, sich zu stark auf Analogien zu stützen und PCB-Level-Design wie VLSI-Design machen zu wollen. Ich halte das nicht für völlig unmöglich. Wenn DRC- und Verifikationstools besser werden, kann sich Design auf Bauteilebene VLSI stärker annähern. Aber die Kopplung zwischen Design, EDA/CAM/Simulation, Verifikation, Herstellern, Bestückern, Bauteilanbietern sowie Regulierungs- und Zertifizierungsstellen ist so lose, dass es schon ein großer Erfolg wäre, nur eine Ecke davon richtig hinzubekommen.
Heute läuft UHF-Design mit Impedanzkontrolle eher zusammen mit domänenspezifischen Simulationstools. Deshalb routet man kritische Traces zuerst manuell, erstellt Island Poles und kümmert sich zuletzt um die Stromanschlüsse.
KiCad-Layout ist etwas besser als gar nichts, aber es zu noch einem halbgaren Simulationstool machen zu wollen, wirkt lächerlich.
Gemeint sind Datenbank-Support und die outjob-Funktion. Abgesehen davon geht es eher um Adoption und darum, wie Nutzer diese Funktionen einsetzen; Datenbanken bringen meist mehr interne Bürokratie rund um die Datenpflege mit sich.
Aus Sicht eines Workflows, der Layouts beschleunigt, bewegt sich KiCad meines Erachtens schon ein Stück in diese Richtung. Ein Beispiel ist die etwa mit 7.0 eingeführte Funktion „Trace Autocomplete“. Ich glaube, in pcbnew war das die Taste F; sie legt den Trace für den Track, den man gerade platziert. Zusammen mit dem Shortcut E für „von der anderen Seite des Tracks routen“ steigt die Produktivität deutlich, wenn man zwischen zwei unterschiedlichen Ballout-Grids arbeitet.
In Version 9 kann man Busse oder mehrere Tracks ziehen, wodurch dieser Ablauf noch schneller werden kann.
Ehrlich gesagt: Wenn man zu einer zufriedenstellenden Platzierung kommt und dem Autorouter Constraints für die Routing-Positionen geben kann, könnte man einen erheblichen Teil des Designs dem Autorouter überlassen. Ich habe zum Beispiel letztes Jahr ein Board mit einem NXP iMX8MP und eMMC gemacht; der Ballout an der Prozessorperipherie passte gut zum eMMC-Ballout, sodass man die Chips nur ausrichten und die Leitungen ziehen musste. Wenn er nur gewusst hätte, dass der Datenbus auf der obersten Lage bleiben soll, hätte ein Autorouter das, wofür ich 10 Minuten gebraucht habe, in wenigen Sekunden erledigt.
Autorouter-Projekte haben ein Problem mit ihren Erfolgskriterien. Offenbar gilt etwas erst als „fertig“, wenn es alles auf dem Board behandeln kann; als praktizierender Elektroingenieur will ich das aber nicht. Ich möchte einen Autorouter, der kleine Teilstücke des Designs gemeinsam mit mir bearbeitet, mir Zeit zur Prüfung gibt und dann zum nächsten Teilstück übergeht.
Wenn man sogar Constraints über Layer hinweg angeben kann, wird das mächtig. Zum Beispiel: „Halte alle Netze mit den Namen D0-7 auf Layer 1 und 3, gleiche ihre Längen untereinander auf 5 mm an und nimm D0 als Längenreferenz.“ Wenn das möglich ist, hat man DRAM-Längentuning im Griff, und Designs mit deutlich höherer Komplexität werden auch für normale Nutzer machbar.
Wenn ich Zeit habe, würde ich gern mit einer Demo zeigen, was ich meine.
Es war ein großer Fehler, die Monte-Carlo-Methode in Punkt 8 so vorschnell zu verwerfen
Der Kern von Monte Carlo ist, dass man Genauigkeit gegen Geschwindigkeit eintauschen kann. Je länger man den Algorithmus laufen lässt, desto genauer wird er
Noch interessanter ist, dass man auch die Umkehrung oft nutzen kann: Man kann sehr schnell ein sehr ungenaues Ergebnis bekommen. Statt alle Pfade zu durchsuchen, durchsucht man zum Beispiel nur einen zufällig ausgewählten Pfad
Diese Methode glänzt, wenn man sie in die innerste verschachtelte Schleife eines Algorithmus setzt. Wenn man etwa ein neuronales Netz trainieren will, das Autorouting lernt, aktualisiert die äußere Schleife die Parameter des neuronalen Netzes, und die innere Schleife berechnet einen Pfad durch den Graphen
Mit Monte Carlo kann man diese innere Schleife, die die Genauigkeit steuert, auf eine einzige Iteration reduzieren, sofern kein Bias vorliegt. Die Varianz steigt und die äußere Schleife wird dadurch langsamer, aber Machine Learning kann „theoretisch“ trotzdem lernen
So kann man eine Policy bauen, die intuitiv richtige Entscheidungen auswählt, wie beim Schach oder Go. Bei Varianten der Monte-Carlo Tree Search wie AlphaGo Zero, AlphaChess Zero oder AlphaRouter Zero kann der in den Parametern des neuronalen Netzes codierte riesige Cache nach dem Training auch ohne den Suchteil mit einem einzigen Durchlauf durch das neuronale Netz, also in konstanter Zeit, den besten geschätzten Pfad berechnen. Diese Konstante lässt sich durch mehr Parameter oder längeres Training leicht gegen Speicher und Geschwindigkeit abwägen
MC ist ein Algorithmus, der einem ein Gefühl für die Realität gibt. Er ist langsam, aber fast immer sehr einfach zu implementieren und verlässlich, wenn man mit sehr hoher Sicherheit gegenprüfen will, ob man nicht völlig in die falsche Richtung abgedriftet ist
Eine hervorragende Diskussion über Autorouting, aber dass sie am Ende mit „dem entscheidenden Baustein, der vibe-building von Elektronik ermöglicht“ schließt, tat etwas weh
Das Routing selbst ist einfach. Komplex wird es in dem Moment, in dem man bereits verlegte Leitungen wieder herausreißen muss, um eine neue Leitung zu legen, und die kombinatorische Explosion zuschlägt
Ich vermisse den Autorouter, den es früher in KiCad gab. Er wurde aus etwas unklaren Gründen rund um geistiges Eigentum entfernt, weil der Autor einmal bei einer Autorouting-Firma gearbeitet hatte. Nutzer, die darum baten, ihn wieder aufzunehmen, bekamen Reaktionen nach dem Motto: „Echte Männer benutzen keine Autorouter“
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Ich hoffe, dass dieser Autorouter und die folgenden Tools Menschen ermöglichen, ihr erstes Elektronikprodukt auf den Markt zu bringen, ohne viele Leitfäden oder formale Ausbildung
Natürlich sollte ein guter Autorouter auch für Profis nützlich sein, also hoffe ich, dass er auch dort hilft
Aber als einer dieser schwierigen alten Hasen, die KiCad nicht besonders gern viel Aufwand in Autorouter stecken sehen, muss ich sagen: PCB-Autorouter sind immer ein Ärgernis und funktionieren nicht richtig
Warum das so ist, sieht man an VLSI-Autoroutern. Auch VLSI-Autorouter waren ein Ärgernis und funktionierten nicht richtig. Dann bekamen VLSI-Designs sehr viele Layer, sodass man eigene Layer für vertikales Routing, horizontales Routing und Stromversorgung zuweisen und darüber hinaus noch einige weitere Layer für globale vertikale Verbindungen, globale horizontale Verbindungen und globale Stromversorgung haben konnte
Das grundlegende Problem beim PCB-Autorouting ist, dass PCBs viel mehr Hindernisse haben als VLSI-Chips. Erstens sind die Bauteile selbst Hindernisse und Engpässe. Zweitens blockieren PCB-Vias fast immer alle Layer der Platine, während VLSI-Vias nur die zwei Layer blockieren, die sie verbinden. Drittens sind PCB-Vias meist größer als die Breite des Routing-Metalls. Viertens ist die Zahl der bei PCBs verwendeten Layer viel kleiner als bei VLSI. Üblich sind 4 Layer, von denen nur 2 wirklich für normales Routing genutzt werden; aus Kostengründen gibt es auch viele 2-Layer-Boards, die noch schwieriger automatisch zu routen sind, und 6-Layer-Boards sind eine kleine Minderheit
Im Ergebnis ist PCB-Autorouting eine deutlich komplexere Aufgabe als VLSI-Autorouting
Gut ist, dass der Artikel Visualisierung und Cache-Effekte besonders wichtig nimmt.
Ein paar Dinge stören allerdings. Die Aussage „ein rekursiver Algorithmus ist Tiefensuche, und eine Schleife, die Kandidaten oder Nachbarn ohne Sortierung durchsucht, ist Breitensuche“ ist wohl falsch oder verfehlt die Intuition. DFS und BFS lassen sich beide mit Schleifen oder Rekursion schreiben; der eigentliche Unterschied ist, ob man den nächsten Kandidaten oben oder unten vom Stack nimmt, also ob man einen Stack (FILO) oder eine Queue (FIFO) verwendet.
Auch die Aussage, A* sei die beste Grundlage für jede informationsbasierte Suche, braucht Kontext. A* ist bei der Pfadsuche nützlich, wenn es einen leicht berechenbaren Begriff von „Distanz“ zum Ziel gibt und man nur ein paar Queries auf demselben Graphen ausführt. Wenn man auf einem nahezu statischen Graphen wie einem Straßennetz viele Queries ausführen will, kann ein Vorverarbeitungsalgorithmus wie Contraction Hierarchy besser sein. Wenn man wie beim Traveling-Salesman-Problem optimiert, aber kein festes Ziel hat, können andere lokale Suchheuristiken wie 2-opt besser geeignet sein.
„BFS durchsucht alle benachbarten Knoten, A* priorisiert Knoten nahe am Ziel“ ist zwar ein Unterschied, aber der größere Unterschied ist, dass A* ein dynamischer Algorithmus ist. Dadurch kann man früh abbrechen, sobald man sicher ist, den kürzesten Pfad gefunden zu haben. BFS kann diese Sicherheit möglicherweise erst haben, wenn der gesamte Graph durchsucht ist, und der Graph kann riesig sein.
In den meisten Sprachen lässt sich das leichter ausdrücken, als über einen externen Stack nachzudenken. Wenn man in echtem Code Rekursion sieht, ist es daher wahrscheinlich eher DFS, aber es ist keine strenge Regel.
BFS verwendet eine FIFO-Queue, DFS einen LIFO-Stack, A* meist eine als Heap implementierte Priority Queue.
Das ist eine der grundlegenden Invarianten, die BFS korrekt machen; sobald alle Ziele erreicht sind, kann man also früh abbrechen.
Der Unterschied zwischen A* und BFS liegt darin, dass BFS nicht den kürzesten Pfad zwischen zwei Punkten findet, sondern vom einzelnen Startpunkt aus die kürzesten Pfade zu allen Punkten im Graphen. A* ist ein Trade-off, der eine schwächere Frage beantwortet und dafür einzelne Queries beschleunigt.
Wenn die Problemstruktur es zulässt, kann schon das Ersetzen von Tausenden A*-Aufrufen durch einen einzigen BFS- oder Dijkstra-Aufruf einen großen Geschwindigkeitsschub bringen. Ein weiterer wichtiger Unterschied ist, dass BFS nur in Graphen funktioniert, in denen alle Kantenlängen gleich sind, während A* unterschiedliche Kantenlängen unterstützt. Die beiden sind nicht austauschbar, so wie das Finden des kleinsten Elements in einer Liste kein Ersatz für das Sortieren der Liste ist.
Aussagen wie „Quadtrees und alle allgemeinen Baumdatenstrukturen sind wahnsinnig langsam“, „Bäume sind keine Darstellung, die Informationen über die Daten enthält“ oder „jedes Mal, wenn man einen Baum verwendet, nutzt man statt eines O(~1)-Hash-Algorithmus einen komplexeren O(log N)-Algorithmus“ gehen ziemlich in die falsche Richtung.
Ein Hashing-Ansatz ist in Ordnung, wenn die Punkte gleichmäßig verteilt sind und man nur Bereiche abfragt, die nahe an der gewählten festen Unterteilung liegen. Andernfalls kann dieses O(1) zu O(n) zusammenbrechen.
Wenn man die Datenverteilung nicht kennt, ist ein Baum eine informationshaltige Darstellung.
Bei randomisierten Algorithmen ist es ähnlich. Was macht man, wenn der Suchraum aus Billionen oder mehr Elementen beziehungsweise Möglichkeiten besteht? Und wenn man keine Heuristik hat? In Situationen, in denen weder Brute Force noch ein cleverer Algorithmus funktionieren, werden randomisierte Algorithmen zum Retter.
Für diese konkrete Anwendung sind sie vielleicht nicht nötig, aber verallgemeinernde Behauptungen sollte man besser vermeiden.
Ernsthafter gesagt: Baumbasierte Algorithmen werden tendenziell überschätzt, und Leute scheinen sich zu sehr in Big-O-Verhalten zu verlieren und zu vergessen, dass konstante Faktoren selbst bei Hunderttausenden Elementen sehr wichtig sind. Dasselbe gilt für Dinge wie Datenlokalität. Manchmal ist es schneller, einfach sequenziell zu scannen, als die Buchhaltung einer komplexeren Struktur zu betreiben.
Insgesamt ist es besser, Operationen in kleine Wrapper zu packen, zuerst die einfache Implementierung zu bauen und dann anhand von Messungen zu entscheiden.
Im schlimmsten Fall muss man das ganze Programm für eine andere Struktur neu schreiben, um bessere Performance zu erreichen; meiner Erfahrung nach bringt das Neuschreiben einer Datei von Grund auf aber auch einige kostenlose Verbesserungen mit sich.
Ich habe noch keine zufriedenstellende Methode gefunden, um 2D- oder 3D-Punkte zu speichern und nahegelegene Punkte abzufragen. kD-Trees sind gut, aber ich möchte Punkte im laufenden Betrieb hinzufügen, statt die Struktur für eine feste Menge aufzubauen.
Fast alles passt zu meinen Heuristiken für die Spieleentwicklung. Auch die Wahl von JavaScript kann ich nachvollziehen.
Ich baue gerade ein Game-Modding-Framework, das mit Lisp-artigen S-Expressions arbeitet, und habe dabei gemerkt, dass Optimierungen zur Verkürzung kreativer Iterationszeiten wichtiger sind als alles andere.
Dinge wie A* oder der Lee-Algorithmus sind alle großartig. Bei jeder Art von Flood Fill keine Visualisierung mitzubauen, grenzt an ein Verbrechen. Das wäre eine enorme Verschwendung von Dopamin.
Der Artikel lässt mich fragen, ob Techniken aus dem Umfeld der Spieleentwicklung, die ich noch nicht gelesen habe, auch für solche Probleme nützlich sein könnten. Ich bin sicher nicht der Erste, der dachte, ein Boids-Router wäre ziemlich spannend. Ernster gesagt könnte ein auf Jump Flooding basierendes Signed Distance Field viel leisten.
Besonders der Teil zu Spatial Hashing deckt sich mit meiner Erfahrung. In fast 20 Jahren habe ich nur selten erlebt, dass Baumstrukturen den investierten Aufwand wert waren. Es gibt eine Ausnahme: Mein Lovecraft-artiger Texteditor nutzt recht intensiv einen Trie für reaktive Verarbeitung. Das war eine gute Methode, um 45.000 Wörter in eine komprimierte Zustandsmaschine für die Ereignisverarbeitung zu verwandeln.
Ich habe früher einmal über einen Autorouter für rekursive Muster geschrieben; der Lösungsraum ist klein und lässt sich daher mit bestehenden Machine-Learning-Algorithmen vergleichsweise gut vorhersagen. Beim Autorouting gibt es noch sehr viele interessante, unerforschte Bereiche.
Jump Flooding kannte ich nicht. Für andere ergänzt: Das ist ein Algorithmus, der Distance Fields schnell parallel approximiert. Das könnte definitiv interessant sein, danke für den Hinweis.
Bäume passen auch gut zu rekursiven Algorithmen, und der Autor meinte, es gebe Gründe, iterative Algorithmen rekursiven vorzuziehen; diese Ratschläge greifen also ineinander.
Allgemein betrachtet ist die Unterscheidung zwischen „rekursiv“ und „nicht rekursiv“ etwas künstlich. Die eigentliche Frage lautet: „Übernimmt ein vorgefertigter Algorithmus mit strengen Regeln die Ablaufsteuerung, oder übernehme ich sie?“ Wenn Performance wichtig ist, sollte die Antwort lauten: ich. Sobald der Ausführungszustand in den vom Laufzeitumfeld bereitgestellten Stack abstrahiert wird und sich zur Laufzeit nur noch schwer auf ungewöhnliche Weise verändern lässt, beginnt das hinderlich zu werden.
Die Aussage „95 % der Konzentration sollten darauf verwendet werden, die Zahl der Iterationen zu reduzieren; deshalb ist die Sprache egal“ stimmt bis zu einem gewissen Grad. Wenn man aber in einer verspielten, ausdrucksstarken, interpretierten, abstrakten und langsamen Sprache einen guten und performanten Algorithmus entwickelt hat und Performance weiterhin wichtig ist, kann man dasselbe in einer performanten Low-Level-Sprache neu schreiben und bei Bedarf sogar architekturspezifisches Assembly ergänzen.
Es gibt einen Grund, warum numpy, pandas, OpenCV, TensorFlow nicht in reinem Python geschrieben sind. Python dient dazu, Arbeiten anzustoßen, die in hochperformantem C++/Assembly/CUDA usw. implementiert sind.
So stolz man auch darauf sein mag, den Problemraum erkundet, einen effizienten Algorithmus gefunden und darüber gebloggt zu haben: Wenn man darauf bestanden hätte, alles ausschließlich in reinem Python oder JavaScript zu schreiben, wäre daraus wohl kaum eine populäre Bibliothek für numerisches Rechnen geworden.
Es ist ein interessanter Artikel, aber wenn die algorithmischen Einsichten des Autors einen reinen JavaScript-HEVC-Encoder von einem Tag pro Frame auf drei Stunden pro Frame reduziert hätten, wäre es wohl schwer, dieselbe Schlussfolgerung zu ziehen.
Ich sehe jede Menge Stichwörter, an die ich mich aus der Uni erinnere. Es wäre schön, einmal Anlass zu haben, berühmte und elegante Algorithmen einzusetzen.
In der Praxis baue ich nur UI-Komponenten und REST-APIs, um Elasticsearch-Ergebnisse anzuzeigen. Die interessanten Dinge sind alle in Black Boxes vergraben.
In der Spieleentwicklung gibt es viele Algorithmen, an denen man nicht vorbeikommt. Wenn man also Algorithmen bauen möchte, sollte man etwas wie ein Tower-Defense-Spiel entwickeln; dabei bekommt man viel mit klassischen Algorithmen zu tun.
Mindestens der heutige Informatikabschluss sollte meiner Ansicht nach aufgespalten werden. Der anspruchsvolle mathematische Teil sollte ein eigener Abschluss werden und könnte mit einem neuen AI-bezogenen Abschluss zusammengelegt werden. Datenbanken und Netzwerktheorie sollten ebenfalls eigene Abschlüsse sein, Low-Level-Assembly ebenso. Wie elektronische Bauteile, NAND-Gatter, boolesche Algebra usw. funktionieren, gehört eher in die Elektrotechnik.
Für die Menschen, die der Markt am meisten braucht – solche, die CRUD-Apps am Fließband bauen können –, sollte es, falls man unbedingt auf akademischem Wissen besteht, einen eigenen Abschluss geben; andernfalls gehört das eher in die berufliche Ausbildung.
Gleichzeitig sollte man Gatekeeping bei Einstellungsanforderungen gesetzlich angehen. Unternehmen sollten keine Abschlüsse verlangen dürfen, die kaum etwas mit der tatsächlichen Tätigkeit zu tun haben. Derzeit verschwenden junge Menschen Jahre ihres Lebens und verschulden sich mit fünf- bis sechsstelligen Dollarbeträgen, nur damit Unternehmen leichter Menschen aussortieren können.
Ich arbeite zwar nicht direkt mit 2D-/3D-Raumproblemen, aber die größte Lektion ist der Wert von Visualisierung.
Menschen sind sehr gut darin, Bilder zu verstehen und zu analysieren. Eine weitere Idee ist, mit probabilistischen Methoden oder Brute Force zunächst die Form des Problems zu erfassen und dann nicht nur auf Basis reinen theoretischen Verständnisses, sondern daran angepasst bessere Methoden auszuwählen.
Die Aussage „Die Implementierungssprache ist egal“ mag in diesem Bereich stimmen, aber auf allgemeines Software Engineering übertragen halte ich die Annahme, dass die Sprachwahl keinen Einfluss auf Geschwindigkeit und die nötige Zahl von Iterationen hat, für stark falsch.
Wenn man gerade versucht, exponentielle oder polynomiale Terme in den Griff zu bekommen, kann der Unterschied zwischen Rust oder hartcodiertem Assembly und JavaScript oder VisualBasic ziemlich bedeutungslos werden.