Wetenschappers van het Tokyo Institute of Technology hebben een nieuwe processorarchitectuur ontworpen die combinatorische optimalisatieproblemen veel sneller kan oplossen dan bestaande. Combinatorische optimalisaties zijn complexe problemen die zich voordoen op vele gebieden van wetenschap en techniek en die voor conventionele computers moeilijk te hanteren zijn, waardoor gespecialiseerde processorarchitecturen erg belangrijk zijn.

Vaak, de wiskundige problemen die worden gebruikt in technische en andere wetenschappelijke toepassingen omvatten complexe berekeningen die de capaciteiten van moderne computers in termen van tijd en middelen te boven gaan. Dit is het geval voor combinatorische optimalisatieproblemen.

Combinatorische optimalisatie bestaat uit het lokaliseren van een optimaal object of optimale oplossing in een eindige reeks van mogelijke. Dergelijke problemen manifesteren zich in financiën als portefeuilleoptimalisatie, in de logistiek als het bekende "traveling salesman problem, " bij machinaal leren, en bij het ontdekken van medicijnen. Echter, huidige computers kunnen deze problemen niet aan als het aantal variabelen groot is.

Een team van onderzoekers van het Tokyo Institute of Technology, in samenwerking met Hitachi Hokkaido University Laboratory, en de Universiteit van Tokio, heeft nu een nieuwe processorarchitectuur ontworpen om specifiek combinatorische optimalisatieproblemen op te lossen, uitgedrukt in de vorm van een Ising-model. Het Ising-model werd oorspronkelijk gebruikt om de magnetische toestanden van atomen (spins) in magnetische materialen te beschrijven. Echter, dit model kan worden gebruikt als een abstractie om combinatorische optimalisatieproblemen op te lossen omdat de evolutie van spin, die de neiging heeft om de zogenaamde laagste energietoestand te bereiken, weerspiegelt hoe een optimalisatie-algoritme naar de beste oplossing zoekt. In feite, de toestand van de spins in de laagste energietoestand kan direct worden toegewezen aan de oplossing van een combinatorisch optimalisatieprobleem.

De voorgestelde processorarchitectuur, genaamd STATICA, is fundamenteel anders dan bestaande processors die Ising-modellen berekenen, annealers genoemd. Een beperking van de meeste gerapporteerde annealers is dat ze alleen spin-interacties tussen naburige deeltjes beschouwen. Dit zorgt voor een snellere berekening, maar beperkt hun mogelijke toepassingen. In tegenstelling tot, STATICA is volledig verbonden en alle spin-to-spin interacties worden overwogen. Hoewel de verwerkingssnelheid van STATICA lager is dan die van vergelijkbare annealers, het rekenschema is beter, omdat het parallelle updates gebruikt.

In de meeste ontharders, de evolutie van spins (updaten) wordt iteratief berekend. Dit proces is inherent serieel, wat betekent dat spin-omschakelingen één voor één worden berekend, omdat het omschakelen van één spin de rest in dezelfde iteratie beïnvloedt. In STATICA, het actualiseringsproces wordt parallel uitgevoerd met behulp van zogenaamde stochastische celautomaten. In plaats van spintoestanden te berekenen met behulp van de spins zelf, STATICA maakt replica's van de spins en er worden spin-naar-replica-interacties gebruikt, parallelle berekening mogelijk te maken. Dit scheelt enorm veel tijd doordat er minder stappen nodig zijn. "We hebben bewezen dat conventionele benaderingen en STATICA onder bepaalde omstandigheden dezelfde oplossing opleveren, maar STATICA doet dat in N keer minder stappen, waarbij N het aantal spins in het model is, " zegt prof. Masato Motomura, die dit project leidde. Verder, het onderzoeksteam implementeerde een aanpak genaamd delta-driven spin-update. Omdat alleen spins die in de vorige iteratie zijn veranderd belangrijk zijn bij het berekenen van de volgende, er wordt een selectorcircuit gebruikt dat alleen de spins omvat die in elke iteratie zijn omgedraaid.

STATICA biedt een lager stroomverbruik, hogere verwerkingssnelheid, en betere nauwkeurigheid dan andere annealers. "STATICA heeft tot doel een revolutie teweeg te brengen in gloeiprocessors door optimalisatieproblemen op te lossen op basis van het wiskundige model van stochastische celautomaten. Onze eerste evaluaties hebben sterke resultaten opgeleverd, ", zegt prof. Motomura. Verdere verfijningen zullen STATICA een aantrekkelijke keuze maken voor combinatorische optimalisatie.