A fully parallel densely connected probabilistic Ising machine with inertia for real-time applications

The Ising optimization problem is a canonical combinatorial optimization problem to which many other problems can be efficiently mapped. In recent years, probabilistic Ising machines (PIMs) based on networks of probabilistic bits (p-bits) have gained attention due to their combination of simple binary-state dynamics, intrinsic stochasticity, and broad implementation flexibility. Traditional PIMs update spins sequentially to preserve detailed balance and enable exact Gibbs sampling on dense Ising graphs. However, this sequential updating imposes a scalability bottleneck, limiting the throughput and hardware efficiency of PIM implementations. To address this, researchers have proposed various methods, including using graph coloring to partition spins into independent sets for parallel updates, but these solutions are often inefficient for dense graphs or require more hardware resources.

It has been thought that Ising spins connected in probabilistic Ising machines cannot be updated in parallel without ruining the machine's solving ability. This presents a major challenge for using probabilistic Ising machines as fast solvers for densely connected problems. Sequential updating limits the scalability and hardware efficiency of PIMs because each update requires O(N) steps. Parallel updating leads to repeated oscillations in the network state, preventing convergence to the Boltzmann distribution. Therefore, achieving fully parallel updates without affecting convergence is a critical problem to solve.

The core innovation of this paper is the introduction of a modified Ising spin dynamics with an inertia term, enabling fully parallel synchronous updates in probabilistic Ising machines. The inertia term biases each spin toward its previous state, suppressing oscillations and ensuring stable convergence to low-energy states. This innovation challenges conventional wisdom, solving the oscillation problem caused by parallel updates and allowing the system to stably converge to low-energy states, with significant advantages over existing methods like momentum annealing and coherent Ising machines. Additionally, the paper demonstrates how to optimize the hardware implementation through hardware-software co-design, achieving efficient FPGA implementation.

• �� Introduce Inertia Term: Add an inertia term to Ising spin dynamics to suppress spin oscillations.
• �� Algorithm Simulations: Validate the effectiveness of the inertia term through algorithm simulations.
• �� FPGA Hardware Emulation: Conduct hardware emulation on FPGA to verify the feasibility of fully parallel updates.
• �� FPGA Experiments: Perform experiments on actual FPGA to verify improved success probability.
• �� Hardware-Software Co-Design: Optimize solver ability and silicon resource usage to achieve efficient FPGA implementation.

The experimental design includes evaluations on various abstract (Max-Cut and Sherrington-Kirkpatrick-model) and application-derived (MIMO, wireless detection) dense Ising benchmark instances. Random unweighted Erdős–Rényi graphs with edge probability 0.5 were used. For each problem size, 100 independently generated instances were evaluated, with each instance undergoing 256 independent trials, each run for 100N update steps. The experiments implemented both conventional PIM and PIMI on FPGA and benchmarked their performance.

For Max-Cut and SK-1 model at a problem size of 200, PIMI achieved an average speedup of approximately 35×, with the best single-instance speedup reaching 150×. The results show that PIMI requires fewer clock cycles to reach a solution than conventional PIM across all tested problem sizes. In real-time MIMO detection for modern 5G cellular wireless networks, PIMI meets stringent solution quality and latency/throughput requirements while using a practically reasonable silicon area.

The method has broad application potential in real-time applications, particularly in real-time MIMO detection for modern 5G cellular wireless networks. Through hardware-software co-design, PIMI can meet stringent solution quality and latency/throughput requirements while using a practically reasonable silicon area. Additionally, PIMI can be applied to other types of combinatorial optimization problems, such as logistics optimization, financial risk management, etc.

Although the inertia term suppresses oscillations, convergence issues may still exist in extremely dense graphs. Hardware implementation requires fine parameter tuning, which may increase design complexity. Further verification of its generality in specific application scenarios may be needed. Future research directions include further optimizing the parameters of the inertia term to adapt to a wider range of application scenarios. Additionally, exploring the application of this method to other types of combinatorial optimization problems and implementation on ASICs to further improve efficiency.