Researchers build first working memcomputer prototype.
38 replies, posted
[QUOTE][QUOTE][IMG]http://d3a5ak6v9sb99l.cloudfront.net/content/advances/1/6/e1500031/F1.large.jpg?width=800&height=600&carousel=1[/IMG][/QUOTE]
A combined team of researchers from the University of California and Politecnico di Torino in Italy has built, for the first time, a working memory-crunching computer (memcomputer) prototype.
It is capable, the team reports in their paper published in the journal Science Advances, of solving the NP-complete version of the subset sum problem.
At its most basic level, a memcomputer is a computer that solves problems by crunching numbers and storing results simultaneously, rather than as completely separate processes, as is done with all modern computing machines.
To create their prototype, the researchers had to come up with a completely new computer design, one based on what the team calls memprocessors—their prototype has six of them.
To prove that it can do actual work, the prototype is able to solve the NP-complete version of the subset sum problem—where given a set of numbers, is there a subset with at least one number, whose sum is zero?
[QUOTE]Abstract
Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, [B]they can solve NP-complete problems in polynomial time[/B] and, using the appropriate architecture, with resources that [B]only grow polynomially with the input size[/B]. The reason for this computational power stems from properties inspired by the brain and shared by any universal memcomputing machine, in particular intrinsic parallelism and information overhead, namely, the capability of compressing information in the collective state of the memprocessor network. We show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem. We have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting. Although the particular machine presented here is eventually limited by noise—and will thus require error-correcting codes to scale to an arbitrary number of memprocessors—it represents the first proof of concept of a machine capable of working with the collective state of interacting memory cells, unlike the present-day single-state machines built using the von Neumann architecture.
Journal:
[URL]http://advances.sciencemag.org/content/1/6/e1500031[/URL][/QUOTE]
Source:
[URL]http://phys.org/news/2015-07-memcomputer-prototype.html[/URL][/QUOTE]
This is beyond amazing.
could this open the way towards synthetic brains? this seems really close to how our minds work.
Hooray for an article which posts a [U]functional[/U] schematic and signal flowchart diagram!
But in all seriousness, utilizing signal interference, quadrature encoding? (judging by the cos/sin pair), etc to perform polynomial calculations is fantastic.
[QUOTE=LoneWolf_Recon;48137516]Hooray for an article which posts a [U]functional[/U] schematic and signal flowchart diagram!
But in all seriousness, utilizing signal interference, quadrature encoding? (judging by the cos/sin pair), etc to perform polynomial calculations is fantastic.[/QUOTE]
Hey, guys, look, look at the nerd, guys! Neeerrdd!
Well duh that's the definition of NP. Non-deterministic polynomial time. So if you have a non-deterministic machine the solution becomes polynomial...
Will we need to have completely different programming methods for memristor computers, or would they be able to integrate with current civilian hardware?
[QUOTE=ironman17;48137558]Will we need to have completely different programming methods for memristor computers, or would they be able to integrate with current civilian hardware?[/QUOTE]
I would assume that you'd have to have taken a good deal worth of Signal/Systems, etc classes to work on this. Control loop theory would probably also go in to understanding this.
Also memristors are a type of electrical component (Charge to Flux relation). :v:
[QUOTE=ironman17;48137558]Will we need to have completely different programming methods for memristor computers, or would they be able to integrate with current civilian hardware?[/QUOTE]
probably extremely different
Did they actually solve the P versus NP problem? I don't have a thorough understanding of this.
Writing a paper on recent developments in the mechanical replication of cognitive functions; seems recent enough for me!
Do I hear the future beckoning?
[QUOTE=Zero Vector;48137611]Did they actually solve the P versus NP problem? I don't have a thorough understanding of this.[/QUOTE]
No, they didn't. As stated above this machine fits with the definition of NP. Aka basically they made new hardware to cater to NP problems.
There's a lingering question if some problems in NP are actually P, meaning they could be solved in polynomial time on a "normal" computer.
Basically P are the problems solvable in polynomial time on a deterministic "turning machine." NP are the ones only (thought to be) solvable on a non-deterministic turing machine. "Normal" computers are deterministic, this new machine is non-deterministic.
[QUOTE=AJ10017;48137602]probably extremely different[/QUOTE]
So people probably won't be making game programs for memristor computers for a LONG time, I imagine.
me right now
[IMG]http://canadianonlinegamers.com/wp-content/uploads/2014/01/caveman.jpg[/IMG]
For a second there, I read it as "memecomputer". My life would have been complete.
Also, how big of a power leap is it to go from current computing to memcomputing? How fast could these things go in comparison to modern machines?
[QUOTE=ironman17;48137722]Also, how big of a power leap is it to go from current computing to memcomputing? How fast could these things go in comparison to modern machines?[/QUOTE]
Depends on the problem. Not all will get a performance boost.
Basically this is like a linear equation, x, vs an exponential equation, 2^x.
compare these for input size (say 1 second per input) and you get:
- 1: 1 second vs 2 seconds
- 10: 10 seconds vs 1024 seconds
- 100: 100 seconds vs 1.5x10^25 [B]days[/B] (4x10^22 years, 40 sextillion years)
You can throw constants in or raise x to any power you like but you can see the growth of the function is what is important.
What does this mean???
[QUOTE=thrawn2787;48137666]No, they didn't. As stated above this machine fits with the definition of NP. Aka basically they made new hardware to cater to NP problems.
There's a lingering question if some problems in NP are actually P, meaning they could be solved in polynomial time on a "normal" computer.
Basically P are the problems solvable in polynomial time on a deterministic "turning machine." NP are the ones only (thought to be) solvable on a non-deterministic turing machine. "Normal" computers are deterministic, this new machine is non-deterministic.[/QUOTE]
I find it funny when reading what you wrote only to look at your avatar as though people are idiots for not understanding NP.
[img]http://facepunch.com/image.php?u=94383&dateline=1411089673[/img]
You wrote better then how I could explain it.
[QUOTE=thrawn2787;48137830]Depends on the problem. Not all will get a performance boost.
Basically this is like a linear equation, x, vs an exponential equation, 2^x.
compare these for input size (say 1 second per input) and you get:
- 1: 1 second vs 2 seconds
- 10: 10 seconds vs 1024 seconds
- 100: 100 seconds vs 1.5x10^25 [B]days[/B] (4x10^22 years, 40 sextillion years)
You can throw constants in or raise x to any power you like but you can see the growth of the function is what is important.[/QUOTE]
Soooo the smaller processes don't get as much of a speed boost, but the larger ones get a much larger boost? I'll be honest, I don't fully understand how it works even with this explanation.
Can someone with an understanding/background in this sort of stuff please explain in laymams terms what this really is all about?
[QUOTE=Zero Vector;48137611]Did they actually solve the P versus NP problem? I don't have a thorough understanding of this.[/QUOTE]
Nooooope.
Just that NP machines now exist in a functioning state.
[url]http://advances.sciencemag.org/content/advances/suppl/2015/06/30/1.6.e1500031.DC1/1500031_SM.pdf[/url]
Looking at the supplementary material makes me understand it a lot more.
The schematic makes me feel like I can make one at home.
I somehow doubt it actually solves NP-complete problems in actual polynomial time.
Edit: There seems to be a bunch of weird things going on.
The claim that their approach doesn't require exponential resources is false. It requires exponential energy, as they admit in the paper.
Wait, wait, non-Turing?
Fuck, I've [I]just[/I] finished learning about how all processes can be displayed as a Turing Machine.
[QUOTE=ThePuska;48140013]The claim that their approach doesn't require exponential resources is false. It requires exponential energy, as they admit in the paper.[/QUOTE]
And apparently it takes exponential time to read the answer.
[QUOTE=green bandit;48137718]For a second there, I read it as "memecomputer". My life would have been complete.[/QUOTE]
Imagine how fast it would generate new memes.
So this is just really fucking fast analog computer? (realtime, no clock signal to drive circuit)
[QUOTE=Fourier;48140621]So this is just really fucking fast analog computer? (realtime, no clock signal to drive circuit)[/QUOTE]
It isn't fast, it's concurrent. And i don't think it's analog either.
Sorry, you need to Log In to post a reply to this thread.