A Time-Division Multiplexing Ising Machine on FPGAs
Kasho Yamamoto, Weiqiang Huang, Shinya Takamaeda-Yamazaki, Masayuki Ikebe, Tetsuya Asai, Masato Motomura · 2017
Annealing machines based on the Ising model which can solve combinatorial optimization problems is an emerging solution to overcome the performance limit of von Neumann architecture. However, it is difficult to solve practical combinatorial optimization problems by existing approaches of FPGA-based annealing machines, due to the small number of implementable spins. In this paper, we propose the time-division multiplexing Ising machine architecture that efficiently utilizes on-chip memory resources in an FPGA, in order to address large scale combinatorial optimization problems. The evaluation result shows that it is possible to increase the spin number by 64 times compared to the conventional annealing machine. In addition, the time-multiplxing architecture liberates a logical Ising structure representing problem constraints from the physical hardware structure on an FPGA. It provides the ability to implement more complex topologies corresponding to practical of problems on FPGAs.