LIMO: lågströms minnes-annealer och matris-multiplikationsprimtiv för kantberäkning

Smartare rutter och slankare chip

Varje dag ställs företag inför gåtor som att hitta den kortaste rutten för en leveransbil som besöker tusentals stopp eller snabbt skanna bilder för att hitta ansikten med en batteridriven kamera. Dessa problem belastar dagens datorer, som flyttar stora mängder data fram och tillbaka mellan minne och processor. Denna artikel introducerar LIMO, en ny typ av lågströms beräkningsblock som håller data på plats samtidigt som det löser svåra ruttplaneringsuppgifter och kör artificiella intelligensmodeller, vilket gör framtida kantenheter snabbare och mer energieffektiva.

Varför det är så svårt att hitta bra rutter

I kärnan av detta arbete finns det välkända Resande försäljarens problem: givet många städer, hitta den kortaste rundresa som besöker varje stad en gång och återvänder till startpunkten. För små kartor kan exakta matematiska verktyg hitta den bästa lösningen. Men när antalet städer växer till tiotusental exploderar antalet möjliga turer, och även kraftfulla datorer saktas ned. Heuristiker som simulerad annealing kan söka i detta enorma utrymme efter bra, om än inte perfekta, turer genom att ibland acceptera sämre mellanlösningar för att undvika lokal fastlåsning. Standardmetoder utforskar dock fortfarande sökutrymmet ineffektivt för mycket stora problem och slösar tid på att flytta data mellan minne och CPU, vilket träffar den så kallade "minnesmuren".

En ny metod för att söka möjligheterna

Författarna föreslår en ny algoritm kallad Significance Weighted Annealed Insertion (SWAI) som omformar hur kandidat­turer utforskas. Istället för att konstant byta par av städer, vilket skalas dåligt när antalet städer ökar, bygger SWAI turer steg för steg genom att infoga en ny stad åt gången. Vid varje steg väljer den ibland nästa närmaste stad (ett girigt val) och ibland förlitar sig på kontrollerad slump som gynnar kortare kandidatkanter men inte helt utesluter längre. Denna partiskhet justeras över tid, börjar mer äventyrligt och blir mer konservativ ju längre sökningen fortskrider. Eftersom varje steg granskar alternativ på ett sätt som endast växer linjärt med antalet städer, utforskar algoritmen långdistansförbättringar mer effektivt än traditionell simulerad annealing.

Beräkning inne i minnet med inbyggd slump

LIMO förvandlar denna algoritm till hårdvara genom att tätt samskapa kretsdesign och sökmetod. I dess kärna finns en modifierad minnesmatris som lagrar både den aktuella turen och avstånden mellan städerna, och utför de viktiga uppdateringsstegen utan att ständigt kommunicera med en separat processor. De slumpval som algoritmen behöver kommer från små magnetiska enheter kallade spin-transfer-torque magnetic tunnel junctions, som naturligt växlar tillstånd på ett oförutsägbart sätt när de drivs med rätt ström. Designerna omvandlar denna fysiska slumpmässighet till digitala bitar och använder enkla jämförelser för att implementera de probabilistiska besluten i algoritmen. Eftersom de flesta operationer förblir digitala och sker direkt inne i minnet undviks klumpiga omvandlare och känsliga analoga kretsar, vilket sparar både energi och yta.

Dela upp stora problem i bitar

För att hantera verkligt stora ruttplaneringsuppgifter med upp till 85 900 städer använder systemet en dela-och-härska-strategi. En lättvikts geometrisk metod grupperar närliggande städer i kluster tills varje kluster är tillräckligt litet för att rymmas i ett enda LIMO-block. Hårdvaran löser många av dessa delrutter parallellt och syr sedan ihop dem till en komplett tur. Ytterligare förfiningssteg putsa den globala rutten: segment av turen optimeras om av hårdvaran, och en klassisk "2-opt"-rensning på en vanlig processor tar bort återstående korsande vägar. I tester på standardbenchmarkar producerade denna kombinerade metod rutter av högre kvalitet än tidigare specialiserade annealing-maskiner, samtidigt som den nådde svar upp till ungefär fem gånger snabbare på det största problemet.

Från svåra rutter till effektiv AI

LIMO är inte begränsat till ruttplanering. Samma minnesmatris kan också fungera som byggsten för neurala nätverk genom att utföra vektor–matris-multiplikationer, den centrala operationen bakom bild- och mönsterigenkänning. Istället för att använda strömslukande, precisa omvandlare för att läsa analoga signaler förlitar sig LIMO på mycket enkla sensoriska kretsar som bara fångar tecknet på den ackumulerade signalen, och kompenserar för denna grovhet genom att träna nätverken på ett hårdvaruvanligt sätt. Vid bildklassificering och ansiktsdetektering nådde dessa nätverk noggrannhet nära standard mjukvarumodeller, samtidigt som de minskade energianvändning och svarstid jämfört med konventionella compute-in-memory-chips. För vardagsanvändare innebär detta att kameror, drönare och andra kantenheter en dag skulle kunna lösa komplexa planeringsuppgifter och köra AI-modeller längre på batteri, tack vare smartare sökningar och beräkningar direkt där datan bor.

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

Nyckelord: in-memory computing, resande försäljarens problem, hårdvaru-annealing, energieffektiv AI, edge computing