Area Efficient Annealing Processor for Ising Model without Random Number Generator

Hidenori GYOTEN  Masayuki HIROMOTO  Takashi SATO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.2   pp.314-323
Publication Date: 2018/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017RCP0015
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Device and Architecture
Keyword: 
combinatorial optimization problem,  max-cut problem,  Ising model,  annealing,  FPGA,  

Full Text: PDF(971.2KB)
>>Buy this Article


Summary: 
An area-efficient FPGA-based annealing processor that is based on Ising model is proposed. The proposed processor eliminates random number generators (RNGs) and temperature schedulers, which are the key components in the conventional annealing processors and occupying a large portion of the design. Instead, a shift-register-based spin flipping scheme successfully helps the Ising model from stucking in the local optimum solutions. An FPGA implementation and software-based evaluation on max-cut problems of 2D-grid torus structure demonstrate that our annealing processor solves the problems 10-104 times faster than conventional optimization algorithms to obtain the solution of equal accuracy.