A Memristor-Based Processor Solves Mazes, Using the Power of Parallel Computing
Those mazes you used to complete with crayons when you were a kid? They’re not just child’s play. They’re actually...
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.