An efficient critical path generation algorithm considering extensive path constraints

Guannan Guo; Tsung-Wei Huang; Chun-Xun Lin; Martin Wong

doi:10.1109/DAC18072.2020.9218750

An efficient critical path generation algorithm considering extensive path constraints

Guannan Guo^*
, Tsung-Wei Huang
, Chun-Xun Lin
, Martin Wong

^*Corresponding author for this work

Office of the Provost

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

19 Citations (Scopus)

Abstract

In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

Original language	English
Title of host publication	57th ACM/IEEE Design Automation Conference - Proceedings 2020
Publisher	IEEE
Number of pages	6
ISBN (Electronic)	9781450367257, 9781728110851
ISBN (Print)	9781728158020
DOIs	https://doi.org/10.1109/DAC18072.2020.9218750
Publication status	Published - 20 Jul 2020
Event	57th ACM/IEEE Design Automation Conference, DAC 2020 - Virtual, San Francisco, United States Duration: 20 Jul 2020 → 24 Jul 2020 https://www.dac.com/About/Conference-Archive/57th-DAC-2020 (Conference website ) https://ieeexplore.ieee.org/xpl/conhome/9211868/proceeding (Conference proceedings ) https://dl.acm.org/doi/proceedings/10.5555/3437539 (Conference proceedings)

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings 2020
Volume	2020-July
ISSN (Print)	0738-100X

Conference

Conference	57th ACM/IEEE Design Automation Conference, DAC 2020
Country/Territory	United States
City	San Francisco
Period	20/07/20 → 24/07/20
Internet address	https://www.dac.com/About/Conference-Archive/57th-DAC-2020 (Conference website ) https://ieeexplore.ieee.org/xpl/conhome/9211868/proceeding (Conference proceedings ) https://dl.acm.org/doi/proceedings/10.5555/3437539 (Conference proceedings)

Access to Document

10.1109/DAC18072.2020.9218750

Cite this

@inproceedings{a1681a7b2ea642d6b18e7116f88fe5ea,

title = "An efficient critical path generation algorithm considering extensive path constraints",

abstract = "In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.",

author = "Guannan Guo and Tsung-Wei Huang and Chun-Xun Lin and Martin Wong",

note = "Funding Information: VII. ACKNOWLEDGEMENT This work is partially supported by NSF Grant CCF-1718883. Publisher Copyright: {\textcopyright} 2020 IEEE.; 57th ACM/IEEE Design Automation Conference, DAC 2020 ; Conference date: 20-07-2020 Through 24-07-2020",

year = "2020",

month = jul,

day = "20",

doi = "10.1109/DAC18072.2020.9218750",

language = "English",

isbn = "9781728158020",

series = "ACM/IEEE Design Automation Conference - Proceedings 2020",

publisher = "IEEE",

booktitle = "57th ACM/IEEE Design Automation Conference - Proceedings 2020",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/57th-DAC-2020, https://ieeexplore.ieee.org/xpl/conhome/9211868/proceeding, https://dl.acm.org/doi/proceedings/10.5555/3437539",

}

Guo, G, Huang, T-W, Lin, C-X & Wong, M 2020, An efficient critical path generation algorithm considering extensive path constraints. in 57th ACM/IEEE Design Automation Conference - Proceedings 2020., 9218750, ACM/IEEE Design Automation Conference - Proceedings 2020, vol. 2020-July, IEEE, 57th ACM/IEEE Design Automation Conference, DAC 2020, San Francisco, United States, 20/07/20. https://doi.org/10.1109/DAC18072.2020.9218750

An efficient critical path generation algorithm considering extensive path constraints. / Guo, Guannan; Huang, Tsung-Wei; Lin, Chun-Xun et al.
57th ACM/IEEE Design Automation Conference - Proceedings 2020. IEEE, 2020. 9218750 (ACM/IEEE Design Automation Conference - Proceedings 2020; Vol. 2020-July).

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

TY - GEN

T1 - An efficient critical path generation algorithm considering extensive path constraints

AU - Guo, Guannan

AU - Huang, Tsung-Wei

AU - Lin, Chun-Xun

AU - Wong, Martin

PY - 2020/7/20

Y1 - 2020/7/20

N2 - In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

AB - In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

UR - https://dl.acm.org/doi/10.5555/3437539.3437767

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

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

U2 - 10.1109/DAC18072.2020.9218750

DO - 10.1109/DAC18072.2020.9218750

M3 - Conference proceeding

AN - SCOPUS:85093981735

SN - 9781728158020

T3 - ACM/IEEE Design Automation Conference - Proceedings 2020

BT - 57th ACM/IEEE Design Automation Conference - Proceedings 2020

PB - IEEE

T2 - 57th ACM/IEEE Design Automation Conference, DAC 2020

Y2 - 20 July 2020 through 24 July 2020

ER -

An efficient critical path generation algorithm considering extensive path constraints

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this