For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Area Efficient Annealing Processor for Ising Model without Random Number Generator
Hidenori GYOTEN Masayuki HIROMOTO Takashi SATO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2018/02/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Device and Architecture
combinatorial optimization problem, max-cut problem, Ising model, annealing, FPGA,
Full Text: PDF>>
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.