Memcomputer verwerkt data op vergelijkbare manier als menselijk brein

Onderzoekers hebben een prototype gebouwd van een 'memcomputer', een computer die werkt door bepaalde eigenschappen van het menselijk brein na te bootsen. De bevindingen kunnen helpen computers te ontwikkelen die gebruik maken van 'memprocessors'.

Memprocessors bestaan uit samenwerkende geheugencellen die gebruik maken van de mogelijkheid om zowel informatie op te slaan als te verwerken. De in de paper gepresenteerde machine is technologisch nog erg gelimiteerd en het is daarom ook een proof-of-concept, schrijven de onderzoekers in de inleiding. De machine werd gebouwd door gebruik te maken van standaard micro-elektronica zodat de theorie makkelijk naar de praktijk omgezet kon worden in een laboratoriumopstelling.

De auteurs van de studie publiceerden al eerder dit jaar een theoretische paper over een mogelijke memcomputer waarin ze aantoonden dat het voor een memcomputing-machine makkelijker moet zijn 'notoir moeilijke computationele problemen op te lossen, zogenaamde NP-volledige problemen'. Met het gebouwde prototype krijgen de auteurs het voor elkaar om een NP-volledige versie van het subset sum-probleem op te lossen in slechts één stap, met behulp van een aantal memprocessors die lineair meeschalen met de grootte van het probleem. De door de onderzoekers gebouwde machine heeft wel veel last van ruis, maar biedt wel mogelijkheden voor de toekomst.

Als een normale computer, of deterministische Turingmachine, een NP-volledig probleem moet oplossen, zoals het handelsreizigersprobleem, kunnen de benodigde processorkracht en het geheugen heel snel omhoog gaan. Bij het handelsreizigersprobleem ontstaat dit door het toenemen van het aantal punten waar deze langs moet. Daardoor kan het oplossen vrijwel onmogelijk worden. Theoretisch kan deze computer problemen wel in korte tijd oplossen. Andere computers die dergelijke problemen in de toekomst mogelijk op zouden kunnen lossen, zijn bijvoorbeeld kwantumcomputers.

Schema van de memcomputerarchitectuur die voor dit experiment gebruikt werd om het subset sum-probleem op te lossen Bron: AAAS

Reacties (23)

[Anoniem: 243272]

De vrijdagavond maakt het wat lastig om een gefundeerde bijdrage te leveren, maar hierbij toch een oppervlakkige poging van iemand met een redelijke computer science achtergrond.

De paper is hier te vinden:
http://arxiv.org/pdf/1411.4798v2.pdf

De claim in de introductie (apparaat heeft de rekenkracht van een non-deterministic turing machine) worden slechts ondersteund door 2 zelf-citaties. De paper staat vol met foto's. Op zichzelf is er niks mis met foto's, maar over het algemeen gebruik je de beperkte ruimte in een paper liever om een punt te maken. Voor zover ik kan zien is het paper niet ge-peer-reviewed: http://dblp.uni-trier.de/...urnals/corr/TraversaRBV14 . En de zinsnede "... reminiscent of the collective (entangled) state of many qubits in quantum computation" valt op de eerste pagina.

Al met al gaan er redelijk wat alarmbellen af als ik dit bekijk.

edit:

Nu op zaterdag alle linkjes in het artikel weer werken, is te zien dat het gepubliceerd is in "Science Advances
Vol 1, No. 6
03 July 2015"

Dit journal is vrij jong, dus de kwaliteit is lastig te beoordelen, maar er is in ieder geval een peer-review proces: http://advances.sciencemag.org/content/information-authors

[Reactie gewijzigd door Anoniem: 243272 op 25 juli 2024 02:49]

[blorf]

Wat ik me afvraag is waarom zoiets niet op een conventionele computer is te simuleren met elektronica-gerelateerde software maar wel mbv een wetenschappelijke opstelling. Het lijkt mij dat het dan gebaseerd moet zijn op iets wat de wetenschappers zelf eigenlijk ook niet begrijpen. Op het moment dat ze precies weten wat ze doen wordt simulatie weer een optie. Of bestaat er een elektronisch component waar software geen raad mee weet?

[Meijuh]

Ik weet niet of het aan de auteur van dit artikel op tweakers ligt of aan het paper. Maar dit is werkelijk het grootste blaatverhaal wat ik ooit gelezen heb. Misschien de film "the traveling salesman" te letterlijk genomen?

RIP tweakers.

Over de eerste twee paragrafen kan ik niets zeggen, maar elke zin uit de laatste twee paragrafen is regelrechte onzin en blaat.

De auteurs van de studie publiceerden al eerder dit jaar een theoretische paper over een mogelijke memcomputer waarin ze aantoonden dat het voor een memcomputing-machine makkelijker moet zijn 'notoir moeilijke computationele problemen op te lossen, zogenaamde NP-volledigheidsproblematiek'.
Nieuw woord: "NP-volledigheidsproblematiek".
Met het gebouwde prototype krijgen de auteurs het voor elkaar om een NP-volledig-versie van het subset sum-probleem
Niet "versie"maar subset sum is NP-compleet.
op te lossen in slechts één stap,
Lol, sure. Ik stop nu met mijn PhD onderzoek dan.
met behulp van een aantal memprocessors die lineair meeschalen met de grootte van het probleem.
Good luck doing that. En, pech voor de onderzoekers dat het probleem niet linear schaalt met het aantal "punten".
De door de onderzoekers gebouwde machine heeft wel veel last van ruis, maar biedt wel mogelijkheden voor de toekomst. Mooi, pseudo-science noemen we dat.

Als een normale computer, of deterministische Turingmachine,
Eerder een bounded Turingmachine. Hooguit kun je zeggen dat een computer even krachtig is als een turingmachine.
een NP-volledigheidsprobleem moet oplossen, zoals het handelsreizigersprobleem, gaat de benodigde processorkracht en geheugen kwadratisch omhoog als het aantal punten waar de 'handelsreiziger' langs moet, toeneemt.
Niet kwadratisch maar exponentieel in tijd.
Daardoor wordt het oplossen vrijwel onmogelijk. Deze computer kan deze problemen wel in korte tijd oplossen.
HAHAHAHAHA.
Andere computers die dergelijke problemen op zouden kunnen lossen, zijn bijvoorbeeld kwantumcomputers.
Over het algemeen niet waar geacht. Kwantumcomputers zijn daar waarschijnlijk lang niet krachtig genoeg voor.

Oh ja, te belachelijk voor woorden dat mensen NP-complete problemen willen oplossen met meer rekenkracht in plaats van slimme algoritmes. Doomed to failure.

De DOI is ook al niet meer bereikbaar?

Van reddit: http://www.popularmechani...um-computing-alternative/. Geeft een veel betere kijk op memcomputers. Waar niet wordt beweerd dat het triviaal het traveling salesman probleem kan worden opgelost oid.

Verder lezen op reddit: https://www.reddit.com/r/...turing_machine_which_can/, laat zien dat ze het waarschijnlijk nooit kunnen toepassen om enigsinds grote problemen. Dus zo promising is dit echt allemaal niet.

[Reactie gewijzigd door Meijuh op 25 juli 2024 02:49]

[jbdeiman]

Just some thoughts:
Met pure rekenkracht willen ze ook niet komen, maar een andere architectuur dan gebruikelijk in computers, waardoor er meer gelijktijdig gerekend kan worden. Een dergelijke structuur biedt ook meer mogelijkheden om tot een slim algoritme te komen, waarbij je optimaal gebruik maakt van de architectuur.
Wat onze hersenen heel goed kunnen is gelijktijdig verwerken, data opslaan en die ook meteen weer in een andere verwerking meenemen. Bij een computer is dat tot op heden vrij lineair en kan dat niet. Juist door een dergelijke verdeling te maken in de architectuur, kunnen de genoemde problemen beter opgepakt worden dan tot op heden.

Natuurlijk gaat het in eerste instantie vooral om rekenkracht, maar door die rekenkracht op een slimme manier te bundelen (Heel anders dan in "Supercomputers") probeert men een efficiëntieslag te behalen.

[MSalters]

NP-compleet is een theoretisch concept wat losstaat van elke architectuur. Bij het bewijzen dat een probleem NP-compleet is wordt niet méér aangetoond dan dat het een NP-compleet probleem is voor 1 specifieke architectuur, en die kan dan vaak slim gekozen worden voor het probleem.

[lesderid]

Blijkbaar kan het probleem 'opgelost' worden in polynomiale tijd, maar gebeurt het uitlezen van de oplossing in exponentiële tijd.

Volgens Scott Aaronson, een MIT professor die zich bezig houdt met computationele complexiteit, moeten we nog niet gaan juichen over dit resultaat. Een stukje uit zijn blogpost:

To solve Subset Sum in polynomial time, the basic idea of “memcomputing” is to generate waves at frequencies that encode the sums of all possible subsets of ai‘s, and then measure the resulting signal to see if there’s a frequency there that corresponds to k.
Alas, there’s a clear scalability problem that seems to me to completely kill this proposal, as a practical way of solving NP-complete problems. The problem is that the signal being measured is (in principle!) a sum of waves of exponentially many different frequencies. By measuring this wave and taking a Fourier transform, one will not be able to make out the individual frequencies until one has monitored the signal for an exponential amount of time.

Bron: https://www.reddit.com/r/..._first_functional/csrcfaw

[narotic]

Op arxiv staat ook een interessante inhoudelijke review van de paper. Het lijkt er sterk op dat de auteurs hun werk iets teveel hebben opgehemeld.

[noobz]

Ik snap niks van alle termen. Iemand een versimpelde uitleg voor normale mensen?

[narotic]

De auteur hier op tweakers begrijpt het volgens mij ook niet helemaal:

het handelsreizigersprobleem, gaat de benodigde processorkracht en geheugen kwadratisch omhoog als het aantal punten waar de 'handelsreiziger' langs moet, toeneemt

Het TSP probleem heeft natuurlijk exponentiele in plaats van kwadratische (tijds) complexiteit, anders zou het ook geen NP-volledig probleem zijn.

Maar goed, ik heb de paper snel nagekeken en heb een idee waar ze het over hebben (alhoewel je wat door de "marketing" heen moet lezen). Zoals je weet werkt een normale computer met een CPU voor berekeningen en apart geheugen voor data opslag. Geinspireerd door hoe de hersenen werken, stellen deze auteurs voor dit onderscheid tussen rekenkern en opslag weg te halen. Met andere woorden, ze combineren in kleine module zowel een rekenopdracht als een kleine hoeveelheid geheugen.

Kort door de bocht zijn het dus extreem simpele CPU's met een enkele functie en een paar registers, maar zonder centraal geheugen. Het voordeel is dat als je heel veel van deze kleine modules hebt je erg snel parallel kunt rekenen (dit is bijv. hoe hersenen werken). Daarnaast schaalt het totale (gedistribueerde) geheugen van het systeem met het aantal modules dat je gebruikt.

Voor bepaalde problemen werkt dit type architectuur dus blijkbaar erg goed, alhoewel ze de "verbetering" in complexiteit bereiken door het aantal modules te schalen met de probleemgrootte (imho ietwat valsspelen).

[Double-X-L]

Kort door de bocht zijn het dus extreem simpele CPU's met een enkele functie en een paar registers, maar zonder centraal geheugen. Het voordeel is dat als je heel veel van deze kleine modules hebt je erg snel parallel kunt rekenen (dit is bijv. hoe hersenen werken). Daarnaast schaalt het totale (gedistribueerde) geheugen van het systeem met het aantal modules dat je gebruikt.

Kunnen we het voor mij, en wellicht de mensen zonder deze specifieke studie, dan vereenvoudigen naar de GPU cores met caches zoals Nvidia en AMD?

Heb ook nog nooit zo'n high level tekst gezien als FP nieuws artikel. En die salesman problematiek vraagt ook om verduidelijking. Kan het allemaal extern gaan uitzoeken maar ik kom voor info graag hier

[narotic]

Kunnen we het voor mij, en wellicht de mensen zonder deze specifieke studie, dan vereenvoudigen naar de GPU cores met caches zoals Nvidia en AMD?

GPU's hebben inderdaad simpelere maar meer rekenkernen i.v.m. een CPU. Oppervlakkig gesproken zou je dus inderdaad kunnen zeggen dat het idee uit het artikel deze trend tot in het extreme doortrekt. Deze vergelijking gaat echter niet helemaal op, aangezien zowel CPU's als GPU's ontworpen zijn volgens (een afgeleide van) de Von Neumann architectuur, wat dat er nog steeds een duidelijk onderscheid is tussen rekeneenheden enderzijds en geheugen anderzijds.

De zogenaamde memristors daarentegen verenigen beide types eenheden op het allerlaagste niveau. Dit verschil is van belang omdat het een andere aanpak van programmeren vereist. Waar het in huidige GPU's en zelfs CPU's hooguit een performanceverlies betekent om het centrale geheugen te benaderen, is dit nagenoeg onmogelijk in dit soort extreem parallele architecturen op basis van memristors.

Het "handelsreizigersprobleem" (TSP: Travelling Salesman Problem) is simpelweg het probleem om de minimale afstand te berekenen om een gegeven aantal steden te bezoeken, als je de onderlinge afstand weet en slechts een keer langs elke stad mag komen. Dit probleem wordt erg snel heel moeilijk als het aantal steden wat je moet bezoeken toeneemt. De reden dat dit probleem "bekend" is is niet zozeer om alle vertegenwoordigers eerder thuis te laten komen, maar te meer omdat gebleken is dat veel andere problemen herschreven ("gereduceerd") kunnen worden naar het TSP. Als je dus een snel algoritme hebt om het TSP op te lossen, dan kun je deze dus inzetten voor een heel scala aan andere problemen.

Overigens kun je gerust het TSP vergeten. Ten eerste presenteert de paper een algoritme voor het subset-sum probleem en dus niet het TSP. Ten tweede lijkt het er inmiddels op dat de auteurs een paar cruciale details over het hoofd gezien hebben en dat de claims in het artikel dus gewoonweg niet waar zijn (zie meerdere reacties hieronder voor details).

[Reactie gewijzigd door narotic op 25 juli 2024 02:49]

[Anoniem: 435090]

Of het TSP een exponentieel probleem is, is nog onzeker. Nog sterker: Als je kun bewijzen dat dit zo is (of juist niet zo is) dan ligt er nog ergens een miljoen dollars voor je klaar. Het is namelijk één van de zeven millennium problemen.

En om nog maar iets toe te voegen aan de kritiek op dit bullshit artikel.
Er staat: "Andere computers die dergelijke problemen (=NP-volledigheidsproblemen) op zouden kunnen lossen, zijn bijvoorbeeld kwantumcomputers."

Dit geeft het idee dat kwantumcomputers NP-Complete problemen kunnen oplossen. Dit is echter nog vrij onzeker en de huidige opinie is juist dat kwantumcomputers dit niet kunnen.

Of zoals Scott Aaronson zegt: Contrary to popular belief, we don't know of a quantum algorithm to solve NP-complete problems in polynomial time. If such an algorithm existed, it would have to be dramatically different from Shor's algorithm.

[Reactie gewijzigd door Anoniem: 435090 op 25 juli 2024 02:49]

[anargeek]

Het brein kan informatie verwerken en opslaan tegelijkertijd. Een computer schrijft data naar het geheugen en verplaatst het daarna naar de processor. Omdat deze handelingen vertraging opleveren, zit er een limiet aan data-verwerking.
Vanwege deze extra handelingen bestaan er voor computers "niet-oplosbare problemen". Een memcomputer zou hetzelfde werken als het brein en zou dus deze problemen wel kunnen oplossen

Maar correct me if I'm wrong, ik vind het ook ingewikkeld

Hier vind je meer informatie, is duidelijk geschreven
edit: verduidelijking en link

[Reactie gewijzigd door anargeek op 25 juli 2024 02:49]

[neoeldex]

Nee, de problemen niet bij de praktische limitaties, maar bij de wiskundige limitaties.
Problemen in NP-Compleet en NP-Hard, hebben heel veel mogelijke oplossingen, en kunnen niet zomaar efficienter worden opgelost. Mensen zijn zelf ook niet beter in NP-Complete problemen oplossen. Dan zouden we bijvoorbeeld naar een RubicsCube kunnen kijken, en snel kunnen zien welke stappen we moeten zetten om hem onder 20 zetten op te lossen.

Helaas zijn er zoveel verschillende mogelijkheden, en niet per-se een structuur in het probleem zit, waardoor er veel stappen gezet moeten worden voordat er een oplossing gevonden wordt.

Kwantumcomputers en Memcomputers zullen vast algoritmes krijgen die efficient bepaalde zaken kunnen uitrekenen. Maar eigenlijk moet volgens mij de hardware schalen met de grootte van het probleem.
Dat hoefde niet bij gewone computers, daarmee konden we gewoon langer wachten tot hetzelfde probleem was opgelost. Met kwantumcomputers zouden de processoren steeds meer bits moeten verwerken voor een grotere input zet.

Het is dan ook niet gezegd dat je op die manier makkelijk grote getallen efficient kan factoriseren, omdat je daar computers voor nodig hebt die duizenden bits groot zijn.

[Anoniem: 628318]

Daarom ook dat er wiki links bijstaan.. en leek zou een betere benaming zijn dan normale mensen

[noobz]

Was dat in de eerste versie al?
Zou kunnen hoor.

[Septimamus]

Erg indrukwekkend. Overigens snap ik niks van die afbeelding. Ik hoop dat ik niet de enige ben
Is deze techniek dan niet nog sneller dan de techniek van een kwantum computer?

[MAX3400]

Het lijkt me onmogelijk dat ie sneller is dan een kwantum computer. Bovenstaande opstelling is gemaakt met bestaande electronica; een kwamtum computer is "nieuwe" technologie om de beperkingen van bestaande electronica te vervangen.

[smikkol]

Echter is dit 'slechts' een proof-of-concept. Hoe het(brain-like processors) in de toekomst zal worden toegepast kan je kijk erop compleet veranderen.

He klinkt in iedergeval reuze interessant!

[Shammah]

Op het eerste gezicht lijkt dit mij een analoge / hardware versie van neurale netwerken als het plaatje zo bekijk? Wat is hier precies nieuwswaardig aan, zonder de hele paper te hebben gelezen?

[Reactie gewijzigd door Shammah op 25 juli 2024 02:49]

[twmichel]

NB: de uitleg is verkeerd om: makkelijke problemen schalen (bijvoorbeeld) kwadratisch, NP-complete problemen schalen meer dan polynomisch. Het handelsreizigersprobleem schaalt met (2^n)*(n^2).