Accelerating functional timing analysis with encoding duplication removal and redundant state propagation

Denny C.Y. Wu, Pin Ru Jhao, Charles H.P. Wen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Functional timing analysis (FTA) emerges for better timing closure than static timing analysis (STA) by providing the true delay of the circuit as well as its input pattern. For Satisfiability(SAT)-based FTA, a search problem for circuit delay can be expressed by clauses corresponding to circuit consistency function (CCF) and timed characteristic function (TCF). In particular, the clause number tends to grow exponentially as the circuit size increases, lengthening runtime for FTA. However, when formulating TCF, numerous clauses and literals are found useless. Therefore, two key techniques are proposed: (1) Encoding Duplication Removal (EDR) for removing those literals that are previously encoded in CCF but now duplicated in TCF, and (2) Redundant State Propagation (RSP) for propagating redundant states of nodes to help prune TCF clauses. Experiments indicate that under the worst-case delay of each benchmark circuit, EDR and RSP successfully reduce averagely 49% of clauses, 65% of literals, and 52% runtime on seven benchmark circuits for FTA.

Original languageEnglish
Title of host publication2017 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages117-122
Number of pages6
ISBN (Electronic)9781538630938
DOIs
StatePublished - 13 Dec 2017
Event36th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017 - Irvine, United States
Duration: 13 Nov 201716 Nov 2017

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2017-November
ISSN (Print)1092-3152

Conference

Conference36th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
CountryUnited States
CityIrvine
Period13/11/1716/11/17

Fingerprint Dive into the research topics of 'Accelerating functional timing analysis with encoding duplication removal and redundant state propagation'. Together they form a unique fingerprint.

  • Cite this

    Wu, D. C. Y., Jhao, P. R., & Wen, C. H. P. (2017). Accelerating functional timing analysis with encoding duplication removal and redundant state propagation. In 2017 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017 (pp. 117-122). (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; Vol. 2017-November). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCAD.2017.8203768