Article

Free access

Efficient algorithms for computing the longest viable path in a combinational network

Authors:

P. C. McGeer,

R. K. BraytonAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 561 - 567

https://doi.org/10.1145/74382.74476

Published: 01 June 1989 Publication History

PDF eReader

Abstract

We consider the elimination of false paths in combinational circuits. We give the single generic algorithm that is used to solve this problem, and demonstrate that it is parameterized by a Boolean function called the sensitization condition. We give two criteria which we argue that a valid sensitization condition must meet, and introduce four conditions that have appeared in the recent literature, of which two meet the criteria and two do not. We then introduce a dynamic programming procedure for the tightest of these conditions, the viability condition, and discuss the integration of all four sensitization conditions in the LLLAMA timing environment. We give results on the IWLS and ISCAS benchmark examples and on carry-bypass adders.

References

[1]

J. Benkoski, E. Vanden Meesch, L. Claesen, and H. De Man. Efficient Algorithms for Solving the False Path Problem in Timing Verification. In IEEE International Conference on Computer- Aided Design, 1987.

Google Scholar

[2]

Daniel Brand and Vijay S. Iyengar. Timing Anal ysis Using Functional Analysis. Technical Report RC 11768, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 10598, 1986.

Google Scholar

[3]

R. K. Brayton, R. Rudell, A. L. Sagiovanni- Vincentelli, and A. Wang. Mis: a multiple-level logic optimization system. IEEE Teansactions on CAD, 1987.

Digital Library

Google Scholar

[4]

R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 1986.

Digital Library

Google Scholar

[5]

Robert B. Hitchcock. Timing verification and the timing analysis program. In Design Automation Conference, 1982.

Digital Library

Google Scholar

[6]

V. M. Hrapcenko. Depth and delay in a network. Soviet Math. DokL, 1978.

Google Scholar

[7]

N. J ouppi. TV: an nMOS Timing Analyzer. In Third Caltech VLSI Conference, 1983.

Google Scholar

[8]

S. Malik, A. R. Wang, R. K. Brayton, R. Rudell, and A. L. Sagiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In IEEE International Conference on Computer-Aided Design, 1988.

Crossref

Google Scholar

[9]

Patrick C. M cGeer and Robert K. Brayton. Provably Correct Critical Paths. in Decennial Caltech Conference on VLSI, 1989.

Digital Library

Google Scholar

[10]

John K. Ousterhout. Crystal: a Timing Analyzer for nMOS VLSI Circuits. In Third Callech VI, SI Conference, 1983.

Google Scholar

[11]

J. P. Roth. Diagnosis of automata failures: a calculus and a method. IBM J. Res. Develop, 1966.

Google Scholar

Cited By

View all

Wibbels MStevens K(2022)Causal Path Identification for Timed and Sequential CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.306809741:3(571-582)Online publication date: Mar-2022
https://doi.org/10.1109/TCAD.2021.3068097
Abolmaali SKamal MAfzali-Kusha APedram M(2018)An Efficient False Path-Aware Heuristic Critical Path Selection Method with High Coverage of the Process Variation SpaceACM Transactions on Design Automation of Electronic Systems10.1145/317786623:3(1-25)Online publication date: 23-Feb-2018
https://dl.acm.org/doi/10.1145/3177866
Camus VCacciotti MSchlachter JEnz C(2018)Design of Approximate Circuits by Fabrication of False Timing Paths: The Carry Cut-Back AdderIEEE Journal on Emerging and Selected Topics in Circuits and Systems10.1109/JETCAS.2018.28517498:4(746-757)Online publication date: Dec-2018
https://doi.org/10.1109/JETCAS.2018.2851749
Show More Cited By

Index Terms

Efficient algorithms for computing the longest viable path in a combinational network
1. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Combinational circuits
  2. Very large scale integration design

Recommendations

Quaternary CMOS Combinational Logic Circuits
ICIMT '09: Proceedings of the 2009 International Conference on Information and Multimedia Technology

Good Characteristics and advantages of multi-valued logic (MVL) electronic systems and circuits are created great interest for its practical implementation. This paper presents voltage mode quaternary CMOS circuit design using 90nm technology. Basic ...
Efficient reliability evaluation of combinational and sequential logic circuits

Reliability has become one of the major goals for designs based on emerging technologies. Therefore, reliability evaluation should be included in the design flow of logic integrated circuits. In this paper, a probability transfer matrix-based method is ...
An efficient automatic test generation system for path delay faults in combinational circuits
VLSID '95: Proceedings of the 8th International Conference on VLSI Design

The new test pattern generation system for path delay faults in combinational logic circuits considers robust and nonrobust tests, simultaneously. Once a robust test is obtained for a path with a given transition, another test for the same path with the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

156
Total Citations
View Citations
690
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)12

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wibbels MStevens K(2022)Causal Path Identification for Timed and Sequential CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.306809741:3(571-582)Online publication date: Mar-2022
https://doi.org/10.1109/TCAD.2021.3068097
Abolmaali SKamal MAfzali-Kusha APedram M(2018)An Efficient False Path-Aware Heuristic Critical Path Selection Method with High Coverage of the Process Variation SpaceACM Transactions on Design Automation of Electronic Systems10.1145/317786623:3(1-25)Online publication date: 23-Feb-2018
https://dl.acm.org/doi/10.1145/3177866
Camus VCacciotti MSchlachter JEnz C(2018)Design of Approximate Circuits by Fabrication of False Timing Paths: The Carry Cut-Back AdderIEEE Journal on Emerging and Selected Topics in Circuits and Systems10.1109/JETCAS.2018.28517498:4(746-757)Online publication date: Dec-2018
https://doi.org/10.1109/JETCAS.2018.2851749
Sreenath KRamesh S(2018)Statistical Viability Analysis and Optimization Through Gate SizingAdvanced Computational and Communication Paradigms10.1007/978-981-10-8240-5_17(149-155)Online publication date: 8-Jun-2018
https://doi.org/10.1007/978-981-10-8240-5_17
Afonso JMonteiro J(2017)Analysis of short-circuit conditions in logic circuitsProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130577(824-829)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130577
Afonso JMonteiro J(2017)Analysis of short-circuit conditions in logic circuitsDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927102(824-829)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927102
Abolmaali SMansouri-Ghiasi NKamal MAfzali-Kusha APedram M(2017)Efficient Critical Path Identification Based on Viability Analysis Method Considering Process VariationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2017.270362325:9(2668-2672)Online publication date: Sep-2017
https://doi.org/10.1109/TVLSI.2017.2703623
Tsai CWang CHuang CChen YHenkel J(2013)Sensitization criterion for threshold logic circuits and its applicationProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561874(226-233)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561874
Jung JKim T(2013)Statistical Viability Analysis for Detecting False Paths Under Delay VariationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2012.221110232:1(111-123)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1109/TCAD.2012.2211102
Tsai CWang CHuang CChen Y(2013)Sensitization criterion for threshold logic circuits and its application2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2013.6691123(226-233)Online publication date: Nov-2013
https://doi.org/10.1109/ICCAD.2013.6691123
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Quaternary CMOS Combinational Logic Circuits

Efficient reliability evaluation of combinational and sequential logic circuits

An efficient automatic test generation system for path delay faults in combinational circuits