A memristor-based Hopfield neural architecture to solve combinatorial optimization problems
Over the past few years, many researchers have tried to develop techniques and technologies that can solve combinatorial optimization problems, which entail identifying an optimal item or solution within a set number of possibilities. Past studies have tackled these problems using annealing-inspired computing accelerators based on a variety of technological tools, including quantum, optical and electronic devices.
Most approaches developed so far, however, have not achieved the processing speeds and energy-efficiencies necessary to solve combinatorial optimization problems on a large scale. This prevents them from being implemented in industrial settings and in other real-world environments.
Researchers at Hewlett Packard Labs (HPL), part of Hewlett Packard Enterprise, have recently developed a new memristor-based annealing system that can solve combinatorial optimization problems rapidly and efficiently. This system, presented in a paper published in Nature Electronics, uses an energy-efficient neuromorphic architecture based on a Hopfield neural network, a type of recurrent neural network first disseminated by John J. Hopfield in 1982 that can be used to implement an auto-associative memory.
"In 2008, our group at HPL found the memristor (i.e., memory resistor), a two-terminal device that could store information in its resistance state even when the power was turned off," Suhas Kumar, one of the researchers who carried out the study, told TechXplore. "In 2017, we hypothesized that noisy memristors could be used to construct a Hopfield network, which could be used to solve NP-hard optimization problems instead of their original purpose of associative memory."
For several years, difficulties in dislodging Hopfield network-based architectures from less favorable solutions have prevented these architectures from becoming mainstream. Kumar and his colleagues were able to overcome this limitation and build a memristor-based chip that exemplifies a Hopfield network. In contrast with other systems developed in the past, their chip can solve any combinatorial optimization problem by harnessing its own noise.
"In parallel to the work that Suhas mentioned, there is also a research effort at HPL to see whether silicon photonics can be used for computation instead of communication, which is the area I have been working on since I joined the company," Thomas Van Vaerenbergh, another researcher involved in the study, told TechXplore. "At some point, we were designing a light-based accelerator called an optical Ising machine that was perfect to solve combinatorial optimization problems. I realized that—even though the physics is very different—this system could also be implemented in analog electronics using memristors."
The recent paper published in Nature Electronics is the product of a collaboration between Kumar and other researchers in HPL's memristor team and Van Vaerenbergh and his colleagues, who specialize in an area of research known as photonics. Combining their expertise, these two teams were ultimately able to design a new memristor Hopfield neural network (mem-HNN) architecture that can harness the noise present in any electrical circuit, using an innovative trick.
"More specifically, we implemented a hysteretic feedback, which enabled both amplification and suppression of noise to any predetermined level, which could then be injected into the desired part of the circuit to enable the dislodging of the system from sub-optimal solutions," Kumar said. "Based on the experimental performance of the chip at the scales of 60 nodes, we project its performance to exceed the best CPUs and GPUs by a factor of 10,000 in energy consumed to solve any given optimization problem."
Kumar, Van Vaerenbergh and their colleagues think that their memristor Hopfield network would outperform any competing quantum or tabletop optical approaches by many orders of magnitude. Interestingly, these tabletop optical approaches were the starting point for many studies on optical next-gen combinatorial optimization accelerators carried out by Van Vaerenbergh and the rest of the HPL photonics team in the past.
The researchers tested their mem-HNN system by using it to solve different non-deterministic polynomial-time (NP)-hard problems and explored its scalability in a series of simulations. Their results were highly promising, suggesting that their system could be an ideal solution for solving combinatorial optimization problems on a large scale.
"Together with Suhas and the other collaborators working on the current analog electronics paper, we discovered that an electronic version of this system also has very appealing energy-efficiency and speed metrics, clearly outperforming the optical tabletop system," Van Vaerenbergh said. "Other photonic teams are now also trying to experimentally demonstrate the efficiency of an integrated photonics approach, including a team at MIT and a team at La Sapienza University, ISC-CNR and Sorbonne University."
The recent work by Kumar, Vaerenbergh and their colleagues proves that electronic noise, which most researchers try to reduce or eliminate when developing digital or analog hardware platforms, could actually prove useful for some optimization applications. By successfully combining this idea with the in-memory computing capabilities of a non-volatile memristor crossbar array, the new chip they designed could help to speed up calculations in various fields that rely on combinatorial optimization algorithms.
"One of the most intriguing results of this study is that circuit noise, which people have been trying hard to minimize for many decades, can actually be used for accelerating solutions to certain types of computationally hard problems, which people have also been trying to solve for many decades," Kumar said. "So, it's a combination of putting a typically unwanted circuit aspect to use in solving a type of problems we care very much about, known as NP-hard problems."
In the future, the new mem-HNN system developed by this team of researchers could be used to solve a number of NP-hard problems, including weather forecasting, navigation optimization, supply chain optimization and gene sequencing tasks. The new chip has so far only been demonstrated in the lab, but HPE could soon be scaling it up for manufacturing and moving it towards widespread commercialization.
"We are now also looking into more real-life use cases of our technology, instead of the academic benchmark tasks we've been using in our work so far," Van Vaerenbergh said. "Being able to speed up the solutions of problems that our customers care about is what we're aiming for."
More information: Fuxi Cai et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks, Nature Electronics (2020). DOI: 10.1038/s41928-020-0436-6
Suhas Kumar et al. Chaotic dynamics in nanoscale NbO2 Mott memristors for analogue computing, Nature (2017). DOI: 10.1038/nature23307
Dmitri B. Strukov et al. The missing memristor found, Nature (2008). DOI: 10.1038/nature06932
Nikolas Tezak et al. Integrated Coherent Ising Machines Based on Self-Phase Modulation in Microring Resonators, IEEE Journal of Selected Topics in Quantum Electronics (2019). DOI: 10.1109/JSTQE.2019.2929184
Mihika Prabhu et al. Accelerating recurrent Ising machines in photonic integrated circuits, Optica (2020). DOI: 10.1364/OPTICA.386613
Scalable spin-glass optical simulator. arXiv:2006.00828 [physics.optics]. arxiv.org/abs/2006.00828
© 2020 Science X Network