Recall your most recent road trip across the United States. While you may have searched for attractions and lodgings, you likely had little trouble using GPS or calling ahead, thanks to one of the 350,000 cell towers that dot the landscape. With cell tower rents exceeding $2,000 per month, and bids for wireless spectrum at an all-time high, your wireless provider allocates limited bandwidth to maximize users while ensuring seamless national coverage at a reasonable cost. Your cell phone's ability to talk with the closest tower, and the tower's ability to recognize your phone, involves careful planning. This answer to this practical problem lies in theoretical math.Nikhil Shukla, University of Virginia assistant professor of electrical and computer engineering with a joint appointment in materials science and engineering, has designed an alternative computing paradigm to solve this type of complex problem. “Not all computing problems are created equal,†Shukla said. Certain problems—known in the field as NP-hard problems—are near impossible to solve using digital machines because they need exponentially increasing computing resources. “These are among the class of problems to be solved with quantum computing, but our poor man's approach solves these problems without requiring cryogenic temperatures.†The cell tower example illustrates one type of NP-hard problem, called the maximum independent set. In this example, the goal is to maximize the number of cell phone towers that can be accommodated within a given spectral bandwidth without interference. In mathematical terms, the cell towers and cell phones compose a structured data set; the data and their relations are represented in a graph. Graphs are extensively used to model real-world systems including critical infrastructure. “To resolve the maximum independent set, our computations identify the largest set of nodes with no common edges,†Shukla said. The ones and zeros of conventional computing are not up to this task. The number of possible combinations—the solution space—increases exponentially with the scope of the problem. Whereas conventional computing must process each and every possibility sequentially, Shukla's team has identified a system that uses a highly parallelized approach to search for the optimal combination. Shukla and his students demonstrate their unorthodox computing approach in collaboration with UVA colleagues andSiddharth Joshi, assistant professor of computer science and engineering at Notre Dame. They developed an integrated circuit comprised of 30 oscillators that can synchronize with each other in highly reconfigurable patterns on a 1.44 square millimeter chip. 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 presented their design in a co-authored paper,Using Synchronized Oscillators to Compute the Maximum Independent Set, published Sept. 17 in Nature Communications. Now, jump into the future. Instead of driving cross-country, your road trip routes you through a big city in a self-driving car. Autonomous vehicles are watching each other as well as pedestrians, who themselves are eyeing all the vehicles. Everyone aims to get somewhere without bumping into each other. Sophisticated image processing does the choreography. The team's oscillator-based chip can partition pixels to compute relationships among the objects in the scene. “Our goal for this problem is to reduce, if not remove, the car's blind spots,†Shukla said. Helping an autonomous car safely navigate a crowded intersection illustrates another NP-hard problem, called the maximum cut. “In this example, I want to divide the graph into two mutually exclusive sets of nodes, the cars and the people, while making the number of edges—the ways in which they could potentially intersect—as large as possible,†Shukla said. The oscillator-based chip recreates how magnetic materials arrange themselves in the physical world and subsequently uses this physics as a computational platform from which to solve the max-cut problem. The team presents their solution to the max-cut problem in a co-authored paper,Experimental Demonstration of a Reconfigurable Coupled Oscillator Platform to Solve the Max-Cut Problem, published in the IEEE Journal on Exploratory Solid-State Computational Devices and Circuits. The team's oscillator-based system can solve both the maximum independent set and maximum cut problems because it can be programed in two different modes to analyze each problem's unique data structure and corresponding graphs. Shukla credits his Ph.D. advisee Antik Mallick with the circuit design and translating the design into a prototype chip with Joshi's guidance. Shukla's advisee Mohammad Khairul Bashar performed simulations to support and guide the experimental efforts.Benton Calhoun, professor of electrical and computer engineering at UVA, and his student Daniel S. Truesdell tested the chip and verified its computational properties. “These combinatorial optimization problems have a wide range of applications ranging from medical imaging to scheduling, even solving complex Sudoku puzzles,†Mallick said. Their experimentally demonstrated prototype integrated circuit is compatible with existing CMOS technology, highly reconfigurable, and only needs an area of few square millimeters. “This achievement provides a pathway to realizing various real-world applications in the near future,†Mallick said. Longer term, their research offers promise for an oscillator-based analog platform that complements digital computers for highly complex and intractable computational tasks. The next step is to increase the number of oscillators on a chip, as well as their functionality, to solve a broader spectrum of real-world problems at actual scale.