A Memristor-Based Processor Solves Mazes, Using the Power of Parallel Computing

By Clay Dillow Posted 03.03.2011 at 5:57 pm 6 Comments

Memristor Maze Yuriy V. Pershin & Massimiliano Di Ventra

Those mazes you used to complete with crayons when you were a kid? They’re not just child’s play. They’re actually analogous to a lot of mathematical models and problems that require time and, in most cases, a good deal of trial and error (read: dead ends) to solve. But using memristors--resistors with “memory”--a couple of researchers have created a memristor processor that solves mazes in a massively parallel way that has implications far beyond the puzzles page in an in-flight magazine.

Memristors are the fourth fundamental piece of electronic circuitry after capacitors, inductors, and resistors. They are basically resistors that remember what state of resistance they were in the last time a current passed through them. They were proposed more than three decades ago but were only first created in recent years by HP. And they are expected to drive revolutionary advances in future electronics for several reasons, not least of which is their ability to behave more like neurons than conventional electronic circuits.

Which brings us back to mazes. A maze can have varying degrees of complexity. It might have several solutions. A conventional processor would solve a maze the same way a person might--start at the starting point and weave itself through, noting dead ends and retrying until it gets all the way through to the end. Depending on the complexity of the maze, this could take some time.

To demonstrate how memristors could do better, Yuriy Pershin at the University of South Carolina and Massimiliano Di Ventra at UCSD constructed a sort of universal maze out of a grid of memristors which could be adopted to reflect any maze by disabling certain connections between memristors through which electricity cannot flow. Using this memristor array, once any maze design is imposed on their processor it can be solved for by simply applying voltage to the maze entrance and a ground to the finish.

That doesn’t sound so groundbreaking until you think it through. The memristor grid, unlike a conventional computer program, actually works in parallel, with all of the memristors working on solving the maze simultaneously. If there are multiple solutions, those are solved for simultaneously as well. Beyond that, the memristors will “remember” the solution(s) in their states for recall or use later.

That’s not such a big deal if you’re just solving a maze, but if you’re applying this power to robotics, graph theory, network optimization, or a slew of other computing models, it has the power to work much faster and more efficiently than computing complex problems in series.

Perhsin and Di Ventra’s processor amounts to the first application of memristor networks to massively parallel computing. Considering it such computing more closely mirrors the way the human brain works--or the way a brain-like computer might work--solving a maze with a memristor is about thrilling solving a simple puzzle can get.

[Technology Review]

Previous Article: A Long Exposure Captures Bioluminescence Below, a Swirling, Starry Night Above

Next Article: Video: 'Optical Tweezers' App Lets Users Manipulate Microscopic Particles With an iPad

6 Comments

Link to this comment

ford2go

03/04/11 at 3:47 am

I'm just not sure about this. The article (and its source) are a little vague.

However, it SOUNDS like they are wiring up the specific maze out of memistors. The 'solution' is found by applying voltage at the entrance and ground at the exit. Memistors in the maze path will conduct electricty and retain the evidence afterward.

No mention of how they 'read' the memistors. If I'm reading this right, it really doesn't sound like much.

Also, they have NOT built a device. This is a simulation.

Link to this comment

Volt

03/04/11 at 7:30 am

So in other words, rather than having the computer try to solve the maze, the computer creates its own maze out of memristors and then proceeds to run current through it, letting the maze solve itself.

This could work well for any number of processor heavy applications. Sure, it would quite literally suck up processor space, but not nearly as much as the alternative.

I'm assuming that either they run a program afterwards that deciphers the path of the electrons by studying the state of all the memristors.

Link to this comment

CodeZero

03/04/11 at 10:05 am

This follows the basic law of electric current, current will always flow in the lease resistant path. The problem I have with the article is that it states these paths will be saved for later use, that's not entirely true, the memristor will only hold the previous state, it will not hold/remember states before that. Once you run a new configuration, it loses the one before it. Much like E-Ink displays, current is run though the display to create text, with the current turned off, the text remains in place, once you place a new current over the display, if the configuration is different, IE a new page of text, the previously "remembered" configuration is lost and replaced. memristors do not store all previous configurations just the previous state.

Link to this comment

B.V.

03/04/11 at 12:22 pm

@ford2go,

I agree... it doesn't sound like much. They did a similar thing with a gas filled glass grid of London. You take 2 electrodes, and put one on the "starting point" and one on the "destination" on the map, the electricity naturally finds the shortest route between the two points... thereby displaying (by means of the now-glowing gas) the quickest route to take through the city to get from one point to the next.

Other than the "creativity" aspect of problem solving, I don't think it's very impressive since the practical applications are still quite a long ways off.

Link to this comment

bob_the_third

03/04/11 at 1:35 pm

Cool, but I'm wondering why they chose mazes as an example of a difficult problem. A maze can be thought of as a network, and Dijkstra's shortest path algorithm can easily be used to find a solution (well actually ALL solutions), and can do so worst case in (C + J log J) calculations, where C is the number of corridors, and J is the number of junctions between corridors. Even huge mazes could easily be solved by a modern computer in the blink of an eye (e.g. 1,000,000 calculation steps is no big deal, you have to get into the billions+ for it to become an issue, time-wise), and the program used to solve them would be much easier to reconfigure for a new maze.

Nonetheless it is neat, just maybe a bit overreaching in terms of the statement of impact.

Link to this comment

patron

03/04/11 at 4:58 pm

Neurons! We're even closer to Data than I thought. Maybe soon, someone will hit warp.
HALO Nerd ;D

Popular Tags

Science

All Tags All Photos All Videos

Science

+ More Photo Galleries

June 2013: American Energy Independence

Five amazing, clean technologies that will set us free, in this month's energy-focused issue. Also: how to build a better bomb detector, the robotic toys that are raising your children, a human catapult, the world's smallest arcade, and much more.