By Tianshi Wang and Jaijeet Roychowdhury
Editor’s Note: Winners of the 2019 Bell Labs Prize, Tianshi Wang is a PhD student and Jaijeet "JR" Roychowdhury is a professor of the Electrical Engineering and Computer Sciences Department at the University of California at Berkeley. Their work proposes a new type of processor element that will be significantly more efficient in computing discrete optimization problems. As guest bloggers for the Bell Labs Blog, they have shared the details of how they arrived at their ground-breaking innovation and their experiences at the Bell Labs Prize.
When we found out about the Bell Labs Prize, knowing its unique history and scientific reputation, we felt it could be just the right venue for our invention to be genuinely appreciated: a semiconductor-oscillator-based design for solving computationally hard problems. Indeed, we share some history with Bell Labs, since JR worked on aspects of oscillator analysis and design while working there in the mid-1990s.
The genesis of this work can be traced to our project Phase Logic using Oscillatory Nanosystems (PHLOGON), which started in Berkeley around 2008. As part of the PHLOGON project we showed, mathematically, how broad classes of oscillators could be quantized to hold binary, i.e., 1/0, logic in their phase or timing. The mechanism we exploited was a variant, called sub-harmonic injection locking (SHIL), of the synchronization phenomena widely observed in oscillators, natural or constructed, exemplified in nature by fireflies flashing in unison.
In 2016, during a visit to Purdue University, we learned about an approach towards hardware accelerators for difficult problems that Dr Supriyo Datta's group was working on. Tianshi got interested and started looking into the area. This led to his finding out about the laser-based coherent Ising machine developed by Dr Yoshihisa Yamamoto and, of course, the D-Wave machine. Both solve the Ising model, which models changes in the alignment of atomic spins. When he found out about the Ising model, Tianshi realized that SHIL could be applied to implement Ising spins, using binarized oscillator phases as the physical manifestation.
A key concept in the Ising model is that of the Hamiltonian or "energy", which is minimized when hard problems are solved. A similar looking, though hitherto unrelated, concept in oscillators is that of a "Lyapunov function,” that had been used to explain coupled oscillator synchronization. Tianshi soon realized that the Lyapunov function could be generalized to the case when each oscillator was binarized using SHIL. As he worked it out, he found that the Lyapunov function with SHIL was essentially equivalent to the Ising Hamiltonian, i.e., coupled oscillators under SHIL basically implement an Ising model. Since any system with a Lyapunov function naturally minimizes it as the system evolves (this is a generalization of the energy minimization principle widely used in physics), coupled oscillators under SHIL not only implement Ising, but by naturally minimizing the Lyapunov function, also solve the Ising problem.
Once this mathematical result had been established, we set out to work out the practical details for an electronic implementation. We ran simulations (to confirm that it would all work and to estimate performance), and devised, built and tested hardware designs. Tianshi did all these and by 2017, put out an arXiv paper. Even to our own surprise, the hardware designs – which started with only four oscillators and gradually progressed to our current system of 240 oscillators – all worked smoothly the first time. The only hiccups were due to small errors in wiring and component choices during the design of our 240-size system, which were rapidly detected and fixed. We were fortunate to have Leon Wu, a sophomore in our group, help greatly with key aspects of the 240-spin design.
We expected the Bell Labs Prize competition to be tough and indeed it was. We felt lucky to make it to the final round. One of the highlights of the process was the close and intensive interactions we had with our Bell Labs advisors Joachim Wabnig, Iraj Saniee, Sanjay Patel, and Chris White – extraordinarily bright people who each spent an incredible amount of time advising us. Along the way, we learned from them that certain important 5G wireless applications could benefit greatly from our scheme. We were already working towards industrializing this technology, but we have modified our immediate plans to prioritize 5G applications amongst our suite of applications. We look forward to low-level technical collaborations with our mentors and other Bell Labs scientists as we continue developing the technology.
To learn more about Wang and Roychowdhury’s research read our profile “Bell Labs Prize winners replicate the power of quantum computing on a chip”