(Phys.org)—Forskare har designat och implementerat en algoritm som löser datorproblem med hjälp av en strategi inspirerad av hur en amöba förgrenar sig för att skaffa resurser. Den nya algoritmen, kallas AmoebaSAT, kan lösa satisfiability-problemet (SAT) – ett svårt optimeringsproblem med många praktiska tillämpningar – genom att använda storleksordningar färre steg än det antal steg som krävs av en av de snabbaste konventionella algoritmerna.

Forskarna förutspår att det amöba-inspirerade datorsystemet kan erbjuda flera fördelar, som hög effektivitet, miniatyrisering, och låg energiförbrukning, som kan leda till ett nytt datorparadigm för höghastighetsproblemlösning i nanoskala.

Leds av Masashi Aono, Associate Principal Investigator vid Earth-Life Science Institute, Tokyo Institute of Technology, och på PRESTO, Japan Science and Technology Agency, forskarna har publicerat en artikel om det amöba-inspirerade systemet i ett färskt nummer av Nanoteknik .

"Vi visade ett sätt att utnyttja den enorma beräkningskraften hos naturfenomen när det gäller komplexitet och energi, " berättade Aono Phys.org .

Motivationen för denna forskning kommer till stor del från den pågående trenden med elektronisk miniatyrisering. Som forskarna förklarar, transistorer har blivit så små att de närmar sig den skala där termiska fluktuationer kan störa deras funktion. Dessa fluktuationer måste åtgärdas, men istället för att försöka minimera deras inverkan, färsk forskning har visat att ett bättre alternativ kan vara att samexistera med dem. Många biologiska system, såsom de molekylära motorerna som är involverade i muskelkontraktion, har gjort detta framgångsrikt i miljontals år.

I deras studie, forskarna designade ett datorsystem i nanoskala bestående av en elektrisk Brownsk spärrhake, som använder samma grundläggande mekanism som en biologisk molekylär motor, att generera ström från fluktuerande elektroner. I en elektrisk Brownsk spärrhake, termisk energi i en nanotråd gör att elektroner slumpmässigt rör sig i en riktning (t.ex. vänster men inte höger) eller stanna på samma plats. Att upprepa denna process flera gånger genererar ett riktat elektronflöde, resulterar i en elektrisk ström med stokastiska (slumpmässiga) fluktuationer. Som tidigare forskning har visat, så länge ingen energi överförs utanför systemet, processen bryter inte mot termodynamikens andra lag.

För att implementera deras amöba-inspirerade datorsystem, forskarna designade ett nätverk av elektriska Brownska spärrar med många "grenar" eller ledningar. Grenarna motsvarar en amöbas pseudopoder, som kan sträcka sig över stora ytor för att maximera näringsupptaget. På ett liknande sätt, grenarna av spärrnätverket kan leverera ström (som representerar det binära värdet "1") eller ingen ström (representerar "0") på ett stokastiskt sätt. Övergripande, båda systemen använder slumpmässig rörelse, i kombination med dynamisk återkopplingskontroll, att utföra datoruppgifter.

För att utvärdera AmoebaSAT-systemets beräkningsförmåga, forskarna använde det för att lösa ett svårt kombinatoriskt optimeringsproblem som kallas SAT-problemet, vilket i grunden innebär att bestämma om en given formel som består av många logiska variabler och begränsningar är "tillfredsställbar". SAT-problemet och dess härledda problem har ett brett utbud av tillämpningar inom områden inklusive robotik, modellering, elektronisk handel, och andra.

"För att söka efter en lösning på SAT-problemet, varje enhet i systemet måste bete sig på ett stokastiskt sätt och göra ett "fel" för att utforska ett bredare tillståndsrum; felet indikerar att resursen inte tillförs även när den spärrande styrsignalen inte appliceras, " förklarade Aono. "I detta avseende, den elektriska Brownska spärrhaken är en av de bästa enheterna för att lösa problemen eftersom den implementerar stokastiska operationer med fel, som utsätts för slumpmässigt termiskt brus. Vidare, denna enhet är fördelaktig eftersom den förbrukar låga nivåer av energi, som är jämförbara med termisk energi; det underlättar storskalig integration för att lösa stora problem."

Tester visade att AmoebaSAT-systemet hade 100 % framgång i att hitta en lösning på olika SAT-problem med 50 variabler, lösa dessa problem med ett genomsnitt på cirka 3, 000 steg. En modifierad version av algoritmen, som mer effektivt kan hantera felinducerande slumpmässigt brus, presterade ännu bättre, i genomsnitt färre än 1800 steg. För jämförelse, en av de snabbaste kända lokala sökalgoritmerna, WalkSAT, krävde storleksordningar fler steg för att lösa samma problem. Dessutom, AmoebaSAT överträffar WalkSAT mer markant när antalet variabler ökar.

Forskarna föreslår att AmoebaSAT:s överlägsna prestanda kommer från dess "samtidiga sökning"-funktion, hänvisar till dess förmåga att uppdatera flera variabler samtidigt. I kontrast, WalkSAT-algoritmer och andra metoder som körs på konventionella digitala datorer kan endast uppdatera en variabel vid varje steg. Denna "seriella" funktion kan spåras tillbaka till Turing-maskinen, som definierade det konventionella begreppet beräkning. I framtiden, forskarna planerar att ytterligare utforska ursprunget till den nya naturinspirerade algoritmens prestandafördelar.

En annan fördel med den nya algoritmen som gör den särskilt lovande för framtida utveckling är dess potentiella skalbarhet. Många naturliga datorer, såsom hjärninspirerade neurala nätverk, kräver ett stort antal sammankopplade ledningar som växer snabbt när problemets komplexitet växer, begränsa skalbarheten för dessa nätverk. Den amöba-inspirerade arkitekturen undviker detta problem eftersom antalet sammankopplade enheter bara växer linjärt när komplexiteten ökar.

Med alla dessa fördelar, forskarna hoppas att amöba-inspirerade datorer kommer att erbjuda mer än bara en datornyhet, men ett praktiskt sätt att implementera framtida datorteknik i nanoskala.

"För närvarande, vi har precis designat systemet och verifierat att det fungerar ganska bra, även om de korrekta funktionerna för de elektriska Brownian-spärrarna redan har bekräftats, " sa Aono. "Inom en snar framtid, vi kommer att tillverka själva AmoebaSAT-systemet implementerat med den elektriska Brownian-spärren och visa att det framgångsrikt uppnår sina utmärkta prestanda när det gäller effektivitet, miniatyrisering, och minskad energiförbrukning."

© 2015 Phys.org