Browse Prior Art Database

# Timing Verification Algorithm for Clock Design with Slack Stealing

IP.com Disclosure Number: IPCOM000106225D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 202K

IBM

## Related People

Lee, JF: AUTHOR [+2]

## Abstract

Disclosed is a new timing analysis method for level-sensitive clock design, which can handle (1) aggressive late-mode slack stealing, and (2) feedback loops among the latches. This is to be implemented in CYCLOPSS, a prototype tool.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 26% of the total text.

Timing Verification Algorithm for Clock Design with Slack Stealing

Disclosed is a new timing analysis method for level-sensitive
clock design, which can handle (1) aggressive late-mode slack
stealing, and (2) feedback loops among the latches.  This is to be
implemented in CYCLOPSS, a prototype tool.

In the digital system, a set of latches are used to synchronize
the signals through different paths of combinational logic network.
The signal delay through some paths of combinational logic may be
longer than one cycle period, so long as it can be compensated by a
shorter delay in the subsequent clock cycles.  This slack (cycle)
stealing technique can be correctly analyzed by considering
multiple-cycle paths in a latch graph lbracket 1 '-' 3 rbracket .
Latch graph is a directed graph LG=(L,LE) in which nodes L = lbrace L
sub 1 , L sub 2 ...  rbrace represent a set of latches, primary
inputs (PI) and primary outputs (PO), while arcs represent the
early/late mode timing constraints between them.  Since the
early-mode slack stealing is normally not allowed, let us consider
the late-mode analysis on the latch graph.

1.  Each arc (L sub i ,L sub j ) is associated with two numbers:  the
latch-to-latch long path delay d sub ij  and the cycle adjustment
p sub ij  ( the signal arrived at the latch L sub j %% p sub ij
cycles later).

2.  Each latch node i is associated with three parameters:  the
triggering time phi sub i , the propagation delay from the latch
input to output delta sub i , and the setup time s sub i .
3.  Each PI node is associated with a signal arrival time A sub i ,
while each PO node is associated with a signal required arrival
time RA sub i .

Let A sub i  and D sub i  represent the latest signal arrival and
departure time at node L sub i :

< A sub j = max  midsub  <(i,j) memberof 'LE' >
(D sub i + d sub ij - p sub ij ) ; %%%%
D sub j = max  (A sub j + delta sub j , phi sub j )
%%%% ' for latches' >
lvabove < D sub j = A sub j %%%% ' for PI' >

Then the arrival times need to satisfy

< A sub j le s sub j  %%%%%%%% ' : set-up constraints for latches
' >
lvabove < A sub j le RA sub j %%%%
' : the required arrival time for PO' >

An example of latch graph is shown in Fig. 1a.

The multiple-cycle timing analysis problem can be transformed
into a longest path problem by generating a latch timing graph
G=(V,E) from the latch graph as follows:

1.  Create a source node V sub 1 to represent the origin of the
clock.

2.  For each latch i, create two nodes: V sub 2i  representing the
arrival time and V sub 2i+1  representing departure time.

a.  Draw an arc from the arrival node to the departure node with
...