Forskare vid Tokyo Institute of Technology har designat en ny processorarkitektur som kan lösa kombinatoriska optimeringsproblem mycket snabbare än befintliga. Kombinatoriska optimeringar är komplexa problem som dyker upp inom många vetenskaps- och teknikområden och som är svåra för konventionella datorer att hantera, vilket gör specialiserade processorarkitekturer mycket viktiga.

Ofta, de matematiska problemen som används inom ingenjörsvetenskap och andra naturvetenskapliga tillämpningar involverar komplexa beräkningar som ligger utanför moderna datorers kapacitet när det gäller tid och resurser. Detta är fallet för kombinatoriska optimeringsproblem.

Kombinatorisk optimering består av att lokalisera ett optimalt objekt eller lösning i en ändlig uppsättning möjliga. Sådana problem dyker upp inom finans som portföljoptimering, inom logistik som det välkända "resande säljarproblemet, "i maskininlärning, och i drogupptäckten. Dock, nuvarande datorer klarar inte av dessa problem när antalet variabler är högt.

Ett team av forskare från Tokyo Institute of Technology, i samarbete med Hitachi Hokkaido University Laboratory, och Tokyos universitet, har nu designat en ny processorarkitektur för att specifikt lösa kombinatoriska optimeringsproblem uttryckta i form av en Ising-modell. Ising-modellen användes ursprungligen för att beskriva magnetiska tillstånd hos atomer (spin) i magnetiska material. Dock, denna modell kan användas som en abstraktion för att lösa kombinatoriska optimeringsproblem eftersom utvecklingen av spin, som tenderar att nå det så kallade lägsta energitillståndet, speglar hur en optimeringsalgoritm söker efter den bästa lösningen. Faktiskt, tillståndet för snurren i det lägsta energitillståndet kan direkt mappas till lösningen av ett kombinatoriskt optimeringsproblem.

Den föreslagna processorarkitekturen, kallas STATICA, skiljer sig fundamentalt från befintliga processorer som beräknar Ising-modeller, kallas glödgarn. En begränsning av de flesta rapporterade glödglödgningsmedel är att de endast tar hänsyn till spinninteraktioner mellan närliggande partiklar. Detta möjliggör snabbare beräkning, men begränsar deras möjliga tillämpningar. I kontrast, STATICA är helt uppkopplad och alla spin-to-spin-interaktioner beaktas. Medan STATICAs bearbetningshastighet är lägre än för liknande glödgarn, dess beräkningsschema är bättre, eftersom den använder parallell uppdatering.

I de flesta glödgarn, utvecklingen av snurr (uppdatering) beräknas iterativt. Denna process är till sin natur seriell, vilket innebär att snurrbyten beräknas en efter en eftersom bytet av ett snurr påverkar alla andra i samma iteration. I STATICA, uppdateringsprocessen utförs parallellt med så kallade stokastiska cellautomater. Istället för att beräkna snurrtillstånd med själva snurren, STATICA skapar kopior av snurren och spin-till-replik-interaktioner används, möjliggör parallell beräkning. Detta sparar enormt mycket tid på grund av det minskade antalet steg som behövs. "Vi har bevisat att konventionella metoder och STATICA härleder samma lösning under vissa förhållanden, men STATICA gör det i N gånger färre steg, där N är antalet snurr i modellen, " säger prof. Masato Motomura, som ledde detta projekt. Vidare, forskargruppen implementerade en metod som kallas deltadriven spin-uppdatering. Eftersom endast snurr som ändrades i föregående iteration är viktiga när du beräknar följande, en väljarkrets används som endast involverar de snurr som vänt i varje iteration.

STATICA erbjuder minskad strömförbrukning, högre bearbetningshastighet, och bättre noggrannhet än andra glödgarn. "STATICA syftar till att revolutionera glödgningsprocessorer genom att lösa optimeringsproblem baserat på den matematiska modellen av stokastiska cellautomater. Våra första utvärderingar har gett starka resultat, " säger Prof. Motomura. Ytterligare förfining kommer att göra STATICA till ett attraktivt val för kombinatorisk optimering.