ECE Featured News: "Probabilistically Speaking"
Professors Luke Theogarajan and Kerem Çamsarı
A hardware innovation enables ECE researchers to solve complex optimization problems faster while using much less energy
The classic traveling-salesman problem (TSP), along with a wide range of other complex optimization problems, is especially challenging to solve, because each new “node,” or option (an additional site or city to visit in the TSP) that is added to the territory exponentially increases the number of possible solutions. Similar problems include finding new molecules for medical applications, routing trucks for delivery or ride-share vehicles for customer pickups, distributing portfolio assets, and allocating channels for 5G cell phones. Each of those problems must be solved efficiently on the fly in real time.
“All of these belong to a class of problems called NP-complete” explains Luke Theogarajan, professor in the UC Santa Barbara Electrical and Computer Engineering (ECE) Department, and department chair since July 2024. “Most of them can be recast to minimize a cost function. The traveling salesman, for example, wants to visit all the required stops while driving the fewest possible miles, i.e., using the least energy possible.”
Theogarajan explains that such constrained optimization problems can be remapped into an energy-based model. “Basically, you reformulate the optimization as an energy-cost function to be minimized,” he explains. “An easy way to visualize this is to picture the solution as a deep valley (i.e., a global minima) in an energy landscape, with the position of a ball on this landscape denoting the state of the system. Under the constraint of gravity, the ball will follow a path to the valley, which is the solution, provided no other valleys exist (also called local minima) where the ball can get stuck.”
People go about solving such problems in several ways. One is to use a classical computer, but that is ineffective because it requires a vast amount of computing resources, a result of the above-mentioned exponentially increasing complexity associated with increasing the number of nodes. “Although approximation methods exist, trying to solve a one-hundred-city TSP precisely on a conventional computer would take a long time,” Theogarajan says. “For example, on a computer that could process one terabyte [1012 bytes] of data per second, the time needed to solve the problem would be approximately four trillion years.”
A recently developed way to solve such problems involves what is often referred to as probabilistic computing, an approach that is being widely adapted. In a recent paper relating to that field, titled “CMOS-compatible Ising and Potts annealing using single-photon avalanche diodes,” published in the journal Nature Electronics, Theogarajan and co-author Kerem Çamsarı, a pioneer in probabilistic computing who was just promoted to associate professor in ECE, describe a relatively simple stochastic device. Called a single-photon optoelectronic diode (SPAD), it shows great promise for solving many optimization problems much faster while using far fewer resources.
In their work, Theogarajan and Çamsarı investigated a class of energy-based models, namely Ising and Potts models. The Ising model is an energy model borrowed from statistical physics reflecting the spin configuration in a magnetic material. The co-authors used simulated annealing, a term borrowed from the heat-based treatment used to make metals less brittle, to find their solution. The basic idea is to use a hot (computational) temperature in the beginning, which allows the system to freely traverse the energy landscape. As the system starts to evolve, the temperature is slowly reduced, narrowing the system and thereby guiding it to find the optimal configuration.
“While most research in this field has focused on Ising models,” Theogarajan says, “we extended our hardware to enable Ising models, which are binary models in which each node has two states corresponding to some physical variable, such as up/down or one/zero, etc.). Potts, on the other hand, is an n-state model in which each node can be in one of n possibilities rather than just two. The simplest symbol representation is the one hot-encoded vector, which is a way of representing categorical data as numerical data to avoid arbitrary “greater/less than” ratings of items in categories — or categories themselves — that have no such inherent relationship.
Here, the position of the 1 in the string of n binary values denotes a particular possibility. For example, we can encode a four-city TSP problem in four Potts nodes, each having four states, such that each node represents a city — say, city A, B, C, or D — while each state encodes the time step in which the city was visited. In an ising machine, a group of four spins encodes that time, and those spins have to be configured such that only a single spin is on (no city can be visited twice), which results in a one-hot encoded pattern.
Assuming, for example, that the optimal route was C>A>D>B>D, the final solution would be Potts Node A(0100), B(0001), C(1000) and D(0010), with the position of each node indicating the optimal order in which to visit the cities. While this problem can also be solved using sixteen Ising nodes, that approach results in a lot of unwanted spurious transitions.
All such problems require deciding which is the next state, with the probability of going to any state from the current state expressed as a probability. In these types of machines, called Boltzmann machines, that probability depends on the negative exponential of the energy, so low energies are favored and high energies are disfavored. During his doctoral studies, Çamsarı and his advisor pioneered a method of implementing these types of algorithms in hardware. To distinguish their approach from the normal deterministic binary approach — which often results in getting “stuck” in local minima) — they termed the fundamental unit of representation the p-bit.
The original approach exploits the probabilistic nature of stochastic magnetic tunnel junctions. A stochastic magnetic tunnel junction (sMTJ) is a stochastic device, meaning that it has a random probability pattern. Unlike normal MTJs used in memory, the sMTJ states — the one and zero — are not separated by a huge physical barrier that usually prevents one from ever spontaneously becoming a zero (i.e. spin up from becoming spin down). In an sMTJ, that barrier is designed to be so low as to be almost nothing, so that at room temperature, the spin flips randomly from spin up to spin down (between one and zero) very quickly and randomly, turning magnetic tunnel junctions into p-bits.
Ease of manufacturing is an important consideration for any hardware. One of the biggest advantages of the SPAD-based approach, Çamsarı says, is that it is fully CMOS-compatible: “We can manufacture it using existing semiconductor foundries, which sets it apart from sMTJs that require specialized materials.”
In another important aspect of the project, the researchers exploited the SPAD’s ability to detect single photons — which demonstrate probabilistic arrival times — using that characteristic to engineer those probabilistic arrivals into a p-bit. As a result, Theogarajan notes, ”We have demonstrated a 144-spin (or -node) Ising machine and shown that we can solve NP-complete problems, such as graph coloring with three colors (useful for electronic design automation), and that the Potts model solves such problems far more efficiently than does the Ising machine.”
Theogarajan's Biomimetic Circuits & Nanosystems Group
Çamsarı's Orchestrating Physics for Unconventional Systems (OPUS) Lab
