An Annealing Processor based on 1k-Spin Fully-Connected Ising Model for Combinatorial Optimization Problems
Zhanhong Huang, Xiangrui Wang, Dong Jiang, Yukang Huang, Enyi Yao · 2023
Combinatorial optimization problems (COPs) find extensive applications in industrial and social scenarios such as transportation and communication. As the size of NP-hard COPs increases, it becomes impossible to obtain the optimal solution using an enumerative method. Recently, Ising model based annealing processors have received increasing attention due to their potential for rapidly converging to the near-optimal solutions after mapping the problem to them. This paper presents a novel annealing processor (AP) with 1024 fully-connected spins based on a modified Ising model annealing algorithm, which is more suitable for hardware implementation compared to conventional simulated annealing (SA) algorithm. The prototype is implemented using FPGA with the operation frequency up to 100MHz. We tested our design on various G-set problems with an average cut accuracy of 99.19% achieved. The proposed design outperforms the conventional CPU-based method by achieving a max speedup of 2204x for G51.