Ein vollständig vernetzter Annealer, der auf ein Multi-Chip-System erweiterbar ist und über einen Multi-Policy-Mechanismus verfügt, wurde von Tokyo Tech-Forschern entwickelt, um eine breite Klasse von Problemen der kombinatorischen Optimierung (CO) schnell und effizient zu lösen, die für reale Szenarien relevant sind. Der Annealer mit dem Namen Amorphica hat die Fähigkeit, Parameter entsprechend einem bestimmten Ziel-CO-Problem fein abzustimmen, und hat potenzielle Anwendungen in Logistik, Finanzen, maschinellem Lernen und so weiter.
Die moderne Welt hat sich an eine effiziente Warenlieferung direkt vor unserer Haustür gewöhnt. Aber wussten Sie, dass die Realisierung einer solchen Effizienz die Lösung eines mathematischen Problems erfordert, nämlich die bestmögliche Route zwischen allen Zielen? Dieses als „Problem des Handlungsreisenden“ bekannte Problem gehört zu einer Klasse mathematischer Probleme, die als Probleme der „kombinatorischen Optimierung“ (CO) bekannt sind.
Wenn die Anzahl der Ziele zunimmt, wächst die Anzahl möglicher Routen exponentiell, und ein Brute-Force-Verfahren, das auf einer erschöpfenden Suche nach der besten Route basiert, wird unpraktisch. Stattdessen wird ein Ansatz namens „Glühberechnung“ verwendet, um ohne erschöpfende Suche schnell die beste Route zu finden.
Eine von Forschern der Tokyo Tech durchgeführte numerische Studie hat jedoch gezeigt, dass es zwar viele Glühberechnungsmethoden gibt, aber keine Methode, die zur Lösung einer breiten Klasse von CO-Problemen geeignet ist. Daher besteht ein Bedarf an einem Ausheilungsmechanismus, der mehrere Ausheilungsverfahren (einen Multi-Policy-Mechanismus) aufweist, um auf eine Vielzahl solcher Probleme abzuzielen.
Glücklicherweise hat dasselbe Forscherteam unter der Leitung von Assistenzprofessor Kazushi Kawamura und Professor Masato Motomura vom Tokyo Institute of Technology (Tokyo Tech) über einen neuen Annealer berichtet, der einen solchen Multi-Policy-Ansatz oder „metamorphes Annealing“ aufweist. Ihre Ergebnisse werden in veröffentlicht Fortsetzung von ISSCC2023 und wird auf der bevorstehenden International Solid-State Circuits Conference 2023 vorgestellt.
„In der Glühberechnung wird ein CO-Problem als Energiefunktion in Form von (Pseudo-)Spinvektoren dargestellt. Wir gehen von einer anfänglich randomisierten Spinvektorkonfiguration aus und aktualisieren sie dann stochastisch, um die minimalen Energiezustände zu finden, indem wir ihre (Pseudo-)Spinvektoren reduzieren. Dies spiegelt den Glühprozess von Metallen wider, bei dem heiße Metalle kontrolliert abgekühlt werden“, erklärt Dr. Kawamura. „Unser Annealer namens Amorphica verfügt über mehrere Glühmethoden, einschließlich einer neuen, die von unserem Team vorgeschlagen wurde. Dadurch kann die Glühmethode an das jeweilige spezifische CO-Problem angepasst werden.“
Das Team entwarf Amorphica, um die Einschränkungen früherer Annealer zu überwinden, nämlich dass ihre Anwendbarkeit auf nur wenige CO-Probleme beschränkt ist. Dies liegt zum einen daran, dass diese Annealer lokal verbunden sind, das heißt, sie können nur mit Spinmodellen umgehen, die eine lokale Inter-Spin-Kopplung aufweisen. Ein weiterer Grund ist, dass sie keine Flexibilität in Bezug auf Glühverfahren und Parametersteuerung haben. Diese Probleme wurden in Amorphica gelöst, indem ein Vollverbindungs-Spin-Modell verwendet und fein steuerbare Glühmethoden und -parameter integriert wurden. Darüber hinaus führte das Team eine neue Annealing-Richtlinie namens „Ratio-Controlled Parallel Annealing“ ein, um die Konvergenzgeschwindigkeit und Stabilität bestehender Annealing-Methoden zu verbessern.
Darüber hinaus kann Amorphica zu einem Multi-Chip-Vollverbindungssystem mit reduziertem Datentransfer zwischen den Chips erweitert werden. Beim Testen von Amorphica im Vergleich zu einer GPU stellten die Forscher fest, dass es bei nur (1/500) Stromverbrauch bis zu 58-mal schneller war, was bedeutet, dass es etwa 30.000-mal energieeffizienter ist.
„Mit einem Full-Connection-Annealer wie Amorphica können wir jetzt mit beliebigen Topologien und Dichten von Interspin-Kopplungen umgehen, selbst wenn sie unregelmäßig sind. Dies wiederum würde es uns ermöglichen, reale CO-Probleme wie die damit verbundenen zu lösen zu Logistik, Finanzen und maschinellem Lernen“, schließt Prof. Motomura.
Mehr Informationen:
Amorphica: 4-Replica 512 Fully Connected Spin 336MHz Metamorphic Annealer mit programmierbarer Optimierungsstrategie und Compressed-Spin-Transfer Multi-Chip Extension, Proceeding of ISSCC2023.
Konferenz: www.isscc.org/