Oscillator-based Ising Network Computation
Seminar | November 20 | 4-5 p.m. | 531 Cory Hall
Tianshi Wang, Graduate Student, EECS Department, UC Berkeley
More than 90 years ago, the German physicist Ernst Ising analyzed a mathematical model of ferromagnetism, in which "spins" coupled in a graph try to minimize a collective energy that became known as the Ising Hamiltonian. We now know that many difficult real-world optimization problems, such as job-shop scheduling, protein folding, VLSI routing, etc., (in fact, all Karp's 21 NP-complete problems) can be mapped to minimizing the Ising Hamiltonian. A physical implementation of coupled "spins" that can do so, namely an Ising machine, has the potential of outperforming conventional algorithms run on CPUs in terms of both speed and energy efficiency. Ising machines have been attracting considerable research attention in recent years, with incarnations based on optics and novel nano-devices (including quantum ones) having been proposed.
Our work shows that implementations of Ising machines need not rely on "futuristic" devices. Instead, we show that almost all types of nonlinear self-sustaining oscillators can represent Ising "spins" physically. Several tried-and-tested types of self-sustaining oscillators are suitable, offering the advantages of scalability to large numbers of spins, high-speed operation, and straightforward design and fabrication using standard IC technologies.
The mechanism underlying the suitability of oscillators for Ising machines is injection locking, familar in many natural and man-made systems -- including Huygens' clocks, biological circadian rhythms, the synchronized flashing of fireflies, frequency-division circuits, etc. We show that specially engineered oscillators, whose phase is "Booleanized" using a special type of injection locking, can be networked such that they synchronize to minimize Ising Hamiltonians. Indeed, such "Booleanized oscillators" are useful not only for Ising machines, but can also be used to devise Finite State Machines (FSMs) for general-purpose computing, extending a scheme originally proposed by John von Neumann.
In this talk, we will discuss the key ideas and mechanisms underlying our schemes, and also show several examples in both simulation and hardware for oscillator-based computing.
Tianshi Wang is a PhD student in the EECS Department here at UC Berkeley, working with Jaijeet Roychowdhury. His research interests include the theory, characterization and compact modelling of novel electronic and multi-domain devices, as well as their applications in novel computational architectures and paradigms. As part of his PhD work, he has shown that nonlinear oscillators can implement phase-encoded general-purpose Boolean computation systems, as well as Ising-model-inspired combinatorial optimization solvers.
He has also worked on multi-physics device modelling, particularly for hysteretic devices. This work led to the Berkeley Memristor Models (BMM) and the Berkeley Electrostatic Discharge (BESD) device models, the first well-posed models for memristors and ESD devices. He has been the primary contributor to the Berkeley Model and Algorithm Prototyping Platform (MAPP), a MATLAB-based system for rapid development and debugging of novel device models and analysis algorithms. Through these activities, he has gained considerable familiarity with a wide range of semiconductor, optical, magnetic, and spin-based device models, as well as with advanced simulation algorithms. This experience with devices and algorithms has been the foundation of his work on oscillator-based computation, to design which he wrote his own CAD tools. All software from his work has been released as open source.
Tianshi is a recipient of EECS' Leon Chua Award for Nonlinear Science.