Wissenschaftler der EPFL, von AMD und der Universität Novi Sad haben eine alte Schwachstelle in dem Algorithmus entdeckt, der Millionen von rekonfigurierbaren Chips programmiert, die weltweit eingesetzt werden. Diese Entdeckung könnte die Art und Weise, wie zukünftige Generationen von Chips entworfen und programmiert werden, neu definieren.
Viele Branchen, darunter die Telekommunikation, die Automobilindustrie, die Luft- und Raumfahrt und die Teilchenphysik, verlassen sich auf eine bestimmte Art von Chips, die als FPGA (Field-Programmable Gate Array) bezeichnet wird. Im Gegensatz zu herkömmlichen Chips können FPGAs fast unbegrenzt neu konfiguriert werden, was sie in sich schnell entwickelnden Bereichen, in denen die Entwicklung eines individuellen Chips Jahre dauern und ein Vermögen kosten würde, unverzichtbar macht. Diese Flexibilität hat jedoch auch einen Nachteil: Die Effizienz von FPGAs hängt stark von der Software ab, mit der sie programmiert werden.
Seit Ende der 1990er Jahre bildet ein Algorithmus, der als PathFinder bekannt ist, die Grundlage für das FPGA-Routing. Seine Aufgabe ist es, Tausende von kleinen Schaltkreiskomponenten zu verbinden, ohne Überschneidungen zu erzeugen. Jahrzehntelang funktionierte er so gut, dass er zum Standard wurde. Als die Schaltkreise jedoch immer grösser wurden, hatten die Ingenieure mit frustrierenden Verlangsamungen und gelegentlichen Ausfällen zu kämpfen. Modelle, die hätten funktionieren sollen, wurden oft mit dem Etikett "unmöglich zu routen" versehen.
Zusammen mit Kollegen der Universität Novi Sad und des Halbleiterherstellers AMD hat das Labor für parallele Systemarchitektur (PARSA) der Fakultät für Informatik und Kommunikation einen neuen Schritt unternommen, um das Räderwerk dieses klassischen Algorithmus zu entwirren.
In ihrem Artikel, der auf dem 33.IEEE International Symposium on Custom Field Programmable Computing Machines mit dem Preis für den besten Artikel ausgezeichnet wurde, enthüllten sie, warum es zu diesen Ausfällen kommt und wie die Grenzen von PathFinder überwunden werden können.
Versagen des Algorithmus
"Eigentlich ist es nicht überraschend, dass PathFinder manchmal versagt", sagt Shashwat Shrivastava, Doktorand an der PARSA und Hauptautor des Artikels. "Schon früh zeigten die Teams, dass das Problem hinter dem Routing von FPGAs äusserst komplex ist. Später fanden die Schöpferinnen und Schöpfer des ursprünglichen Algorithmus zusammen mit einigen Mitarbeiterinnen und Mitarbeitern Fälle, in denen PathFinder niemals erfolgreich sein würde, aber sie merkten an, dass solche Fälle in der Praxis nicht vorkommen würden." Jahrzehntelang schien er Recht zu haben - PathFinder funktionierte erstaunlich gut.
"PathFinder funktionierte so gut, dass die Leute, wenn er versagte, selten den Algorithmus in Frage stellten. Anstatt nachzusehen, was im Inneren vor sich ging, änderten sie die Parameter, modifizierten die Schaltkreise oder gingen zu grösseren FPGAs über", ergänzt Stefan Nikolic, EPFL-Alumnus und heute Professor an der Universität Novi Sad. "Das liegt zum Teil daran, dass es ziemlich schwierig ist, an Beispielen von praktischer Bedeutung zu verstehen, was PathFinder macht. Moderne Schaltkreise sind so gross, dass ihre Signale einen wahren Dschungel auf dem Chip bilden."
Willkommen im Wald
"Wir mussten uns also jeden einzelnen Baum in diesem Dschungel ansehen", fährt Shashwat Shrivastava fort, und ich meine wirklich Bäume. "Jedes Signal, d. h. eine Verbindung, die Informationen zwischen den Komponenten des Schaltkreises transportiert, muss mehrere Ziele erreichen, ohne sich mit anderen Signalen zu überschneiden. Das Routing von FPGAs besteht im Wesentlichen darin, für jedes Signal auf dem Chip einen Baum zu erstellen."
Während das Team an einem anderen Projekt arbeitete, das auf PathFinder aufbaute, erzielte es immer wieder Ergebnisse, die die Intuition herausforderten. Zunächst schoben die Wissenschaftler die Schuld auf externe Faktoren, nicht auf den Algorithmus selbst. Schliesslich erkannten sie, dass sie kontrollierte Beispiele brauchten: kleine, schwierige Fälle, für die es sicherlich eine Lösung gab und in denen PathFinder erfolgreich sein musste.
shashwat Shrivastava erklärt: "Wir brauchten echte, praktische Beispiele, und zwar in grosser Zahl, um zu verstehen, was wirklich vor sich ging. Also schufen wir ein Framework, um kleine, schwierige Probleme automatisch aus echten Schaltkreisen zu extrahieren. Als wir beobachteten, wie PathFinder mit diesen Problemen umging, entdeckten wir weitere, die sehr lange verborgen geblieben waren."
Die Stärke der Partnerschaft
"Dieser Durchbruch wäre ohne die Unterstützung der Industrie viel schwieriger zu erreichen gewesen", sagt Mirjana Stojilovic, Doktorandenberaterin von Shashwat Shrivastava. "Von Anfang an haben wir mit Chirag Ravishankar und Dinesh Gaitonde von AMD zusammengearbeitet. Sie halfen uns, die FPGAs so nah wie möglich an den kommerziellen Geräten zu modellieren und so die tatsächliche Auswirkung unserer Entdeckungen zu gewährleisten."
Nachdem der Rahmen stand, ging es schnell weiter. Das Team stellte fest, dass PathFinder häufig grössere Routingbäume als nötig erstellte und damit das Risiko von Überschneidungen erhöhte. Das Problem lag in der Reihenfolge, in der es neue Zweige erstellte und zu den Bäumen hinzufügte.
"Im Nachhinein betrachtet ist es intuitiv, aber irgendwie blieb es viele Jahre lang weitgehend unbemerkt", sagt Shashwat Shrivastava. "Unsere erste Lösung war einfach: Wir probierten verschiedene Reihenfolgen aus und wählten diejenige, die den kleinsten Baum ergab. Experimentell hat das überraschend gut funktioniert."
Ausblick auf die Zukunft
Das Team untersucht nun skalierbarere Lösungen. "Ich bin besonders stolz darauf, dass die Praktikanten des Summer@EPFL-Programms einen bedeutenden Beitrag geleistet haben. Einer von ihnen, Sun Tanaka, ist auch Co-Autor des Artikels", fügt Mirjana Stojilovic hinzu. "Unsere Entdeckung könnte die Art und Weise, wie Millionen von FPGAs programmiert werden, neu definieren und das Design zukünftiger Generationen dieser rekonfigurierbaren Chips beeinflussen."
https://doi.ieeecomputersociety.org/10.1109/FCCM62733.2025.00060
