Heb je ooit een probleem gehad waarbij je een optimale oplossing moest vinden uit vele mogelijke opties, zoals het vinden van de snelste route naar een bepaalde plaats, rekening houdend met zowel afstand als verkeer?

Als dat het geval is, is het probleem waarmee u te maken had, wat formeel bekend staat als een 'combinatorisch optimalisatieprobleem'. Hoewel wiskundig geformuleerd, komen deze problemen veel voor in de echte wereld en komen ze voor op verschillende gebieden, waaronder logistiek, netwerkroutering, machine learning en materiaalwetenschap.

Grootschalige combinatorische optimalisatieproblemen zijn echter zeer rekenintensief om op te lossen met behulp van standaardcomputers, waardoor onderzoekers zich tot andere benaderingen wenden. Een dergelijke benadering is gebaseerd op het "Ising-model", dat wiskundig de magnetische oriëntatie van atomen of "spins" in een ferromagnetisch materiaal weergeeft.

Bij hoge temperaturen zijn deze atomaire spins willekeurig georiënteerd. Maar naarmate de temperatuur daalt, staan ​​de spins in een rij om de minimale energietoestand te bereiken waarbij de oriëntatie van elke spin afhangt van zijn buren. Het blijkt dat dit proces, bekend als "annealing", kan worden gebruikt om combinatorische optimalisatieproblemen te modelleren, zodat de uiteindelijke toestand van de spins de optimale oplossing oplevert.

Onderzoekers hebben geprobeerd gloeiprocessors te maken die het gedrag van spins nabootsen met behulp van kwantumapparaten, en hebben geprobeerd halfgeleiderapparaten te ontwikkelen met behulp van grootschalige integratie (LSI) -technologie die hetzelfde wil doen. Met name de onderzoeksgroep van professor Takayuki Kawahara aan de Tokyo University of Science (TUS) in Japan heeft belangrijke doorbraken bereikt op dit specifieke gebied.

In 2020 presenteerden prof. Kawahara en zijn collega's op de internationale conferentie van 2020, IEEE SAMI 2020, een van de eerste volledig gekoppelde (dat wil zeggen, rekening houdend met alle mogelijke spin-spin-interacties in plaats van interacties met alleen naburige spins) LSI-gloeiprocessors, bestaande uit 512 volledig verbonden spins.

Hun werk verscheen in het tijdschrift IEEE Transactions on Circuits and Systems I:Regular Papers . Deze systemen zijn notoir moeilijk te implementeren en op te schalen vanwege het enorme aantal verbindingen tussen spins dat moet worden overwogen. Hoewel het parallel gebruiken van meerdere volledig aangesloten chips een mogelijke oplossing voor het schaalbaarheidsprobleem was, maakte dit het vereiste aantal onderlinge verbindingen (draden) tussen chips onbetaalbaar.

In een recente studie gepubliceerd in Microprocessors and Microsystems , toonden prof. Kawahara en zijn collega een slimme oplossing voor dit probleem. Ze ontwikkelden een nieuwe methode waarbij de berekening van de energietoestand van het systeem eerst wordt verdeeld over meerdere volledig gekoppelde chips, waardoor een 'arraycalculator' ontstaat.

Een tweede type chip, 'controlechip' genaamd, verzamelt vervolgens de resultaten van de rest van de chips en berekent de totale energie die wordt gebruikt om de waarden van de gesimuleerde spins bij te werken. "Het voordeel van onze aanpak is dat de hoeveelheid gegevens die tussen de chips wordt verzonden extreem klein is", legt prof. Kawahara uit. "Hoewel het principe eenvoudig is, stelt deze methode ons in staat om een ​​schaalbaar, volledig verbonden LSI-systeem te realiseren voor het oplossen van combinatorische optimalisatieproblemen door middel van gesimuleerd uitgloeien."

De onderzoekers hebben hun aanpak met succes geïmplementeerd met behulp van commerciële FPGA-chips, die veelgebruikte programmeerbare halfgeleiderapparaten zijn. Ze bouwden een volledig verbonden gloeisysteem met 384 spins en gebruikten het om verschillende optimalisatieproblemen op te lossen, waaronder een 92-node grafiekkleuringsprobleem en een 384-node maximum cut-probleem.

Het belangrijkste is dat deze proof-of-concept-experimenten hebben aangetoond dat de voorgestelde methode echte prestatievoordelen oplevert. Vergeleken met een standaard moderne CPU die hetzelfde gloeisysteem modelleert, was de FPGA-implementatie 584 keer sneller en 46 keer energiezuiniger bij het oplossen van het maximale snijprobleem.

Nu, met deze succesvolle demonstratie van het werkingsprincipe van hun methode in FPGA, zijn de onderzoekers van plan om het naar een hoger niveau te tillen. "We willen een op maat ontworpen LSI-chip produceren om de capaciteit te vergroten en de prestaties en energie-efficiëntie van onze methode aanzienlijk te verbeteren", zegt prof. Kawahara. "Dit zal ons in staat stellen de vereiste prestaties te realiseren op het gebied van materiaalontwikkeling en medicijnontdekking, waarbij zeer complexe optimalisatieproblemen betrokken zijn."

Tot slot merkt prof. Kawahara op dat hij de implementatie van hun resultaten wil bevorderen om echte problemen in de samenleving op te lossen. Zijn groep hoopt gezamenlijk onderzoek te doen met bedrijven en hun benadering naar de kern van halfgeleiderontwerptechnologie te brengen, waardoor deuren worden geopend voor de heropleving van halfgeleiders in Japan. + Verder verkennen

Een nieuwe processor die notoir complexe wiskundige problemen oplost