EDGE: Efficient DAG-based Global Routing Engine

Jinwei Liu; Evangeline F.Y. Young

doi:10.1109/DAC56929.2023.10247702

EDGE: Efficient DAG-based Global Routing Engine

Jinwei Liu, Evangeline F.Y. Young

Department of Computer Science

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

11 Citations (Scopus)

Abstract

Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD'19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.

Original language	English
Title of host publication	2023 60th ACM/IEEE Design Automation Conference, DAC 2023
Publisher	IEEE
Number of pages	6
ISBN (Electronic)	9798350323481
ISBN (Print)	9798350323498
DOIs	https://doi.org/10.1109/DAC56929.2023.10247702
Publication status	Published - 15 Sept 2023
Event	60th ACM/IEEE Design Automation Conference - Moscone West, San Francisco, United States Duration: 9 Jul 2023 → 13 Jul 2023 https://60dac.conference-program.com/ (Conference program) https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding (Conference proceeding) https://www.dac.com/About/Conference-Archive/60th-DAC-2023 (Conference website)

Publication series

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

Conference

Conference	60th ACM/IEEE Design Automation Conference
Abbreviated title	DAC 2023
Country/Territory	United States
City	San Francisco
Period	9/07/23 → 13/07/23
Internet address	https://60dac.conference-program.com/ (Conference program) https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding (Conference proceeding) https://www.dac.com/About/Conference-Archive/60th-DAC-2023 (Conference website)

UN SDGs

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

Access to Document

10.1109/DAC56929.2023.10247702

Cite this

@inproceedings{688abd613e0645f8bc14be543a1b5e8d,

title = "EDGE: Efficient DAG-based Global Routing Engine",

abstract = "Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD'19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.",

author = "Jinwei Liu 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. CUHK14218422). Publisher Copyright: {\textcopyright} 2023 IEEE.; 60th ACM/IEEE Design Automation Conference, DAC 2023 ; Conference date: 09-07-2023 Through 13-07-2023",

year = "2023",

month = sep,

day = "15",

doi = "10.1109/DAC56929.2023.10247702",

language = "English",

isbn = "9798350323498",

series = "Proceedings - Design Automation Conference",

publisher = "IEEE",

booktitle = "2023 60th ACM/IEEE Design Automation Conference, DAC 2023",

address = "United States",

url = "https://60dac.conference-program.com/, https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding, https://www.dac.com/About/Conference-Archive/60th-DAC-2023",

}

TY - GEN

T1 - EDGE

T2 - 60th ACM/IEEE Design Automation Conference

AU - Liu, Jinwei

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. CUHK14218422). Publisher Copyright: © 2023 IEEE.

PY - 2023/9/15

Y1 - 2023/9/15

N2 - Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD'19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.

AB - Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD'19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.

UR - http://www.scopus.com/inward/record.url?scp=85173092160&partnerID=8YFLogxK

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

U2 - 10.1109/DAC56929.2023.10247702

DO - 10.1109/DAC56929.2023.10247702

M3 - Conference proceeding

AN - SCOPUS:85173092160

SN - 9798350323498

T3 - Proceedings - Design Automation Conference

BT - 2023 60th ACM/IEEE Design Automation Conference, DAC 2023

PB - IEEE

Y2 - 9 July 2023 through 13 July 2023

ER -

EDGE: Efficient DAG-based Global Routing Engine

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this