Not all computing problems are created equal. Certain problems—commonly known as NP-hard problems—are considered intractable to solve using digital machines and require exponentially increasing resources for increasing sizes of the input. A team of electrical and computer engineers from the University of Virginia and Notre Dame demonstrate an unorthodox approach to help solve some of the toughest problems in computing. Published September 17 in Nature Communications, their paper, Using Synchronized Oscillators to Compute the Maximum Independent Set, presents an integrated circuit comprised of 30 oscillators that are able to synchronize with each other in highly reconfigurable patterns on a 1.44 square millimeter chip.Using synchronized oscillators is ideal for solving hard optimization problems like computing the maximum independent set, that finds application in real-world challenges such as coding theory, resource allocation and VLSI design.
Nikhil Shukla, assistant professor of electrical and computer engineering with a joint appointment in materials science and engineering, is interested in understanding how the dynamical properties of the coupled oscillators can be leveraged to solve these computationally hard problems. Shukla credits his Ph.D. advisee Antik Mallick with the circuit design and translating the design into a prototype chip, guided by Siddharth Joshi, assistant professor of computer science and engineering at Notre Dame. Shukla's group worked with Benton Calhoun, professor of electrical and computer engineering at UVA, and his student Daniel S. Truesdell to test the chip and verify its computational properties. Shukla's advisee Mohammad Khairul Bashar performed simulations to support and guide the experimental efforts.
The ingenuity of their approach lies in allowing the natural physics of oscillators and synchronization to do the computing. Instead of computing with 1s and 0s like digital computers, the solution emerges from the spatial-temporal properties of the system—the behavior of one oscillator with respect to others—over time. The team's design demonstrates how an oscillator-based chip can solve the MIS problem efficiently. Longer term, their research offers promise for an oscillator-based analog platform that complements digital computers for highly complex and intractable computational tasks.