An approach to realize Potts annealing using single-photon avalanche diodes

Massively parallel annealing processors, where the computing nodes on a single processor can simultaneously perform a series of coordinated operations, could have a huge potential for tackling complex sampling and optimization problems. Electronics engineers and physicists worldwide have thus been trying to devise new approaches that enable the realization of these devices.

Researchers at University of California, Santa Barbara, recently carried introduced a method to continuously control the computational temperature and implement the so-called Potts model, realizing Ising and Potts annealing using small light-detecting devices known as single-photon avalanche diodes (SPADs). Their proposed approach, outlined in a Nature Electronics paper, could inform the future development of massively parallel annealing processors.

“A few years ago, I was attending a talk by Prof. Kerem Y. Camsari (co-author of this paper), where he was talking about his elegant work on computing with probabilistic bits (p-bits) using Ising (or more generally Boltzmann) machines,” Prof. Luke Theogarajan, senior author of the paper, told Tech Xplore.

“A key component of the p-bit is a nanodevice, in his work the magnetic tunnel junction (MTJ), which provides the source of randomness required for probabilistic computing. I was working on imagers using SPADs at that time and I knew that these devices could be used to create random number generators. This ultimately sparked the idea for this work.”

Notably, unlike magnetic tunnel junctions (MTJs) and various other devices, SPADs can be easily integrated with widely used complementary metal-oxide semiconductor (CMOS)-based circuits and with existing processes for fabricating electronics. The favorable properties of these devices are what ultimately encouraged Theogajaran, in collaboration with William Whitehead, a graduate student he supervises, to try exploiting these devices as a source of entropy for so-called probabilistic computing applications.

“Unlike other approaches that use SPADs as a clocking source for a conventional digital pseudo-random generator, my brilliant graduate student William realized that the underlying physics leading to exponential changes in pulse rates could be exploited to realize the transfer function needed for sampling from the Boltzmann distribution (a key feature in p-bit computing),” Theogarajan said. “One of our goals was to prove we could achieve near ideal p-computing using SPADs. Furthermore, we were exploring some ideas in protein folding using evolutionary couplings, which uses the Potts model.”

The Potts model is a statistical mechanics-based framework, which is essentially a more powerful generalization of the two-state Ising model. Prof. Theogarajan, Whitehead, Prof. Camsari and graduate student Zachary Nelson from Theograjan’s group devised an approach to easily implement a Potts model in hardware, which had never been attempted before.

“One of the key advantages of using SPADs is the ability to readily integrate them into CMOS hardware, and we currently have some simple protypes that we are characterizing,” Theogarajan explained, “Also, unlike other devices trying to exploit natural noise the SPAD signal is an amplified pulse due to the avalanche multiplication process. Perhaps, the bigger advantage results from exploiting the natural exponentials present in our SPAD based hardware for the Ising and Potts models.”

Both the Ising and the Potts model are part of a broader class of frameworks known as energy-based models. Energy-based models have been widely implemented by researchers worldwide and have helped to tackle a wide range of practical problems by recasting the cost function in terms of energy.

“The most likely (or probable) solution is the optimal solution.” Theogarajan said. “The energy equation is called the Hamiltonian and the probability of being in a particular state is proportional to the (negative) exponential of the energy, which is a well-known result from statistical mechanics, resulting in the Boltzmann distribution. In simple terms, the Boltzmann distribution is the most probable state of the system in equilibrium.”

Deriving the so-called Boltzmann distribution is a computationally hard problem. Hardware or experimental implementations of the Ising and Potts model, on the other hand, enable the production of sample states from the distribution, rather than calculating the complete distribution.

“One way to visualize this would be to imagine a rugged landscape in the energy space with hills and valleys, each valley being a stable state,” Theogarajan said. “The system then moves from one valley (state) to the other with some probability depending on the difference in energy in the states. The goal of optimization tasks, for instance, is to find the lowest valley in the entire energy landscape (the state with the lowest energy or global minimum) when the cost function is recast as an energy function. However, often the system can get stuck in suboptimal valleys (also called local minima) if the barrier around the valley is high.”

A proposed approach to tackle this issue is to start a system with a high computational temperature. This allows the system to bounce out of local minima, slowly lowering the temperature to identify the optimal solution. This strategy is known as annealing, as it mimics the annealing process described by physics theory.

“So, how do SPADs fit in here? The pulse rate of the SPADs is intimately coupled to the photon arrival time (or photon statistics),” Theogarajan explained. “It is well known the photon statistics follow a Poisson process, the arrival time between photons is exponentially distributed. If this time between pulses (or rate) is converted into a voltage using a filter and compared to a voltage representing the energy the resulting rate of pulses from this comparison will follow an exponential proportional to the energy, precisely what is required to implement the Boltzmann distribution.”

After this process is completed, all that is left is to convert the brief pulses produced by SPADs into the states required by Ising and Potts implementations. Theogarajan and colleagues achieved this using a simple set-reset flip-flop technique and a winner take-all latch mechanism to implement the one-hot encoded vector of the Potts model.

“The winner takes-all latching mechanism basically sets the current output to 1 if it receives an event and resets (or inhibits) all other nodes of the vector forming the Potts node,” Theogarajan said. “The event nature of the SPAD output coupled with the mechanism to realize the exponential reduces all the computation into a single compact device, which would normally take 1000’s of transistor to achieve. More importantly the implementation of the exponential is highly accurate since it is tied to the intrinsic physical properties of the device.”

A further interesting characteristic of SPADs is that they can realize annealing in real-time using the light intensity and/or excess bias voltage. These are variables that can control the overall pulse rate of the devices and thus also their computational temperature.

“This is very different from current annealing approaches, where the weights are scaled in each anneal step to change the computational temperature,” Theogarajan said. “Overall, our study highlights the power of the Potts model. Using the same underlying hardware, we were able to show the Potts model with its intrinsic one hot vector implementation achieves solutions almost 10X faster than the Ising implementation. To the best of our knowledge, this is first direct Potts implementation in hardware.”

The recent work by this team of researchers could have various practical implications. For instance, their approach to realize Potts annealing in hardware systems could inform the development of tools that can find approximate solutions to nondeterministic polynomial time problems.

“One practical area of consequence is 5G MIMO channel allocation,” Theogarajan said. “Another example would be floor planning for chip design. Ising and Potts model truly sampling from the underlying distribution using few training examples can be useful in AI/ML applications as well.”

In their next studies, Theogarajan and his colleagues plan to realize their Potts annealing implementation on a CMOS chip. The team has already made some progress towards this goal, for instance verifying integrated single neuron circuits in CMOS that is 65nm in size.

“These circuits are incredibly small and use approximately 50 µm², in comparison a single 2³¹-1 pseudo random number generator (excluding all the other circuitry needed to implement the tangent hyperbolic) occupies approximately 200 µm² in the same technology node,” Theogarajan added. “We will design a chip incorporating many spins/neurons along with the synapse (multiply and accumulate) very soon. We are additionally evaluating architectures leveraging the Potts model for computation.”

© 2023 Science X Network