Verifying clock schedules
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Timing verification and optimization have been formulated as mathematical programming problems. The computational aspects of using such a formulation for verifying clock schedules are considered. The formulation can have multiple solutions, and these extraneous solutions can cause previously published algorithms to produce incorrect or misleading results. The conditions under which multiple solutions exist are characterized, and it is shown that even when the solution is unique, the running times of these previous algorithms can be unbounded. By contrast, a simple polynomial time algorithm for clock schedule verification is exhibited. The algorithm was implemented and used to check the timing of all the circuits in the ISCAS-89 benchmark suite. Observed running times are linear in circuit size and quite practical.<>Keywords
This publication has 3 references indexed in Scilit:
- Computing optimal clock schedulesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- CheckT/sub c/ and minT/sub c/: timing verification and optimal clocking of synchronous digital circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Analysis and design of latch-controlled synchronous digital circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992