IEEE International Symposium on Circuits and Systems proceedings
FPGA-Based Dense-Sparse Adaptive Simulated Bifurcation Ising Machine for MAX-CUT Problems
Yihang Peng, Chengjie Wang, Yudi Zhao, Shisheng Xiong
Abstract
Combinatorial Optimization Problems (COP) are mostly arbitrary and sparse in practice. Simulated bifurcation (SB), as an emerging quantum-inspired heuristic algorithm exhibits strong performance in solving COP. However, existing SB-based Ising machines lack adaptability to sparse graphs, require excessive hardware resources, and struggle to balance convergence speed and solution quality. To address these issues, this paper proposes a fully connected FPGA-based dense-sparse adaptive SB Ising Machine (DSA-SBM) for sparse COP. DSA-SBM adopts an adaptive SB strategy rooted in saturating-growth control to balance system convergence speed and optimal solution accuracy. Its hardware features a dense-sparse adaptive architecture with compressed sparse row (CSR) format storage for 5-bit coefficient matrix and supports dynamic data allocation and adaptive matrix-spin multiplication. Implemented on Xilinx UltraScale+ XCZU7EV FPGA with 151 MHz clock frequency, it achieves 13.81× higher energy efficiency than the original dense SB Ising machine. In the 2000 spin MAX-CUT benchmark, it achieves 99.56% accuracy with an average of 0.687 ms, delivering a 123.6-170.5× speedup compared to the GPU.