An Ising model mapping to solve rectangle packing problem

Kotaro Terada; Daisuke Oku; Sho Kanamaru; Shu Tanaka; Masato Hayashi; Masanao Yamaoka; Masao Yanagisawa; Nozomu Togawa

doi:10.1109/VLSI-DAT.2018.8373233

An Ising model mapping to solve rectangle packing problem

Kotaro Terada, Daisuke Oku, Sho Kanamaru, Shu Tanaka, Masato Hayashi, Masanao Yamaoka, Masao Yanagisawa, Nozomu Togawa

School of Fundamental Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

19 Citations (Scopus)

Abstract

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 3N³-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.

Original language	English
Title of host publication	2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1-4
Number of pages	4
ISBN (Electronic)	9781538642603
DOIs	https://doi.org/10.1109/VLSI-DAT.2018.8373233
Publication status	Published - 2018 Jun 5
Event	2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018 - Hsinchu, Taiwan, Province of China Duration: 2018 Apr 16 → 2018 Apr 19

Publication series

Name	2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018

Other

Other	2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018
Country/Territory	Taiwan, Province of China
City	Hsinchu
Period	18/4/16 → 18/4/19

ASJC Scopus subject areas

Safety, Risk, Reliability and Quality
Control and Optimization
Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/VLSI-DAT.2018.8373233

Cite this

Terada, K., Oku, D., Kanamaru, S., Tanaka, S., Hayashi, M., Yamaoka, M., Yanagisawa, M., & Togawa, N. (2018). An Ising model mapping to solve rectangle packing problem. In 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018 (pp. 1-4). (2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/VLSI-DAT.2018.8373233

An Ising model mapping to solve rectangle packing problem. / Terada, Kotaro; Oku, Daisuke; Kanamaru, Sho et al.
2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 1-4 (2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Terada, K, Oku, D, Kanamaru, S, Tanaka, S, Hayashi, M, Yamaoka, M, Yanagisawa, M & Togawa, N 2018, An Ising model mapping to solve rectangle packing problem. in 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018. 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018, Institute of Electrical and Electronics Engineers Inc., pp. 1-4, 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018, Hsinchu, Taiwan, Province of China, 18/4/16. https://doi.org/10.1109/VLSI-DAT.2018.8373233

Terada K, Oku D, Kanamaru S, Tanaka S, Hayashi M, Yamaoka M et al. An Ising model mapping to solve rectangle packing problem. In 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 1-4. (2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018). doi: 10.1109/VLSI-DAT.2018.8373233

@inproceedings{7fef43a6ce764d5baa69ba73253cbcdc,

title = "An Ising model mapping to solve rectangle packing problem",

abstract = "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.",

author = "Kotaro Terada and Daisuke Oku and Sho Kanamaru and Shu Tanaka and Masato Hayashi and Masanao Yamaoka and Masao Yanagisawa and Nozomu Togawa",

note = "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: {\textcopyright} 2018 IEEE.; 2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

year = "2018",

month = jun,

day = "5",

doi = "10.1109/VLSI-DAT.2018.8373233",

language = "English",

series = "2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1--4",

booktitle = "2018 International Symposium on VLSI Design, Automation and Test, VLSI-DAT 2018",

}

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 -

An Ising model mapping to solve rectangle packing problem

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this