More Web Proxy on the site http://driver.im/

research-article

Event propagation for accurate circuit delay calculation using SAT

Authors:

Suchismita Roy,

P. P. Chakrabarti,

Pallab DasguptaAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 12, Issue 3

Article No.: 36, Pages 1 - 23

https://doi.org/10.1145/1255456.1255473

Published: 22 May 2008 Publication History

Abstract

A SAT-based modeling for event propagation in gate-level digital circuits, which is used for accurate calculation of critical delay in combinational and sequential circuits, is presented in this article. The accuracy of the critical delay estimation process depends on the accuracy with which the circuit in operation is modeled. A high level of precision in the modeling of the internal events in a circuit for the sake of greater accuracy causes a combinatorial blowup in the size of the problem, resulting in a scalability bottleneck for which most existing techniques effect a trade-off by restricting themselves to less precise models. SAT based techniques have a good track record in efficiency and scalability when the problem sizes become too large for most other methods. This article proposes a SAT-based technique for symbolic event propagation within a circuit which facilitates the estimation of the critical delay of circuits with a greater degree of accuracy, while at the same time scaling efficiently to large circuits. We report very encouraging results on the ISCAS85 and ISCAS89 benchmark circuits using the proposed technique.

References

[1]

Bell, J. L., Whittlemore, J. P., and Sakallah, K. A. 1998. False path analysis in sequential circuits. In Proceedings of 8th International Workshop on Power and Timing Modeling, Optimization and Simulation. 245--254.

[2]

Benkoski, J., Meersch, E. V., Claesen, L. J. M., and DeMan, H. 1990. Timing verification using statically sensitizable paths. IEEE Trans. Comput. Aid. Design 9, 1073--1084.

Digital Library

[3]

Chen, H. C. and Du, D. H. C. 1993. Path sensitization in critical path problem. IEEE Trans. Comput. Aid. Design Integr. Circuits Syst. 2 (Feb.), 196--207.

Digital Library

[4]

Clarke, E. M., Grumberg, J. O., and Peled, D. A. 2001. Model Checking. The MIT Press.

[5]

Devadas, S., Keutzer, K., Malik, S., and Wang, A. 1992. Certified timing verification and the transition delay of a logic circuit. In Proceedings of the 29th ACM/IEEE Design Automatiom Conference. 549--555.

Digital Library

[6]

Fu, Z., Mahajan, Y., and Malik, S. zchaff solver. http://www.princeton.edu/~zchaff/zchaff.html.

[7]

Goldberg, E. and Nonikov, Y. 2002. Berkmin: A fast and robust sat solver. In Proceedings of the Conference on Design Automation and Test in Europe (DATE'02). Paris, France. 142--149.

Digital Library

[8]

Guerra eSilva, L., Marques-Silva, J., Silviera, L. M., and Sakallah, K. A. 2002. Satisfiability models and algorithms for circuit delay computations. ACM Trans. Design Autom. Electr. Syst. 7, 1 (Jan.), 137--158.

Digital Library

[9]

Jin, H., Awedh, M., and Somenzi, F. 2004. Circus: A satisfiability solver geared towards bounded model checking. In Proceedings of the 16th Conference on Computer Aided Design.

[10]

Keutzer, K., Malik, S., and Saldanha, A. 1991. Is redundancy necessary to reduce delay? IEEE Trans. Comput. Aid. Design 10, 427--435.

[11]

Lam, W. K. C., Brayton, R. K., and Sangiovanni-Vincentelli, A. L. 1993. Circuit delay models and their exact computation using timed boolean functions. In Proceedings of the 30th ACM/IEEE Design Automation Conference. 128--134.

Digital Library

[12]

Lam, W. K. C., Brayton, R. K., and Sangiovanni-Vincentelli, A. L. 1994. Exact minimum cycle times for finite state machines. In Proceedings of the 31st ACM/IEEE Design Automation Conference. 100--105.

Digital Library

[13]

Larrabee, T. 1992. Test pattern generation using boolean satisfiability. IEEE Trans. Comput. Aid. Design Integr. Circuits Syst. 11, 2 (Jan.), 4--15.

[14]

McGeer, P. C. 1989. On the interaction of functional and timing behaviour of combinational logic circuits. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA.

Digital Library

[15]

McGeer, P. C. and Brayton, R. K. 1989. Efficient algorithms for computing the longest viable path in a combinational network. In Proceedings of 26th ACM/IEEE Design Automation Conference. 561--567.

Digital Library

[16]

McGeer, P. C., Saldanha, A., Brayton, R. K., and Sangiovanni-Vincentelli, A. L. 1993. Logic Synthesis and Optimization. (Chapter Delay Models and Exact Timing Analysis, 167--189) Kluwer Academic Publishers.

[17]

Mondal, A. and Chakrabarti, P. P. 2006. Reasoning about timing behavior of digital circuits using symbolic event propagation and temporal logic. IEEE Trans. Comput. Aid. Design Integr. Circuits Syst. To appear.

Digital Library

[18]

Yalcin, H. and Hayes, J. P. 1997. Event propagation condition in circuit delay computation. ACM Trans. Design Autom. Electr. Syst. 2, 3 (July), 249--280.

Digital Library

Cited By

Kundu SRoy SMukherjee S(2021)An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SATIETE Journal of Research10.1080/03772063.2021.196779069:6(3346-3356)Online publication date: 1-Sep-2021
https://doi.org/10.1080/03772063.2021.1967790
He ZLv TLi HLi X(2013)Test Path Selection for Capturing Delay Failures Under Statistical Timing ModelIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.220866121:7(1210-1219)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1109/TVLSI.2012.2208661
Chung YJiang J(2013)Functional Timing Analysis Made Fast and GeneralIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.225646132:9(1421-1434)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TCAD.2013.2256461
Show More Cited By

Index Terms

Event propagation for accurate circuit delay calculation using SAT
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

Event propagation conditions in circuit delay computation

Accurate and efficient computation of delays is a central problem in computer-aided design of complex VLSI circuits. Delays are determined by events (signal transitions) propagated from the inputs of a circuit to its outputs, so precise characterization ...
Design of Low-Power 10-Transistor Full Adder Using GDI Technique for Energy-Efficient Arithmetic Applications
Abstract
The general focus of this work is to design an area-optimised full adder and utilise it to lay out a low-power arithmetic unit that can be helpful for microprocessors. A traditional full adder with 28 transistors has been devised with 10 ...
Bounded delay timing analysis and power estimation using SAT

This paper presents a satisfiability based approach that can be used for accurate estimation of both the critical delay and dynamic transition power consumption of circuits using an event propagation model. The accuracy of the model depends on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 12, Issue 3

August 2007

427 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1255456

Issue’s Table of Contents

Copyright © 2008 ACM.

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 22 May 2008

Accepted: 01 February 2007

Revised: 01 October 2006

Received: 01 April 2006

Published in TODAES Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kundu SRoy SMukherjee S(2021)An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SATIETE Journal of Research10.1080/03772063.2021.196779069:6(3346-3356)Online publication date: 1-Sep-2021
https://doi.org/10.1080/03772063.2021.1967790
He ZLv TLi HLi X(2013)Test Path Selection for Capturing Delay Failures Under Statistical Timing ModelIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.220866121:7(1210-1219)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1109/TVLSI.2012.2208661
Chung YJiang J(2013)Functional Timing Analysis Made Fast and GeneralIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.225646132:9(1421-1434)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TCAD.2013.2256461
Shao SLuo GLuo JZhao X(2013)Circuit delay computation based on ITTPN2013 IEEE 12th International Conference on Cognitive Informatics and Cognitive Computing10.1109/ICCI-CC.2013.6622282(454-460)Online publication date: Jul-2013
https://doi.org/10.1109/ICCI-CC.2013.6622282
Mondal AChakrabarti PDasgupta P(2012)Symbolic-Event-Propagation-Based Minimal Test Set Generation for Robust Path Delay FaultsACM Transactions on Design Automation of Electronic Systems10.1145/2348839.234885117:4(1-20)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1145/2348839.2348851
Chung YJiang JGroeneveld PSciuto DHassoun S(2012)Functional timing analysis made fast and generalProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228552(1055-1060)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228552
Tadesse DBahar RGrodstein J(2011)Test Vector Generation for Post-Silicon Delay Testing Using SAT-Based Decision ProblemsJournal of Electronic Testing: Theory and Applications10.1007/s10836-011-5205-z27:2(123-136)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1007/s10836-011-5205-z
Mondal AChakrabarti PDasgupta P(2010)Accelerating Synchronous Sequential Circuits Using an Adaptive ClockProceedings of the 2010 23rd International Conference on VLSI Design10.1109/VLSI.Design.2010.40(176-181)Online publication date: 3-Jan-2010
https://dl.acm.org/doi/10.1109/VLSI.Design.2010.40
He ZLv TLi HLi X(2010)An Efficient Algorithm for Finding a Universal Set of Testable Long PathsProceedings of the 2010 19th IEEE Asian Test Symposium10.1109/ATS.2010.61(319-324)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/ATS.2010.61
Roy SChakrabarti PDasgupta P(2010)Bounded delay timing analysis and power estimation using SATMicroelectronics Journal10.1016/j.mejo.2010.04.00141:5(317-324)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1016/j.mejo.2010.04.001
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents