March: MAze routing under a concurrent and hierarchical scheme for buses

Jingsong Chen; Jinwei Liu; Gengjie Chen; Dan Zheng; Evangeline F.Y. Young

doi:10.1145/3316781.3317860

March: MAze routing under a concurrent and hierarchical scheme for buses

Jingsong Chen
, Jinwei Liu
, Gengjie Chen
, Dan Zheng
, Evangeline F.Y. Young

Department of Computer Science

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

19 Citations (Scopus)

Abstract

The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.

Original language	English
Title of host publication	Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
Place of Publication	New York
Publisher	IEEE
Number of pages	7
ISBN (Electronic)	9781450367257
DOIs	https://doi.org/10.1145/3316781.3317860
Publication status	Published - 2 Jun 2019
Event	56th ACM/IEEE Design Automation Conference - Las Vegas, United States Duration: 2 Jun 2019 → 6 Jun 2019 https://ieeexplore.ieee.org/xpl/conhome/8791231/proceeding (Link to conference proceedings) https://dl.acm.org/doi/proceedings/10.1145/3316781 (Link to conference proceedings)

Publication series

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

Conference

Conference	56th ACM/IEEE Design Automation Conference
Abbreviated title	DAC 2019
Country/Territory	United States
City	Las Vegas
Period	2/06/19 → 6/06/19
Internet address	https://ieeexplore.ieee.org/xpl/conhome/8791231/proceeding (Link to conference proceedings) https://dl.acm.org/doi/proceedings/10.1145/3316781 (Link to 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.1145/3316781.3317860

Cite this

@inproceedings{f3216ad3f0b74f5a9ece59c5dc88b656,

title = "March: MAze routing under a concurrent and hierarchical scheme for buses",

abstract = "The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.",

author = "Jingsong Chen and Jinwei Liu and Gengjie Chen and Dan Zheng 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. CUHK14202218). Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 56th ACM/IEEE Design Automation Conference, DAC 2019 ; Conference date: 02-06-2019 Through 06-06-2019",

year = "2019",

month = jun,

day = "2",

doi = "10.1145/3316781.3317860",

language = "English",

series = "Proceedings - Design Automation Conference",

publisher = "IEEE",

booktitle = "Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/8791231/proceeding, https://dl.acm.org/doi/proceedings/10.1145/3316781",

}

Chen, J, Liu, J, Chen, G, Zheng, D & Young, EFY 2019, March: MAze routing under a concurrent and hierarchical scheme for buses. in Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019., 216, Proceedings - Design Automation Conference, IEEE, New York, 56th ACM/IEEE Design Automation Conference, Las Vegas, Nevada, United States, 2/06/19. https://doi.org/10.1145/3316781.3317860

March: MAze routing under a concurrent and hierarchical scheme for buses. / Chen, Jingsong; Liu, Jinwei; Chen, Gengjie et al.
Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. New York: IEEE, 2019. 216 (Proceedings - Design Automation Conference).

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

TY - GEN

T1 - March

T2 - 56th ACM/IEEE Design Automation Conference

AU - Chen, Jingsong

AU - Liu, Jinwei

AU - Chen, Gengjie

AU - Zheng, Dan

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. CUHK14202218). Publisher Copyright: © 2019 Association for Computing Machinery.

PY - 2019/6/2

Y1 - 2019/6/2

N2 - The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.

AB - The continuous development of modern VLSI technology has brought new challenges for on-chip interconnections. Different from classic net-by-net routing, bus routing requires all the nets (bits) in the same bus to share similar or even the same topology, besides considering wire length, via count, and other design rules. In this paper, we present MARCH, an efficient maze routing method under a concurrent and hierarchical scheme for buses. In MARCH, to achieve the same topology, all the bits in a bus are routed concurrently like marching in a path. For efficiency, our method is hierarchical, consisting of a coarse-grained topology-aware path planning and a fine-grained track assignment for bits. Additionally, an effective rip-up and reroute scheme is applied to further improve the solution quality. In experimental results, MARCH significantly outperforms the first place at 2018 IC/CAD Contest in both quality and runtime.

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

UR - https://dl.acm.org/doi/10.1145/3316781.3317860

U2 - 10.1145/3316781.3317860

DO - 10.1145/3316781.3317860

M3 - Conference proceeding

AN - SCOPUS:85067804118

T3 - Proceedings - Design Automation Conference

BT - Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019

PB - IEEE

CY - New York

Y2 - 2 June 2019 through 6 June 2019

ER -

March: MAze routing under a concurrent and hierarchical scheme for buses

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this