REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning

Jinwei Liu; Gengjie Chen; Evangeline F.Y. Young

doi:10.1109/DAC18074.2021.9586209

REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning

Jinwei Liu
, Gengjie Chen
, Evangeline F.Y. Young

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

37 Citations (Scopus)

Abstract

Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net's n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of ≤ 0.36% length error on average for nets with ≤ 50 pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.

Original language	English
Title of host publication	2021 58th ACM/IEEE Design Automation Conference, DAC 2021
Publisher	IEEE
Pages	1135-1140
Number of pages	6
ISBN (Electronic)	9781665432740
DOIs	https://doi.org/10.1109/DAC18074.2021.9586209
Publication status	Published - 5 Dec 2021
Event	58th ACM/IEEE Design Automation Conference, DAC 2021 - Online and , San Francisco, United States Duration: 5 Dec 2021 → 31 Dec 2021 https://www.dac.com/About/Conference-Archive/58th-DAC-2021 (Conference website) https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d (Conference programme ) https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding (Conference proceedings)

Publication series

Name	Proceedings - Design Automation Conference
Volume	2021-December
ISSN (Print)	0738-100X

Conference

Conference	58th ACM/IEEE Design Automation Conference, DAC 2021
Country/Territory	United States
City	San Francisco
Period	5/12/21 → 31/12/21
Internet address	https://www.dac.com/About/Conference-Archive/58th-DAC-2021 (Conference website) https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d (Conference programme ) https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding (Conference proceedings)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Access to Document

10.1109/DAC18074.2021.9586209

Cite this

@inproceedings{ab2a657835664161ba3a0cf6ef4432d0,

title = "REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning",

abstract = "Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net's n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of ≤ 0.36\% length error on average for nets with ≤ 50 pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.",

author = "Jinwei Liu and Gengjie Chen and Young, \{Evangeline F.Y.\}",

note = "The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14209320) Publisher Copyright: {\textcopyright} 2021 IEEE.; 58th ACM/IEEE Design Automation Conference, DAC 2021 ; Conference date: 05-12-2021 Through 31-12-2021",

year = "2021",

month = dec,

day = "5",

doi = "10.1109/DAC18074.2021.9586209",

language = "English",

series = "Proceedings - Design Automation Conference",

publisher = "IEEE",

pages = "1135--1140",

booktitle = "2021 58th ACM/IEEE Design Automation Conference, DAC 2021",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/58th-DAC-2021, https://www.dac.com/Portals/0/Documents/Conference/DAC58\%20Onsite\%20Guide\_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw\%3d\%3d, https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding",

}

Liu, J, Chen, G & Young, EFY 2021, REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning. in 2021 58th ACM/IEEE Design Automation Conference, DAC 2021. Proceedings - Design Automation Conference, vol. 2021-December, IEEE, pp. 1135-1140, 58th ACM/IEEE Design Automation Conference, DAC 2021, San Francisco, California, United States, 5/12/21. https://doi.org/10.1109/DAC18074.2021.9586209

REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning. / Liu, Jinwei; Chen, Gengjie; Young, Evangeline F.Y.
2021 58th ACM/IEEE Design Automation Conference, DAC 2021. IEEE, 2021. p. 1135-1140 (Proceedings - Design Automation Conference; Vol. 2021-December).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - REST

T2 - 58th ACM/IEEE Design Automation Conference, DAC 2021

AU - Liu, Jinwei

AU - Chen, Gengjie

AU - Young, Evangeline F.Y.

N1 - The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14209320) Publisher Copyright: © 2021 IEEE.

PY - 2021/12/5

Y1 - 2021/12/5

N2 - Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net's n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of ≤ 0.36% length error on average for nets with ≤ 50 pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.

AB - Rectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net's n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a reinforcement learning based algorithm called REST for RSMT construction. After training, REST constructs RSMT of ≤ 0.36% length error on average for nets with ≤ 50 pins. The average time needed for one net is fewer than 1.9 ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.

UR - https://www.scopus.com/pages/publications/85119439149

UR - https://ieeexplore.ieee.org/document/9586209

U2 - 10.1109/DAC18074.2021.9586209

DO - 10.1109/DAC18074.2021.9586209

M3 - Conference proceeding

AN - SCOPUS:85119439149

T3 - Proceedings - Design Automation Conference

SP - 1135

EP - 1140

BT - 2021 58th ACM/IEEE Design Automation Conference, DAC 2021

PB - IEEE

Y2 - 5 December 2021 through 31 December 2021

ER -

REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement Learning

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this