TY - GEN
T1 - An Ising model mapping to solve rectangle packing problem
AU - Terada, Kotaro
AU - Oku, Daisuke
AU - Kanamaru, Sho
AU - Tanaka, Shu
AU - Hayashi, Masato
AU - Yamaoka, Masanao
AU - Yanagisawa, Masao
AU - Togawa, Nozomu
N1 - Funding Information:
This paper is based on the results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO). One of the authors (K. T.) was supported partially by JSPS KAKENHI Grant-in-Aid for JSPS Fellows and Waseda Research Institute for Science and Engineering, Grant-in-Aid for Young Scientists (Early Bird). One of the authors (S. T.) was supported by JST, PRESTO.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/6/5
Y1 - 2018/6/5
N2 - Floorplanning of modules has been a significant role in VLSI design automation and it can be formulated as the 'Rectangle Packing Problem.' Ising model-based computers (or annealing machines) are the type of a non-von Neumann computer and recently expected to solve combinatorial optimization problems efficiently. In this paper, we propose a mapping of 'Rectangle Packing Problem' for solving it by the annealing machines. In our proposed mapping, a sequence-pair is represented on an Ising model. Our proposed approach maps a 'Rectangle Packing Problem' with N rectangles onto a 3N3-spin logical Ising model. Experimental results demonstrate that through the proposed approach we can solve the problem with 18 rectangles at the maximum on a fully-connected annealing machine and the problem with three rectangles at the maximum on 20k-spin CMOS annealing machine.
AB - Floorplanning of modules has been a significant role in VLSI design automation and it can be formulated as the 'Rectangle Packing Problem.' Ising model-based computers (or annealing machines) are the type of a non-von Neumann computer and recently expected to solve combinatorial optimization problems efficiently. In this paper, we propose a mapping of 'Rectangle Packing Problem' for solving it by the annealing machines. In our proposed mapping, a sequence-pair is represented on an Ising model. Our proposed approach maps a 'Rectangle Packing Problem' with N rectangles onto a 3N3-spin logical Ising model. Experimental results demonstrate that through the proposed approach we can solve the problem with 18 rectangles at the maximum on a fully-connected annealing machine and the problem with three rectangles at the maximum on 20k-spin CMOS annealing machine.
UR - http://www.scopus.com/inward/record.url?scp=85049339579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049339579&partnerID=8YFLogxK
U2 - 10.1109/VLSI-DAT.2018.8373233
DO - 10.1109/VLSI-DAT.2018.8373233
M3 - Conference contribution
AN - SCOPUS:85049339579
T3 - 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018
SP - 1
EP - 4
BT - 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018
Y2 - 16 April 2018 through 19 April 2018
ER -