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.
Hidenori GYOTEN
Kyoto University
Masayuki HIROMOTO
Kyoto University
Takashi SATO
Kyoto University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hidenori GYOTEN, Masayuki HIROMOTO, Takashi SATO, "Area Efficient Annealing Processor for Ising Model without Random Number Generator" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 2, pp. 314-323, February 2018, doi: 10.1587/transinf.2017RCP0015.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017RCP0015/_p
Copy
@ARTICLE{e101-d_2_314,
author={Hidenori GYOTEN, Masayuki HIROMOTO, Takashi SATO, },
journal={IEICE TRANSACTIONS on Information},
title={Area Efficient Annealing Processor for Ising Model without Random Number Generator},
year={2018},
volume={E101-D},
number={2},
pages={314-323},
abstract={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.},
keywords={},
doi={10.1587/transinf.2017RCP0015},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Area Efficient Annealing Processor for Ising Model without Random Number Generator
T2 - IEICE TRANSACTIONS on Information
SP - 314
EP - 323
AU - Hidenori GYOTEN
AU - Masayuki HIROMOTO
AU - Takashi SATO
PY - 2018
DO - 10.1587/transinf.2017RCP0015
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2018
AB - 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.
ER -