FastPass: Fast Pin Access Analysis with Incremental SAT Solving

Fangzhou Wang; Jinwei Liu; Evangeline F.Y. Young

doi:10.1145/3569052.3571879

FastPass: Fast Pin Access Analysis with Incremental SAT Solving

Fangzhou Wang
, Jinwei Liu
, Evangeline F.Y. Young

Department of Computer Science

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

4 Citations (Scopus)

Abstract

Pin access analysis is a critical step in detailed routing. With complicated design rules and pin shapes, efficient and accurate pin accessibility evaluation is desirable in many physical design scenarios. To this end, we present FastPass, a fast and robust pin access analysis framework, which first generates design rule checking (DRC)-clean pin access route candidates for each pin, pre-computes incompatible pairs of routes, and then uses incremental SAT solving to find an optimized pin access scheme. Experimental results on the ISPD 2018 benchmarks show that FastPass produces DRC-clean pin access schemes for all cases while being 14.7× faster than the known best pin access analysis framework on average.

Original language	English
Title of host publication	ISPD 2023 - Proceedings of the 2023 International Symposium on Physical Design
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Pages	9-16
Number of pages	8
ISBN (Electronic)	9781450399784
DOIs	https://doi.org/10.1145/3569052.3571879
Publication status	Published - 26 Mar 2023
Event	32nd ACM International Symposium on Physical Design - Virtual, Online, United States Duration: 26 Mar 2023 → 29 Mar 2023 https://dl.acm.org/doi/proceedings/10.1145/3569052 (Conference proceeding)

Publication series

Name	Proceedings of the International Symposium on Physical Design

Conference

Conference	32nd ACM International Symposium on Physical Design
Abbreviated title	ISPD 2023
Country/Territory	United States
Period	26/03/23 → 29/03/23
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3569052 (Conference proceeding)

UN SDGs

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

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

Boolean satisfiability
Detailed routing
Physical design
Pin access

Access to Document

10.1145/3569052.3571879

Cite this

@inproceedings{fb7cb29c56b1471cb56054394573420e,

title = "FastPass: Fast Pin Access Analysis with Incremental SAT Solving",

abstract = "Pin access analysis is a critical step in detailed routing. With complicated design rules and pin shapes, efficient and accurate pin accessibility evaluation is desirable in many physical design scenarios. To this end, we present FastPass, a fast and robust pin access analysis framework, which first generates design rule checking (DRC)-clean pin access route candidates for each pin, pre-computes incompatible pairs of routes, and then uses incremental SAT solving to find an optimized pin access scheme. Experimental results on the ISPD 2018 benchmarks show that FastPass produces DRC-clean pin access schemes for all cases while being 14.7× faster than the known best pin access analysis framework on average.",

keywords = "Boolean satisfiability, Detailed routing, Physical design, Pin access",

author = "Fangzhou Wang and 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. CUHK 14209320). Publisher Copyright: {\textcopyright} 2023 ACM.; 32nd ACM International Symposium on Physical Design, ISPD 2023 ; Conference date: 26-03-2023 Through 29-03-2023",

year = "2023",

month = mar,

day = "26",

doi = "10.1145/3569052.3571879",

language = "English",

series = "Proceedings of the International Symposium on Physical Design",

publisher = "Association for Computing Machinery (ACM)",

pages = "9--16",

booktitle = "ISPD 2023 - Proceedings of the 2023 International Symposium on Physical Design",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/3569052",

}

Wang, F, Liu, J & Young, EFY 2023, FastPass: Fast Pin Access Analysis with Incremental SAT Solving. in ISPD 2023 - Proceedings of the 2023 International Symposium on Physical Design. Proceedings of the International Symposium on Physical Design, Association for Computing Machinery (ACM), New York, pp. 9-16, 32nd ACM International Symposium on Physical Design, United States, 26/03/23. https://doi.org/10.1145/3569052.3571879

FastPass: Fast Pin Access Analysis with Incremental SAT Solving. / Wang, Fangzhou; Liu, Jinwei; Young, Evangeline F.Y.
ISPD 2023 - Proceedings of the 2023 International Symposium on Physical Design. New York: Association for Computing Machinery (ACM), 2023. p. 9-16 (Proceedings of the International Symposium on Physical Design).

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

TY - GEN

T1 - FastPass

T2 - 32nd ACM International Symposium on Physical Design

AU - Wang, Fangzhou

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. CUHK 14209320). Publisher Copyright: © 2023 ACM.

PY - 2023/3/26

Y1 - 2023/3/26

N2 - Pin access analysis is a critical step in detailed routing. With complicated design rules and pin shapes, efficient and accurate pin accessibility evaluation is desirable in many physical design scenarios. To this end, we present FastPass, a fast and robust pin access analysis framework, which first generates design rule checking (DRC)-clean pin access route candidates for each pin, pre-computes incompatible pairs of routes, and then uses incremental SAT solving to find an optimized pin access scheme. Experimental results on the ISPD 2018 benchmarks show that FastPass produces DRC-clean pin access schemes for all cases while being 14.7× faster than the known best pin access analysis framework on average.

AB - Pin access analysis is a critical step in detailed routing. With complicated design rules and pin shapes, efficient and accurate pin accessibility evaluation is desirable in many physical design scenarios. To this end, we present FastPass, a fast and robust pin access analysis framework, which first generates design rule checking (DRC)-clean pin access route candidates for each pin, pre-computes incompatible pairs of routes, and then uses incremental SAT solving to find an optimized pin access scheme. Experimental results on the ISPD 2018 benchmarks show that FastPass produces DRC-clean pin access schemes for all cases while being 14.7× faster than the known best pin access analysis framework on average.

KW - Boolean satisfiability

KW - Detailed routing

KW - Physical design

KW - Pin access

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

UR - https://dl.acm.org/doi/proceedings/10.1145/3569052

U2 - 10.1145/3569052.3571879

DO - 10.1145/3569052.3571879

M3 - Conference proceeding

AN - SCOPUS:85151551047

T3 - Proceedings of the International Symposium on Physical Design

SP - 9

EP - 16

BT - ISPD 2023 - Proceedings of the 2023 International Symposium on Physical Design

PB - Association for Computing Machinery (ACM)

CY - New York

Y2 - 26 March 2023 through 29 March 2023

ER -

FastPass: Fast Pin Access Analysis with Incremental SAT Solving

Abstract

Publication series

Conference

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this