Max-Cut Solving with Spiking Boltzmann Machine on Phase-Change Memory-Based Neuromorphic Hardware

Efficiently solving combinatorial optimization problems (COPs) such as Max-Cut is difficult due to the exponential growth in required computation resources with problem size. Boltzmann machine (BM) on neuromorphic systems has been widely studied for efficient COP solving. However, BM implementation requires asynchronous updates of neuron subsets, introducing neuron selection steps and preventing fully leveraging the parallelism of neuromorphic systems. Spiking neural network (SNN) which inherently exhibits asynchronous dynamics enables full parallelism of neuromorphic systems. In this work, we introduce our recent research [1] on hardware-oriented spiking BM approaches for Max-Cut solving, which overcome the limitations of conventional BM. Furthermore, this work includes hardware experiments on a neuromorphic SNN chip with phase-change memory (PCM) synapse array.

While the asynchronous dynamics of SNN enable efficient COP solving, they complicate hardware implementation of spike-driven state updates. To address this, we proposed a hardware-friendly method that defines the states of output neurons based on whether they fire within a time window, and uses these states as masks for input neurons to control whether the pre-generated input spike trains are activated or suppressed during sampling. This enables efficient state updates at the end of each time window. Additionally, bias terms in BM were encoded as spike trains to facilitate hardware implementation. We used leaky integrate-and-fire neurons for capacitor-based membrane potential integration and random walk noise [2] for hardware-friendly stochasticity. We validated our method through both simulations and hardware experiments using a neuromorphic SNN chip and FPGA. Our experimental scheme incorporates scan chain-based I/O interfaces and logic operations, implemented on a 6-transistor/2-resistor neuromorphic SNN chip with PCM synapse array [3][4]. By mapping multi-level weights onto the PCM synapse array, we successfully solved a 5-node Max-Cut problem. Further, to improve solution quality, several approaches considering the feasibility of hardware implementation were proposed. We introduced a bias split method that replaces a single large bias spike with finer multiple spikes for accurate searching. Two simulated annealing strategies were also developed to control randomness of searching: one adjusts the random walk noise size, and the other changes the time window length. Simulations confirmed the effectiveness of these approaches, showing fast and accurate convergence on Max-Cut problems with hundreds of nodes. In addition, we devised circuit design schemes that leverage the synapse array for efficient computation of convergence metrics, such as the cut value, presenting novel utilization of the synapse array.

Overall, this work highlights the potential of efficient and hardware-implementable SNN-based methods for COP, while broadening the application scope of neuromorphic synapse arrays, including those based on PCM. This work is, to the best of our knowledge, the first work to solve Max-Cut with a neuromorphic SNN chip.

Y.K., M.I., and J.P. contributed equally to this work. This research was conducted under the IBM-SNU Joint Study Agreement. This work was supported by K-CHIPS (Korea Collaborative & High-tech Initiative for Prospective Semiconductor Research) (2410000283, 20024760, 23008-45FC) funded by the Ministry of Trade, Industry & Energy (MOTIE, Korea). This work was supported by the Technology Innovation Program (20020803, Novel neuromorphic phase change memory device development and performance evaluation from device to circuit level) funded by the Ministry of Trade Industry & Energy (MOTIE, Korea). This research was supported by the LG Display (LGD-SNU Incubation Program).

[1] Y. G. Kang, Adv. Sci., 11, 46, (2024) [2] W. Gerstner, Cambridge University Press, (2014) [3] S. Kim, IEDM, 17.1.1-17.1.4, (2015) [4] M. Ishii, IEDM, 14.2.1-14.2.4, (2019)