NDLI: Fixed points for multi-cycle path detection

Content Provider	IEEE Xplore Digital Library
Author	D'Silva, V. Kroening, D.
Copyright Year	2009
Description	Author affiliation: Computing Laboratory, Oxford University, U.K. (D'Silva, V.; Kroening, D.)
Abstract	Accurate timing analysis is crucial for obtaining the optimal clock frequency, and for other design stages such as power analysis. Most methods for estimating propagation delay identify multi-cycle paths (MCPs), which allow timing to be relaxed, but ignore the set of reachable states, achieving scalability at the cost of a severe lack of precision. Even simple circuits contain paths affecting timing that can only be detected if the set of reachable states is considered. We examine the theoretical foundations of MCP identification and characterise the MCPs in a circuit by a fixed point equation. The optimal solution to this equation can be computed iteratively and yields the largest set of MCPs in a circuit. Further, we define conservative approximations of this set, show how different MCP identification methods in the literature compare in terms of precision, and show one method to be unsound. The practical application of these results is a new method to detect multi-cycle paths using techniques for computing invariants in a circuit. Our implementation performs well on several benchmarks, including an exponential improvement on circuits analysed in the literature.
Starting Page	1710
Ending Page	1715
File Size	206812
Page Count	6
File Format	PDF
ISBN	9781424437818
ISSN	15301591
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-04-20
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	European Design Automation Association (EDAA)
Subject Keyword	Circuits Timing Equations Clocks Frequency Delay estimation State estimation Propagation delay Scalability Costs
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multi-clock path analysis using propositional satisfiability

Fixed points for multi-cycle path detection

Waiting false path analysis of sequential logic circuits for performance optimization

Efficient timing analysis using constraint-guided critical path search

Discrete-state analysis technique for accurate estimation of switching activities in embedded CMOS combinational circuits

Using VHDL Simulator to Estimate Logic Path Delays in Combinational and Embedded Sequential Circuits

Timing verification of NMOS logic circuits

Path sensitization in critical path problem

On Multiple Path Propagating Tests for Path Delay Faults

Fixed points for multi-cycle path detection

Similar Documents

Multi-clock path analysis using propositional satisfiability

Fixed points for multi-cycle path detection

Waiting false path analysis of sequential logic circuits for performance optimization

Efficient timing analysis using constraint-guided critical path search

Discrete-state analysis technique for accurate estimation of switching activities in embedded CMOS combinational circuits

Using VHDL Simulator to Estimate Logic Path Delays in Combinational and Embedded Sequential Circuits

Timing verification of NMOS logic circuits

Path sensitization in critical path problem

On Multiple Path Propagating Tests for Path Delay Faults

Fixed points for multi-cycle path detection