Behind the scenes @ Labs
cancel
Showing results for 
Search instead for 
Did you mean: 

Can chaos improve computing? Labs researchers publish the answer in the journal Nature

Curt_Hopkins

Stan Williams, John Paul Strachan, and the paper's lead author Suhas KumaStan Williams, John Paul Strachan, and the paper's lead author Suhas Kuma

By Curt Hopkins, Managing Editor, Hewlett Packard Labs

When we think of chaos, it is almost always as a destructive force. The essence of chaos theory is sometimes encapsulated in the question “If a butterfly flaps its wings in China, can that lead to a hurricane in the Atlantic?” But as three researchers at Labs have discovered, it is a force that can improve computing substantially by accelerating a search to solve problems traditional digital computers find difficult to manage.

Suhas Kumar, post-doctoral researcher in the Systems Architecture Lab, along with research scientist John Paul Strachan and HPE Senior Fellow R. Stanley Williams, have published their findings in the prestigious journal Nature.

Chaotic dynamics in nanoscale NbO2 Mott memristors for analogue computing” outlines the creation of what Kumar, the article’s lead author, calls an “Analog Computation Engine.”

Strachan, with slightly less concision, described the research, funded in part by the Intelligence Advanced Research Projects Activity, as a “combo of a novel device behavior study with an example ‘circuit’ (in the form of a modified Hopfield network, which allows you to solve optimization problems through physics) that can add functionality. It uses a Dot Product Engine (DPE) – HPE's Memristor-based experimental platform for computational acceleration – to perform the needed analog vector matrix multiplication, combined with a novel device (the chaotic-signal generating NbO2 memristor) to play a ‘neuron-like’ role of activation, with a mix of chaos thrown in which, as we show, has benefits.”

Chaotic device as a supercharger

It’s important in this context to define chaos. Chaos, Kumar explains, is “behavior in between the perfectly regular and the completely random.” As an example, he cites the pendulum vs. the double-pendulum. The pendulum’s back and forth motions are regular, as described by the harmonic oscillator equation, and can be predicted accurately far into the future. The actions of a double-pendulum, however, can only be tracked approximately. There is some regularity, but not enough to map out its movement exactly ahead of time.

At the nanometer scale, atoms vibrate and jostle each other in a very random way. The nanoscale memristor used for these studies amplifies the minute fluctuations in temperature experienced by its atoms and creates a chaotic electronic signal that is irregular in a manner similar to the double-pendulum. A supercharged version of the Dot Product Engine can be created by connecting many of these chaotic devices into a DPE circuit, which thus becomes the Analog Computation Engine (ACE).

The ACE is specially designed to tackle a class of problems called non-deterministic polynomial (NP), and specifically, “constrained optimization problems,” a category that traditional digital computing struggles with. Some well known examples of NP problems include the art gallery problem and the traveling salesman problem.

The researchers simulated the ACE with the example of the traveling salesman problem, which attempts to calculate the shortest route among a set of destinations the salesman needs to visit on a single trip.

traveling-salesman2.gif

Traditional computers approach the problem by first calculating every possible trip variant and then choosing the shortest. Even a small number of destinations in such a problem creates an enormous compute demand. Given that the human mind does a better job of addressing this class of problems, Kumar, Strachan, and Williams tried to figure out what type of approach would address humans’ unique approximate way of dealing with issues like this. The Analog Computation Engine was the outcome of this examination.

Using the brain for inspiration

The memristor, a fourth class of electrical circuit element, theorized by Prof. Leon Chua (and made real at Hewlett Packard Labs) can be built very small and contains a very high degree of non-linearity, which helps the device turn noise into chaos. Chua has shown that the ion channels that control electrical signals in neurons are types of memristors, and that the neurons themselves are “poised on the edge of chaos.” Although the actual processes active in the brain are still not understood, it is known that chaos can lead to complexity and emergent behavior in electronic systems. There has been a lot of speculation that there should be a connection between chaos and computation. This was the motivation behind the research.

The approach used in the paper was to incorporate chaotic electrical signals into a self-guiding “Hopfield network,” which, as Strachan describes it, “encodes any problem into an energy-like function and lets the system evolve toward energy minima, corresponding to optimal solutions. The challenge right away was getting stuck in local, non-global minima. Our chaotic device helps us avoid those traps.”

Because the ACE is based on previously-developed components, because those components can be integrated onto complementary metal-oxide semiconductor (CMOS) chips, and because the energy demands are minimal, Kumar, Strachan, and Williams see the ACE as the basis for a potential future accelerator chip that could be installed on the network fabric of any size computer and could be called to find solutions to classes of NP problems as needed by programs running on more conventional processors, thus saving huge amounts of time and energy for a given computation. In particular, HPE’s Memory-Driven Computing architecture and the Gen-Z fabric are ideal for utilizing accelerators such as the ACE and other special-purpose engines to improve computing speed and efficiency, because they are specifically designed to support heterogeneous computing environments.

Designing with superchargers

“What is still under development is a full-out chip design,” said Strachan. “But it is not a big leap to imagine what it needs to do. Any optimization problem is an encoding of the constraints – cities to visit, resource priorities, and so on. For Hopfield networks, this is encoded in an “energy” function and we can program this directly into the memristor conductances!”

The design Strachan envisions would need to furnish a method to write in those values and then decide when it had searched long enough that it could stop and accept the answer, based on threshold values defined by the user – do you want a very accurate answer, or do you want a fast answer with acceptable accuracy? It would also need to break big problems apart across several engines if necessary.

“This is still a research problem, and not an easy one,” he said. “But the challenge is not whether it can be done, but how efficiently it can be done, so that the design itself doesn’t become the biggest bottleneck to performance.”

The genius in this development is in simply asking the question, Is the missing ingredient to making a functional Analog Computation Engine the chaos that surrounds us?

The answer, simply put, is yes.

About the Author

Curt_Hopkins

Managing Editor, Hewlett Packard Labs

Comments
Rebecca Lewington

Nice work! Making computers faster without relying on Moore's Law is the future.

Events
Jan 30-31, 2018
Online
Expert Days - 2018
Join us online to talk directly with our HPE experts during online Expert Days. Find information here about past, current, and upcoming Expert Days. P...
Read more
28-30 November
Madrid, Spain
Discover 2017 Madrid
Join us for Hewlett Packard Enterprise Discover 2017 Madrid, taking place 28-30 November at the Feria de Madrid Convention Center
Read more
View all