Dissertation Talk: Solving Hard Computational Problems using Oscillator Networks

Seminar | May 10 | 3-4 p.m. | Cory Hall, 540A/B

 Tianshi Wang, UC Berkeley

 Electrical Engineering and Computer Sciences (EECS)

Over the last few years, there has been considerable interest in Ising machines, ie, analog hardware for solving difficult (NP hard/complete) computational problems effectively. We present a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. Our scheme is theoretically rooted in a novel result that connects the phase dynamics of coupled oscillator systems with the Ising Hamiltonian. We show that oscillators can be designed to take on a binary phase, and a network of such binary oscillators has phase dynamics evolving naturally towards local minima of the Ising Hamiltonian. Two simple additional steps (ie, adding noise, and tuning the binarization strength up and down) enable the network to find excellent solutions of Ising problems. We evaluate our method on Ising versions of the MAX-CUT problems, showing that it improves on previously published results on several benchmark problems. Our scheme, which is amenable to realization using many kinds of oscillators from different physical domains, is particularly well suited for CMOS, in which it offers significant practical advantages over previous techniques for making Ising machines. We have demonstrated several working hardware prototypes using CMOS electronic oscillators, built on breadboards and PCBs, implementing Ising machines consisting of 4, 8, 32, 64 and 240 spins.

In this talk, we will also go over my other Ph.D. work that has led to the development of oscillator-based Ising machines In particular, we show that binary oscillators are not only useful for Ising, but can also be used to devise Finite State Machines for general-purpose Boolean computation with phase-based logic encoding, extending a scheme originally proposed by John von Neumann. We also briefly show my other research topics that have enabled the above work on oscillators, particularly those on the modelling of multi-domain nonlinear devices/systems, and those on advanced simulation analyses (eg, oscillator-specific analyses based on linear periodically time-varying system theory).

At the end of this talk, there will be a lab demonstration of a prototype oscillator-based Ising machine of 240 spins with programmable couplings. The prototype is built using off-the-shelf components on PCBs, roughly 10"x6"x4" in size, and interfaces with a laptop through USB.

 Tianshi Wang, Ph.D. student, EECS, UC Berkeley, Berkeley, CA 94720, tianshi@berkeley.edu, 510-6122379