FPGA-Based Simulated Bifurcation Machine
Authors:
- 1 September 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 59-66
Abstract
Since many combinatorial optimization problems can be mapped onto ground-state search problems of Ising models, special-purpose machines for Ising problems have attracted intense attention. Simulated bifurcation (SB) is a recently proposed algorithm to solve these Ising problems. One of the remarkable features of SB is the high-degree parallelism underlying in the algorithm, providing an opportunity to solve the Ising problems very fast by massively parallel processing. In this work, we implement the SB algorithm on FPGAs by designing massively parallel custom circuits. We then compare the FPGA-based SB machines with a state-of-the-art machine called a coherent Ising machine (CIM), a highly optimized implementation of simulated annealing (SA), and GPU-based SB machines. SB machines with spin size of 2,048/4,096 (2K/4K) on an Arria10 GX1150 FPGA have 8,192 processing elements for the matrix-vector multiplication (MM) modules (the most computationally intensive part) and achieve computation throughput of 1,873/2,027 GMAC/s for the MM modules, outperforming 2K/4K SB machines on an Nvidia Tesla V100 GPU (113/183 GMAC/s). The 2K FPGA-SB solves all-to-all connected 2000-node MAX-CUT problem 14X (/124X) faster than the CIM (/the highly-optimized SA), with much better energy efficiency (288X better than the CIM).Keywords
This publication has 25 references indexed in Scilit:
- Bifurcation-based adiabatic quantum computation with a nonlinear oscillator networkScientific Reports, 2016
- Optimised simulated annealing for Ising spin glassesComputer Physics Communications, 2015
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- Quantum annealing with manufactured spinsNature, 2011
- Mersenne twisterACM Transactions on Modeling and Computer Simulation, 1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout DesignOperations Research, 1988
- Optimization by Simulated AnnealingScience, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences of the United States of America, 1982