En ny processor, der løser notorisk komplekse matematiske problemer

Forskere ved Tokyo Institute of Technology har designet en ny processorarkitektur, der kan løse kombinatoriske optimeringsproblemer meget hurtigere end eksisterende. Kombinatoriske optimeringer er komplekse problemer, der dukker op på tværs af mange områder inden for videnskab og teknik og er vanskelige for konventionelle computere at håndtere, gør specialiserede processorarkitekturer meget vigtige.

Tit, de matematiske problemer, der bruges i ingeniørvidenskab og andre videnskabelige applikationer, involverer komplekse beregninger, der ligger uden for moderne computeres kapacitet med hensyn til tid og ressourcer. Dette er tilfældet for kombinatoriske optimeringsproblemer.

Kombinatorisk optimering består i at lokalisere et optimalt objekt eller en optimal løsning i et begrænset sæt af mulige. Sådanne problemer viser sig i økonomi som porteføljeoptimering, i logistik som det velkendte "rejsende sælgerproblem, "i maskinlæring, og i lægemiddelopdagelse. Imidlertid, nuværende computere kan ikke klare disse problemer, når antallet af variabler er højt.

Et team af forskere fra Tokyo Institute of Technology, i samarbejde med Hitachi Hokkaido University Laboratory, og University of Tokyo, har nu designet en ny processorarkitektur til specifikt at løse kombinatoriske optimeringsproblemer udtrykt i form af en Ising-model. Ising-modellen blev oprindeligt brugt til at beskrive de magnetiske tilstande af atomer (spin) i magnetiske materialer. Imidlertid, denne model kan bruges som en abstraktion til at løse kombinatoriske optimeringsproblemer, fordi udviklingen af ​​spin, som har tendens til at nå den såkaldte laveste energitilstand, afspejler, hvordan en optimeringsalgoritme søger efter den bedste løsning. Faktisk, tilstanden af ​​spins i den laveste energitilstand kan direkte kortlægges til løsningen af ​​et kombinatorisk optimeringsproblem.

Den foreslåede processorarkitektur, kaldet STATICA, er fundamentalt forskellig fra eksisterende processorer, der beregner Ising-modeller, kaldet annealere. En begrænsning af de fleste rapporterede annealere er, at de kun tager hensyn til spin-interaktioner mellem nabopartikler. Dette giver mulighed for hurtigere beregning, men begrænser deres mulige anvendelser. I modsætning, STATICA er fuldt forbundet, og alle spin-til-spin-interaktioner tages i betragtning. Mens STATICAs behandlingshastighed er lavere end hastigheden for lignende annealere, dens beregningsskema er bedre, da den bruger parallel opdatering.

I de fleste annealere, udviklingen af ​​spins (opdatering) beregnes iterativt. Denne proces er i sagens natur seriel, hvilket betyder, at spin-skift beregnes en efter en, fordi skiftet af et spin påvirker alle de øvrige i samme iteration. I STATICA, opdateringsprocessen udføres parallelt ved hjælp af såkaldte stokastiske celleautomater. I stedet for at beregne spin-tilstande ved hjælp af selve spins, STATICA skaber replikaer af spins og spin-til-replik interaktioner bruges, giver mulighed for parallel beregning. Dette sparer enormt meget tid på grund af det reducerede antal nødvendige trin. "Vi har bevist, at konventionelle tilgange og STATICA udleder den samme løsning under visse betingelser, men STATICA gør det i N gange færre trin, hvor N er antallet af spins i modellen, " siger prof. Masato Motomura, der ledede dette projekt. Desuden, forskerholdet implementerede en tilgang kaldet delta-drevet spin-opdatering. Fordi kun spins, der ændrede sig i den forrige iteration, er vigtige, når man beregner det følgende, der bruges et vælgerkredsløb, der kun involverer de spins, der vendte i hver iteration.

STATICA tilbyder reduceret strømforbrug, højere behandlingshastighed, og bedre nøjagtighed end andre annealere. "STATICA sigter mod at revolutionere annealing-processorer ved at løse optimeringsproblemer baseret på den matematiske model for stokastiske celleautomater. Vores indledende evalueringer har givet stærke resultater, " siger prof. Motomura. Yderligere forbedringer vil gøre STATICA til et attraktivt valg for kombinatorisk optimering.