En kompakt digital compute-in-memory Ising-annealer med probabilistisk SRAM-bit i 28 nm för handelsresandeproblemet

Varför smartare rutter och chip spelar roll

Varje dag måste leveranslastbilar, flygplan och datapaket bestämma vilken väg de ska ta så att allt kommer fram i tid till minsta möjliga kostnad. Denna typ av problem, känt som handelsresandeproblemet, blir snabbt överväldigande även för kraftfulla datorer när antalet stopp ökar. Artikeln som ligger bakom denna sammanfattning presenterar en ny typ av specialiserat chip som tar sig an sådana ruttplaneringsproblem mycket effektivare genom att använda idéer hämtade från magnetiska material och bygga in dem direkt i standardminne.

En klassisk gåta: besöka varje stopp en gång

Handelsresandeproblemet ställer en enkel fråga: givet en lista över städer och avstånden mellan dem, vilken är den kortaste rundan som besöker varje stad exakt en gång och återvänder till startpunkten? Problemet är att antalet möjliga rundor exploderar när städer läggs till, så att kontrollera varje alternativ är i praktiken omöjligt. Istället söker moderna metoder efter mycket bra, om än inte alltid perfekta, rutter. En lovande metod imiterar hur ett nätverk av små magneter, kallat en Ising-modell, kan lägga sig i ett lågenergitillstånd som representerar en bra lösning. Genom att försiktigt låta detta nätverk ”vicka” genom slumpmässiga förändringar som gradvis dämpas, kan systemet undkomma dåliga lokala val och hitta bättre rutter.

Gör om ett minneschip till en problemlösare

I stället för att köra denna process i vanliga processorer bygger författarna in den i själva minneshårdvaran, en strategi som kallas compute-in-memory. De utformar ett kompakt chip i 28-nanometerteknik där varje liten minnescell både lagrar avståndsinformation och deltar direkt i beräkningarna. Smart nog använder chippet de naturliga tillverkningsvariationerna i sina minnesceller som en inbyggd källa till slumpmässighet, vilket eliminerar behovet av skrymmande slumptalsgeneratorer. Genom att kort störa de lagrade värdena med en kontrollerad spännings"knuff" kan vissa bitar växla på ett probabilistiskt sätt, vilket ger den milda slumpmässighet som krävs för annealingprocessen utan extra kretsar.

Dela upp stora kartor i små grannskap

Ett av huvudhindren för att använda Ising-liknande lösare på stora ruttplaneringsuppgifter är den enorma mängd data som krävs: en fullständig representation av en 96-stadsrutt skulle normalt behöva ett omfattande nätverk av kopplingar och minne. För att undvika detta grupperar forskarna närliggande städer i små kluster och ordnar dessa kluster i flera nivåer av en hierarki. På högsta nivån löser chippet hur klustren ska ordnas; på nästa nivå förfinas ordningen av städer inom varje kluster; och så vidare. Detta stegvisa tillvägagångssätt minskar mängden minne och kopplingar som behövs, och sänker hårdvarukomplexiteten från något som växer med fjärde potensen av antalet städer till något som bara växer med kvadraten, samtidigt som de sparade avstånden komprimeras ytterligare genom att endast de verkligen nödvändiga packas tätt tillsammans.

Hur chippet uppdaterar många val samtidigt

Inne i chippet bildar grupper om tre städer grundläggande byggstenar som hanteras parallellt. Minnesarrayen är organiserad så att inom varje kluster kan kretsen snabbt beräkna förändringen i total ruttlängd om sektioner av rundan byts plats. Eftersom vissa kluster inte interagerar direkt kan systemet uppdatera alla "udda" kluster i ett steg och alla "jämna" kluster i nästa, vilket snabbar upp sökningen samtidigt som beteendet fortfarande motsvarar att ändringar gjordes en i taget. Under varje runda använder chippet sina brusiga minnesceller för att avgöra om man ska acceptera ett sämre drag med viss sannolikhet—hög i början för att utforska, och lägre senare för att stabilisera—vilket efterliknar avsvalningen i ett metalliskt material och styr rutten mot kortare och kortare avstånd.

Från labbchip till storskaliga rutter

Prototypchippet innehåller blygsamma 6 kilobit av detta specialminne men kan redan lösa 96-stadsinstanser av handelsresandeproblemet på ungefär 620 mikrosekunder medan det använder mindre än en mikrojoule energi. Jämfört med tidigare hårdvara designad för samma uppgift uppnår det förbättringar på upp till hundratals gånger i hur mycket minne som krävs per enhet problemstorlek. Simulationer visar också att genom att placera många sådana minnesblock sida vid sida kan samma design skalas upp till problem med tusentals städer samtidigt som hårdvarutillväxten hålls nästan linjär. För en bred läsekrets är huvudpoängen att genom att omforma ett bekant minneschip till en aktiv problemlösare—och genom att vända oundvikliga tillverkningsvariationer till en användbar funktion—pekar detta arbete mot små, snabba och energieffektiva kretsar som kan hjälpa till att planera komplexa rutter och scheman i realtid.

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

Nyckelord: handelsresandeproblemet, Ising-annealer, compute-in-memory, SRAM-hårdvara, kombinatorisk optimering