Browse Prior Art Database

Algorithm for Incremental Timing Analysis

IP.com Disclosure Number: IPCOM000114564D
Original Publication Date: 1995-Jan-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 8 page(s) / 365K

Publishing Venue

IBM

Related People

Lee, JF: AUTHOR [+2]

Abstract

Disclosed is an incremental longest path algorithm. When applied to the timing analysis problem after an incremental change in the digital logic network, this algorithm will identify the portion of design for which the timing is affected, and quickly derives the new arrival times and slacks. This fast incremental timing analysis is very desirable for users doing interactive logic design. It is particularly important for a design process in which iterative changes on logic or delay elements are made such as the case of logic synthesis using local transformations lbracket 1 rbracket .

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

Algorithm for Incremental Timing Analysis

      Disclosed is an incremental longest path algorithm.  When
applied to the timing analysis problem after an incremental change in
the digital logic network, this algorithm will identify the portion
of design for which the timing is affected, and quickly derives the
new arrival times and slacks.  This fast incremental timing analysis
is very desirable for users doing interactive logic design.  It is
particularly important for a design process in which iterative
changes on logic or delay elements are made such as the case of logic
synthesis using local transformations lbracket 1 rbracket .

      A digital computer design may be represented as a finite-state
machine, consisting of a combinational logic network, a set of memory
elements (level-sensitive latches or flip-flops) and a set of Primary
Inputs (PIs) and Outputs (POs).  For a pattern-independent timing
analysis lbracket 2 '-' 6 rbracket of such a logic network, it may be
shown that the worst-case late-mode signal arrival times are given by
the longest path in the timing constraint graph G=(V,E), lbracket 2,
6 rbracket which is defined as follows:  Each node in G represents
either a PI, a PO or a pin on the logic gate, while each edge
represents the delay between a pair of pins.  In the general case
where G may contain some feedback loops through latches, a longest
path algorithm typically takes several iterations to converge with a
cost O(m * vbar G vbar ), where m, the number of iterations, is
bounded by the number of latches, lbracket 6 '-' 8 rbracket.

      The logic design is often modified either manually or with an
optimization program to meet some delay or power requirements, using
techniques such as power-up, power-down, or re-synthesis.  Let G
prime  be the timing constraint graph after the modification on some
edge weights.  Let Lambda sub i,j  and Lambda prime sub i,j  be
respectively the delay weight of edge (V sub i , V sub j ) in G, and
G prime .  The difference in the two graphs can be captured by those
edges with weight changed:  G prime - G = lbrace (V sub i, V sub j)
vbar Lambda prime sub i,j ne Lambda sub i,j rbrace.  For an
incremental
change in the logic design involving a small number of edges, it is
very desirable to have a fast method to find out the corresponding
change in the timing.  The use of the traditional longest path
algorithm on the full graph will take computation time proportional
to vbar G prime vbar .  For the design of a VLSI chip with millions
of
transistors, this is too costly for a small incremental change.  In
this paper, we propose an incremental longest path algorithm which is
very efficient, since it generally retains and utilizes the timing
information not affected by the incremental change.

      Let us briefly review the single-source longest path problem
lbracket 6 '-' 8 rbracket . Given a node V sub i , there may be many
paths from the source node V sub 0...