Kombinatoriska optimeringsproblem (COP) uppstår inom olika områden, såsom skiftplanering, trafikstyrning och läkemedelsutveckling. Det är dock svårt att lösa dem med traditionella datorer inom en rimlig tidsram.
Som alternativ har annealing-processorer (AP), som är specialiserad hårdvara för att lösa COP, fått stor uppmärksamhet. De baseras på Ising-modellen, där COP-variabler presenteras som magnetiska spinn och begränsningar som interaktioner mellan spinn. Lösningar erhålls genom att hitta det spinnläge som minimerar systemets energi.
Det finns två typer av Ising-modeller, den glest kopplade modellen och den fullt kopplade modellen. Glest kopplade modeller erbjuder hög skalbarhet genom att tillåta fler spinn, men kräver att COP omvandlas för att passa modellen. Fullt kopplade modeller, å andra sidan, tillåter att alla COP mappas direkt utan omvandling, vilket gör dem mycket eftertraktade.
De är dock begränsade i kapacitet (antal spinn) och precision (interaktionsbitbredd). Tidigare studier har implementerat fullt Ising-modeller med en skalbar struktur som kan öka kapaciteten med hjälp av applikationsspecifika integrerade kretsar (ASIC), men deras interaktionsbitbredd är fast, vilket gör vissa COP svåra att lösa.
I en ny studie har ett forskarteam från Japan, ledt av professor Takayuki Kawahara från Institutionen för elektroteknik vid Tokyo University of Science, Japan, utvecklat ett innovativt dubbelt skalbart annealing-bearbetningssystem (DSAPS) som kan skala både kapacitet och precision samtidigt med samma skalbara struktur. Deras studie publiceras i tidskriften IEEE Access och presenterades vid 2024 International Conference on Microelectronics.
DSAPS uppnår dubbel skalbarhet genom att manipulera ∆E-block, som ansvarar för beräkningen av systemets energi, med hjälp av två strukturer. Dvs. den konventionella högkapacitetsstrukturen och en ny högprecisionsstruktur. Varje ∆E-block motsvarar en storskalig integrerad (LSI) chip på ett CMOS-baserat AP-kort och innehåller interaktionsmatrisen och spinnarna.
Den högkapacitetsstrukturen delar upp varje ∆E-block i mindre delblock som beräknas separat och sedan läggs samman av ett kontrollblock på AP-kortet. Detta gör det möjligt att öka antalet spinn genom att helt enkelt dela upp ∆E-blocket i fler delblock.
Den högprecisa strukturen gör det möjligt att beräkna flera ∆E-block, med samma spinnummer och interaktioner, på olika bitnivåer. Kontrollblocket kombinerar sedan deras beräkningar genom att utföra bitförskjutningar, vilket resulterar i en högre total interaktionsbitbredd. Till exempel kan ett system med fyra ∆E-block som arbetar på olika bitnivåer med ett enda kontrollblock hantera fyra gånger den ursprungliga interaktionsbitbredden.
”DSAPS är ett revolutionerande system som möjliggör samtidig expansion av antalet spinn och interaktionsbitbredd genom att styra flera identiska LSI-chip med ett enda fältprogrammerbart gate array-kontrollblock”, förklarar professor Kawahara. ”Dessutom kan detta system användas för både glest kopplade och fullt kopplade Ising-modeller.”
För att demonstrera systemets praktiska användbarhet implementerade forskarna två DSAPS-konfigurationer på ett CMOS-AP-kort med hjälp av spinn-trådar: en med 2 048 spinn, med 10-bitars interaktioner och fyra trådar, och en annan med 1 024 spinn, 37-bitars interaktioner och två trådar. Detta är en avsevärd förbättring jämfört med ASIC, som vanligtvis har interaktionsbitbredder på endast 4 till 8 bitar.
Valideringstester på MAX-CUT-problem visade att båda DSAPS uppnådde över 99 % noggrannhet jämfört med de bästa kända teoretiska resultaten. I 0-1-ryggsäcksproblemet uppvisade dock DSAPS med 10-bitars interaktion en stor genomsnittlig avvikelse på 99 %, medan 37-bitars konfigurationen uppvisade en mycket lägre genomsnittlig avvikelse på endast 0,73 %, nära den som ses i CPU-baserade emuleringar. Detta understryker vikten av att välja en DSAPS-konfiguration som är anpassad till egenskaperna hos mål-COP.
”Detta system kommer att visa sig avgörande för utvecklingen av skalbara AP:er för att lösa komplexa COP:er i verkligheten”, kommenterar professor Kawahara. ”Vår avdelning har under de senaste tio åren främjat forskning om LSI-implementering av helt kopplade Ising-maskiner. Från och med 2025 kommer detta system att införas som ett av studentexperimenten för alla tredjeårsstudenter, vilket kommer att förbättra utbildningen inom halvledardesign.”
Sammantaget markerar denna studie ett viktigt steg framåt för utvecklingen av skalbara, högprecisa, fullt kopplade Ising-maskiner med lovande tillämpningar inom olika områden.
Mer information: Dong Cui et al, Dual Scalable Annealing Processing System That Scales Number of Spins and Interaction Bit Width Simultaneously, IEEE Access (2025). DOI: 10.1109/ACCESS.2025.3553542
