Fully-Pipelined Architecture for Simulated Annealing-based QUBO Solver on the FPGA
Hiroshi Kagawa, Yasuaki Ito, Koji Nakano, Ryota Yasudo, Yuya Kawamata, Ryota Katsuki, Yusuke Tabata, Takashi Yazane, Kenichiro Hamano · 2020
The main contribution of this work is to propose a new fully-pipelined architecture for the QUBO solver on the FPGA. For the fully-pipelined architecture, we propose two local search algorithms based on the simulated annealing with different bit-selection strategies in the local search. The implementation supports a 1024-bit QUBO problem with 16-bit weights. For the problem, we use multiple instances and perform the local search in overlapped execution with pipeline structure. We implemented the proposed circuit on Xilinx UltraScale+ FPGA V09P. The implementation result shows that the circuit can search 3.58×1011solutions per second. In addition, by sharing the block RAM, we implemented a dual annealer architecture that has two QUBO solver into the FPGA. As a result, the dual annealer architecture can search 6.14 × 1011solutions per second.