Special-purpose Chip May Solve Intractable Problems in Graph Theory and Analytics

From economics to security, scientific advancement to social welfare, the technology revolution enriches our lives. We have enjoyed the benefits of Moore’s Law, as technology scaling brought the power of supercomputers to our smartphones. But traditional scaling may have reached the point of diminishing returns, given the amount of unstructured data that needs to be processed in real time and the rise of computationally hard problems such as data optimization.

Nikhil Shukla, assistant professor in the University of Virginia Charles L. Brown Department of Electrical and Computer Engineering, is searching for alternative paradigms, architectures and hardware to overcome these limits by solving complex problems more efficiently. He borrows an essential idea from natural computing processes to replace digital switches with oscillators.

Shukla makes an analogy to fireflies, which emit light pulses to communicate with each other: “If you’ve ever watched fireflies in a garden, you might notice that when they first tune up, their light pulses are intermittent and uncoordinated—each pulse is a random event. Gradually, their light pulses organically synchronize, to become a periodic, controlled event.” In computer chip design, similar oscillatory behavior can be realized using extremely miniaturized components.

Shukla’s lab is prototyping a special-purpose chip that contains multiple such oscillators. The oscillators synch up to solve intractable problems in graph theory and analytics. Cyber intruder detection is one example. Graph theory tells us that a network will have a knowable number of nodes and links and that an intruder node will have no links. “Monitoring for unconnected nodes requires continual testing and verification of all the possible connections. This is computationally draining,” Shukla said. This case illustrates how speed, variation and reliability are critical to the practical implementation of emerging hardware technology.

Additionally, Shukla collaborates with Farzad Farnoud, assistant professor in the Charles L. Brown Department of Electrical and Computer Engineering and computer science department at the University of Virginia, to explore how this hardware can aid the design of communication codes that are immune to errors.

In this search for next-generation hardware, Shukla is playing the long game. “Computing is the backbone that has shaped society in spectacular ways, and I want to be able to contribute to this.”

His special-purpose prototype is just one step toward demonstrating the benefits of an oscillator-based chip design with regard to scalability, low power, high performance and easy integration with existing technology.