LIMO: Niedrigenergie-In-Memory-Annealer und Matrix-Multiplikationsprimitive für Edge-Computing

Intelligentere Routen und schlankere Chips

Jeden Tag stehen Unternehmen vor Aufgaben wie dem Finden der kürzesten Route für einen Lieferwagen mit Tausenden von Stopps oder dem schnellen Durchsuchen von Bildern nach Gesichtern mit einer akkubetriebenen Kamera. Solche Probleme belasten heutige Computer, die große Mengen an Daten zwischen Speicher und Prozessor hin- und herschieben. Dieses Papier stellt LIMO vor, einen neuen, energieeffizienten Rechenbaustein, der Daten an Ort und Stelle hält, während er schwierige Routenplanungsaufgaben löst und KI-Modelle ausführt — wodurch künftige Edge-Geräte schneller und energieeffizienter werden.

Warum gute Routen so schwer zu finden sind

Kern dieses Werks ist das bekannte Problem des Handlungsreisenden: Gegeben viele Städte, finde die kürzeste Rundreise, die jede Stadt genau einmal besucht und zum Start zurückkehrt. Für kleine Karten finden exakte mathematische Werkzeuge die optimale Lösung. Steigt die Zahl der Städte jedoch in den Bereich von Zehntausenden, explodiert die Anzahl möglicher Touren und selbst starke Rechner kommen ins Stocken. Heuristiken wie simuliertes Annealing können diesen riesigen Raum nach guten, wenn auch nicht perfekten, Touren durchsuchen, indem sie gelegentlich schlechtere Zwischenschritte zulassen, um nicht in lokalen Minima stecken zu bleiben. Trotzdem erkunden Standardansätze bei sehr großen Problemen den Suchraum ineffizient und verschwenden Zeit durch das ständige Verschieben von Daten zwischen Speicher und CPU — die sogenannte „Memory Wall”.

Eine neue Art, die Möglichkeiten zu durchsuchen

Die Autoren schlagen einen neuen Algorithmus namens Significance Weighted Annealed Insertion (SWAI) vor, der die Art verändert, wie Kandidatentouren erforscht werden. Anstatt ständig Paare von Städten zu vertauschen — eine Methode, die mit zunehmender Stadtzahl schlecht skaliert — baut SWAI Touren Schritt für Schritt auf, indem jeweils eine neue Stadt eingefügt wird. In jedem Schritt wählt er manchmal die nächste Stadt nach dem nächstliegenden Kriterium (eine gierige Wahl) und setzt manchmal auf kontrollierte Zufälligkeit, die kürzere Kandidatenkanten bevorzugt, längere aber nicht vollständig ausschließt. Diese Verzerrung wird im Laufe der Zeit angepasst: zu Beginn mutiger, im Verlauf konservativer. Weil jeder Schritt Optionen in einer Weise betrachtet, die nur linear mit der Anzahl der Städte wächst, erkundet der Algorithmus langfristige Verbesserungen effektiver als traditionelles simuliertes Annealing.

Rechnen im Speicher mit eingebauter Zufälligkeit

LIMO macht diesen Algorithmus zur Hardware, indem Schaltung und Suchmethode eng mitgestaltet werden. Im Kern steht ein modifiziertes Speicherarray, das sowohl die aktuelle Tour als auch die Abstände zwischen Städten speichert und die zentralen Aktualisierungsschritte ausführt, ohne ständig mit einem separaten Prozessor zu kommunizieren. Zufällige Entscheidungen, die der Algorithmus benötigt, stammen aus winzigen magnetischen Bauelementen, sogenannten Spin-Transfer-Torque-Magnet-Tunnel-Junctions, die bei geeigneter Stromsteuerung auf natürliche Weise in unvorhersehbarer Weise ihren Zustand ändern. Die Designer wandeln diese physikalische Zufälligkeit in digitale Bits um und verwenden einfache Vergleiche, um die probabilistischen Entscheidungen des Algorithmus zu realisieren. Da die meisten Operationen digital bleiben und direkt im Speicher erfolgen, entfallen sperrige Wandler und empfindliche Analogschaltungen, was sowohl Energie als auch Fläche spart.

Große Probleme in Stücke teilen

Um wirklich große Routenplanungsaufgaben mit bis zu 85.900 Städten zu bewältigen, nutzt das System eine Teil-und-Herrsche-Strategie. Eine leichte geometrische Methode gruppiert nahe beieinander liegende Städte in Cluster, bis jeder Cluster klein genug ist, um in einen einzelnen LIMO-Baustein zu passen. Die Hardware löst viele dieser Teilrouten parallel und fügt sie dann wieder zu einer vollständigen Tour zusammen. Zusätzliche Verfeinerungsschritte polieren die globale Route weiter: Abschnitte der Tour werden von der Hardware neu optimiert, und ein klassisches „2-opt“-Aufräumen auf einem konventionellen Prozessor entfernt verbleibende Kreuzungen. In Tests auf Standard-Benchmarks lieferte dieser kombinierte Ansatz qualitativ bessere Touren als frühere spezialisierte Annealing-Maschinen und erreichte auf dem größten Problem etwa fünffach schnellere Lösungen.

Von schwierigen Routen zu effizienter KI

LIMO ist nicht auf Routenplanung beschränkt. Dasselbe Speicherarray kann auch als Baustein für neuronale Netze dienen, indem es Vektor–Matrix-Multiplikationen ausführt — die Kernoperation hinter Bild- und Mustererkennung. Anstatt energieintensive, präzise Wandler zum Auslesen analoger Signale zu verwenden, setzt LIMO auf sehr einfache Sensorschaltungen, die nur das Vorzeichen des akkumulierten Signals erfassen, und kompensiert diese Grobheit durch hardwarebewusstes Training der Netze. Bei Aufgaben wie Bildklassifikation und Gesichtserkennung erreichten diese Netze eine Genauigkeit nahe an standardmäßigen Softwaremodellen, während sie Energieverbrauch und Reaktionszeit gegenüber herkömmlichen Compute-in-Memory-Chips reduzierten. Für alltägliche Anwender bedeutet das: Kameras, Drohnen und andere Edge-Geräte könnten eines Tages komplexe Planungsaufgaben lösen und KI-Modelle länger aus einer Batterie betreiben — dank intelligenter Suche und Berechnung direkt dort, wo die Daten liegen.

Zitation: Holla, A., Chatterjee, S., Sen, S. et al. LIMO: Low-power in-memory-annealer and matrix-multiplication primitive for edge computing. npj Unconv. Comput. 3, 10 (2026). https://doi.org/10.1038/s44335-026-00054-8

Schlüsselwörter: In-Memory-Computing, Problem des Handlungsreisenden, Hardware-Annealing, energieeffiziente KI, Edge-Computing