Ein kompakter digitaler Compute-in-Memory-Ising-Annealer mit probabilistischem SRAM-Bit in 28 nm für das Problem des Handlungsreisenden

Warum intelligentere Routen und Chips wichtig sind

Täglich müssen Lieferwagen, Flugzeuge und Datenpakete entscheiden, welchen Weg sie nehmen, damit alles pünktlich und mit minimalen Kosten ankommt. Dieses Rätsel, bekannt als Traveling-Salesman-Problem (Problem des Handlungsreisenden), wird für selbst leistungsstarke Computer rasch unüberschaubar, je mehr Zwischenstationen hinzukommen. Die in dieser Zusammenfassung vorgestellte Arbeit führt eine neue Art spezialisierten Chips ein, der solche Routenplanungsaufgaben deutlich effizienter angeht, indem er Konzepte aus der Physik magnetischer Materialien nutzt und sie direkt in Standardspeicher einbettet.

Ein klassisches Rätsel: jede Station genau einmal besuchen

Das Problem des Handlungsreisenden stellt eine einfache Frage: Gegeben eine Liste von Städten und die Distanzen zwischen ihnen — welche Tour ist die kürzeste, die jede Stadt genau einmal besucht und zum Start zurückkehrt? Das Problem ist, dass die Anzahl möglicher Touren mit jedem zusätzlichen Ort explosionsartig wächst, sodass ein vollständiges Durchsuchen aller Optionen praktisch unmöglich wird. Stattdessen suchen moderne Ansätze nach sehr guten, wenn auch nicht unbedingt perfekten, Routen. Ein vielversprechender Ansatz imitiert, wie ein Netzwerk winziger Magneten — ein sogenanntes Ising-Modell — in einen energiearmen Zustand übergeht, der eine gute Lösung repräsentiert. Indem dieses Netzwerk durch gezielte, zufällige Änderungen „wackeln“ darf, die allmählich abklingen, kann das System schlechten lokalen Lösungen entkommen und bessere Touren finden.

Aus einem Speicherchip wird ein Problemlöser

Anstatt diesen Prozess auf herkömmlichen Prozessoren laufen zu lassen, bauen die Autorinnen und Autoren ihn direkt in die Speicherhardware ein — eine Strategie, die als Compute-in-Memory bezeichnet wird. Sie entwerfen einen kompakten Chip in 28-Nanometer-Technologie, bei dem jede winzige Speicherzelle sowohl Distanzinformationen speichert als auch direkt an den Berechnungen teilnimmt. Clevererweise nutzt der Chip natürliche Fertigungsunvollkommenheiten der Speicherzellen als eingebaute Zufallsquelle und eliminiert so den Bedarf an sperrigen Zufallszahlengeneratoren. Durch ein kurzes Anregen der gespeicherten Werte mit einem kontrollierten Spannungsimpuls kippen einige Bits auf probabilistische Weise um und liefern die sanfte Zufälligkeit, die für den Annealing-Prozess nötig ist — ganz ohne zusätzliche Schaltungsteile.

Große Karten in kleine Nachbarschaften zerlegen

Ein zentrales Hindernis bei der Anwendung von Ising-ähnlichen Lösungsansätzen auf große Routenplanungen ist die schiere Datenmenge: eine vollständige Darstellung einer 96-Städte-Tour würde üblicherweise ein riesiges Netz an Verbindungen und Speicher erfordern. Um das zu umgehen, gruppieren die Forschenden nahe beieinander liegende Städte in kleine Cluster und ordnen diese Cluster in mehreren Hierarchieebenen an. Auf der höchsten Ebene löst der Chip die Reihenfolge der Cluster; auf der nächsten Ebene verfeinert er die Reihenfolge der Städte innerhalb der Cluster; und so weiter. Dieser stufenweise Ansatz reduziert die Menge an benötigtem Speicher und Verbindungen drastisch — die Hardwarekomplexität sinkt von einer Abhängigkeit vierten Grades auf eine, die nur quadratisch wächst — und die gespeicherten Distanzen werden zusätzlich komprimiert, indem nur wirklich benötigte Werte dicht gepackt abgelegt werden.

Wie der Chip viele Entscheidungen zugleich aktualisiert

Im Inneren des Chips bilden Dreiergruppen von Städten die grundlegenden Bausteine, die parallel bearbeitet werden. Das Speicherarray ist so organisiert, dass innerhalb jedes Clusters die Schaltung schnell die Änderung der Gesamtstrecke berechnen kann, falls Teile der Tour vertauscht werden. Da sich manche Cluster nicht direkt gegenseitig beeinflussen, kann das System in einem Schritt alle „ungeraden“ Cluster und im nächsten Schritt alle „geraden“ Cluster aktualisieren — das beschleunigt die Suche, während das Verhalten so wirkt, als wären die Änderungen nacheinander vorgenommen worden. Während jeder Runde nutzt der Chip seine verrauschten Speicherzellen, um mit gewisser Wahrscheinlichkeit zu entscheiden, ob ein schlechterer Zug akzeptiert wird — zu Beginn hoch, um zu explorieren, später niedriger, um sich zu stabilisieren — und ahmt so das Abkühlen eines Metalls nach, wodurch die Route zu immer kürzeren Distanzen gelenkt wird.

Vom Laborchip zu großskaligen Routen

Der Prototypchip enthält bescheidene 6 Kilobit dieses speziellen Speichers, kann aber bereits Instanzen des 96-Städte-Problems in rund 620 Mikrosekunden lösen und dabei weniger als eine Mikrojoule Energie verbrauchen. Gegenüber früherer Hardware für dieselbe Aufgabe erreicht er Verbesserungen von bis zu mehreren Hundertfach beim benötigten Speicher pro Problemgröße. Simulationen zeigen außerdem, dass durch das nebeneinander Platzieren vieler solcher Speicherblöcke das gleiche Design auf Probleme mit Tausenden Städten skaliert werden könnte, während das Hardwarewachstum nahezu linear bleibt. Für den Laien ist die wichtigste Erkenntnis: Indem ein vertrauter Speicherchip zu einem aktiven Problemlöser umgestaltet wird — und unvermeidliche Fertigungsfehler als nützliches Merkmal genutzt werden — weist diese Arbeit auf kleine, schnelle und energieeffiziente Hardware hin, die helfen kann, komplexe Routen und Zeitpläne in Echtzeit zu planen.

Zitation: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Schlüsselwörter: Problem des Handlungsreisenden, Ising-Annealer, Compute-in-Memory, SRAM-Hardware, kombinatorische Optimierung