Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

Memristor Processor Solves Mazes

Physicists have designed a memristor processor that uses a massively parallel approach to solve mazes.

  • March 3, 2011

Memristors are the fourth fundamental building block of electronic circuits, after resistors, capacitors and inductors. They were famously predicted in the early 1970s but only discovered 30 years later at HP Labs in Palo Alto, California.

Memristors are resistors that “remember” the state they were in, which changes according to the current passing through them. They are expected to revolutionise the design and capabilities of electronic circuits and may even make possible brain-like architectures in silicon, since neurons behave like memristors.

Today, we see one of the first revolutionary circuits thanks to Yuriy Pershin at the University of South Carolina and Massimiliano Di Ventra at the University of California, San Diego, two pioneers in this field. Their design is a memristor processor that solves mazes and it is remarkably simple.

Mazes are a class of graphical puzzles in which, given an entrance point, one has to find the exit via an intricate succession of paths, with the majority leading to a dead end, and only one, or few, correctly “solving” the puzzle.

Pershin and Di Ventra begin by creating a kind of a universal maze in the form of a grid of memristors, in other words an array in which each node is connected to another by a memristor and a switch. This can be made to represent any regular maze by switching off certain connections within the array.

Solving this maze is then simple. Simply connect a voltage across the start and finish of the maze and wait. “The current flows only along those memristors that connect the entrance and exit points,” say Pershin and Di Ventra. This changes the state of those memristors allowing them to be easily identified. The chain of these memristors is then the solution.

That’s potentially much quicker than other maze solving strategies which effectively work in series. “The maze is solved in a massively parallel way, since all memristors in the network participate simultaneously in the calculation,” they say.

They’ve tested the idea with a memristor simulator, a computer program that reproduces the behaviour of real memristors, and say it works well. And implementing the device in silicon will become easier as more development work is done in this area.

Of course, it’s not just the memristors that are doing the calculating here. Their network structure and layout is crucial too. When a maze is created, the answer is already embedded in its structure, well before any computation begins. The only question is how easily it can be extracted. This new approach, in which the entire structure of maze takes part, is clearly powerful.

That makes Pershin and Di Ventra’s work part of a growing body of interest in the role that form and structure play in processing information. If you’re in any doubt the significance of this so-called morphological computing, think about how the human body walks or jumps.

There is increasing evidence that the brain has much less involvement with this kind of movement than anybody imagined. Instead, the shape, form and material properties of bones, ligaments and muscles largely control the detail of what happens. In effect, the brain outsources control to the morphology of the system.

This kind of memristive processing falls into a similar category. Expect to hear more about it.

Ref: arxiv.org/abs/1103.0021: Solving Mazes With Memristors: A Massively-Parallel Approach

You can now follow The Physics arXiv Blog on Twitter

Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.
Subscribe today

Uh oh–you've read all five of your free articles for this month.

Insider Premium

$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.

  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Join in and ask questions as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

You've read of free articles this month.