Een compacte digitale compute-in-memory Ising-annealer met probabilistische SRAM-bit in 28 nm voor het reizende-koerierprobleem

Waarom slimere routes en chips ertoe doen

Elke dag moeten bezorgwagens, vliegtuigen en datapakketten kiezen welke route ze volgen zodat alles op tijd en tegen zo laag mogelijke kosten aankomt. Dit type puzzel, bekend als het Reizende-Koerierprobleem, wordt al snel onhandelbaar voor zelfs krachtige computers naarmate het aantal stops groeit. Het artikel achter deze samenvatting introduceert een nieuw soort gespecialiseerde chip die dergelijke routeplanningsproblemen veel efficiënter aanpakt, met ideeën ontleend aan magnetische materialen en direct ingebouwd in standaardcomputermemory.

Een klassiek raadsel: elke locatie precies één keer bezoeken

Het Reizende-Koerierprobleem stelt een eenvoudige vraag: gegeven een lijst steden en de afstanden daartussen, wat is de kortste ronde die elke stad precies eenmaal bezoekt en terugkeert naar het beginpunt? Het probleem is dat het aantal mogelijke tochten explodeert zodra er meer steden bijkomen, waardoor het praktisch onmogelijk is alle opties na te gaan. Moderne methoden zoeken daarom naar zeer goede, zo niet perfecte, routes. Een veelbelovende aanpak bootst na hoe een netwerk van kleine magneetjes, een Ising-model genoemd, kan bezinken in een laag-energietoestand die een goede oplossing voorstelt. Door dit netwerk gecontroleerd te laten "wiggelen" via willekeurige veranderingen die geleidelijk afnemen, ontsnapt het systeem aan slechte lokale keuzes en vindt het betere routes.

Een geheugenchip ombouwen tot probleemoplosser

In plaats van dit proces in gewone processors uit te voeren, bouwen de auteurs het in de geheugenhardware zelf, een strategie die compute-in-memory heet. Ze ontwerpen een compacte chip in 28-nanometertechnologie waarbij elke kleine geheugencel zowel afstandsinformatie opslaat als direct deelneemt aan de berekeningen. Slim gebruik van de natuurlijke fabricage-onregelmatigheden van de geheugencellen levert een ingebouwde bron van willekeurigheid op, waardoor omvangrijke generatoren van willekeurige getallen overbodig worden. Door de opgeslagen waarden kortstondig te verstoren met een gecontroleerde spannings"duw", flippen sommige bits op een probabilistische manier en leveren zo de zachte willekeur die de annealing vereist zonder extra schakelingen.

Grote kaarten opdelen in kleine buurten

Een van de grootste hindernissen bij het toepassen van Ising-achtige oplossers op grote routeplanningsproblemen is de enorme hoeveelheid benodigde data: een volledige representatie van een tour met 96 steden zou normaal gesproken een uitgestrekt netwerk aan verbindingen en geheugen vergen. Om dit te vermijden groeperen de onderzoekers nabijgelegen steden in kleine clusters en rangschikken zij die clusters in meerdere hiërarchische niveaus. Op het hoogste niveau lost de chip op hoe clusters geordend moeten worden; op het volgende niveau verfijnt hij de volgorde van steden binnen elke cluster; enzovoort. Deze stapsgewijze aanpak reduceert de hoeveelheid geheugen en verbindingen drastisch, waardoor de hardwarecomplexiteit daalt van iets dat met de vierde macht van het aantal steden groeit naar iets dat slechts kwadratisch groeit, en de opgeslagen afstanden worden verder gecomprimeerd door alleen de werkelijk benodigde waarden compact op te slaan.

Hoe de chip veel keuzes tegelijk bijwerkt

In de chip vormen groepen van drie steden de basiseenheden die parallel worden behandeld. De geheugenarray is zo georganiseerd dat binnen elke cluster het circuit snel kan berekenen hoe de totale tourlengte verandert als delen van de tour worden verwisseld. Omdat sommige clusters niet direct met elkaar interfereren, kan het systeem eerst alle "oneven" clusters tegelijk bijwerken en in de volgende stap alle "even" clusters, wat de zoektocht versnelt terwijl het toch lijkt alsof wijzigingen één voor één plaatsvinden. Tijdens elke ronde gebruikt de chip zijn noisy geheugencellen om te beslissen of een slechtere zet met een bepaalde waarschijnlijkheid wordt geaccepteerd—hoog aan het begin om te verkennen en later lager om te stabiliseren—waardoor het gedrag het afkoelen van een metaal nabootst en de route naar steeds kortere afstanden stuurt.

Van laboratoriumchip naar grootschalige routes

De prototypechip bevat een bescheiden 6 kilobit van dit speciale geheugen en kan toch al instanties van het Reizende-Koerierprobleem met 96 steden oplossen in ongeveer 620 microseconden terwijl hij minder dan een microjoule energie verbruikt. Vergeleken met eerdere hardware voor dezelfde taak behaalt hij verbetering tot honderden malen in hoeveel geheugen er per probleemgrootte nodig is. Simulaties tonen ook aan dat door veel van zulke geheugeneenheden naast elkaar te plaatsen, hetzelfde ontwerp kan opschalen naar problemen met duizenden steden terwijl de hardwaregroei bijna lineair blijft. Voor een algemene lezer is de kernboodschap dat door een vertrouwde geheugenchip om te vormen tot een actieve probleemoplosser—en door onvermijdelijke fabricageverschillen om te zetten in een nuttige eigenschap—dit werk wijst op kleine, snelle en energiezuinige hardware die kan helpen bij het plannen van complexe routes en schema's in real time.

Bronvermelding: 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

Trefwoorden: reizende-koerierprobleem, Ising-annealer, compute-in-memory, SRAM-hardware, combinatorische optimalisatie