CRITICAL PATHS IN CIRCUITS WITH LEVEL-SENSITIVE LATCHES

This paper extends the classical notion of critical paths in combinati onal circuits to the case of synchronous circuits that use level-sensi tive latches. Critical paths in such circuits arise from setup, hold, and cyclic constraints on the data signals at the inputs of each latch and may extend through one or more latches. Two approaches are presen ted for identifying these critical paths and verifying their timing. T he first implicitly checks all paths using a relaxation-based solution procedure. Results of this procedure are used to calculate slack valu es, which in turn identify satisfied and violated critical paths. The second approach is based on a constructive algorithm which generates a ll the critical paths in a circuit and then verifies that their timing constraints are satisfied. Algorithms are evaluated and compared usin g circuits from the ISCAS89 sequential benchmark suite and the Michiga n High Performance Microprocessor Project.