US 7,681,158 B2Granted

Delay budget allocation with path trimming

AssigneesKabushiki Kaisha Toshiba, International Business Machines Corporation

InventorsTaku Uchino, Alvan Ng

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and methods for determining delay budget allocations for circuit elements. One embodiment comprises a method including defining timing edges and corresponding timing paths in an integrated circuit design, and determining delay budget allocations for each of the edges based on required arrival time and design slack (S,T) pairs associated with the different timing paths. The required arrival time is a maximum time when associated with forward paths, and a minimum time when associated with backward paths. (S,T) pairs associated with some timing paths are discarded (i.e., the corresponding timing paths are trimmed) to reduce the complexity of the delay budget allocation computations. Remaining (S,T) pairs are used to determine scaling factors for significant timing paths through the edges. The smallest of the scaling factors for each edge can be multiplied by an initial delay associated with the edge to produce a delay budget allocation associated with the edge.

Claims16

Dependent claims

A computer-implemented method for determining delay budget allocations for edges in an integrated circuit, the method performed by a computer and comprising:

defining timing edges and corresponding timing paths in an integrated circuit design;
and for one or more of the edges,
determining a set of minimum/maximum arrival time and design slack (S,T) pairs characterizing timing paths beginning or ending at the edge,
trimming one or more of the timing paths based on the associated (S,T) pairs,
determining a scaling factor associated with the edge based on the (S,T) pairs associated with untrimmed timing paths,
multiplying the scaling factor associated with the edge by an initial delay associated with the edge to produce a delay budget allocation associated with the edge,
for each of a plurality of nodes adjacent to the edges of the integrated circuit, the computer determining a set of (S,T) pairs associated with the node, wherein determining the set of (S,T) pairs associated with each node in a backward timing path comprises:
for a first node in the backward timing path, setting S equal to an arrival time defined for the first node, and setting T equal to 0;
and
for one or more following nodes in the backward timing path, setting S equal to the S of a preceding node plus a minimum delay of an intervening edge, and setting T equal to the T of the preceding node plus a current delay of the intervening edge minus the minimum delay of the intervening edge.

7 more elements

A software program product comprising:

a computer-readable medium containing one or more program instructions, wherein the instructions are configured to cause a computer to perform the method including the steps of
reading data defining timing edges and corresponding timing paths in an integrated circuit design;
and
for one or more of the edges,
determining a set of minimum/maximum arrival time and design slack (S,T) pairs characterizing timing paths beginning or ending at the edge,
trimming one or more of the timing paths based on the associated (S,T) pairs,
determining a scaling factor associated with the edge based on the (S,T) pairs associated with untrimmed timing paths,
multiplying the scaling factor associated with the edge by an initial delay associated with the edge to produce a delay budget allocation associated with the edge, and
storing the delay budget allocation,
wherein determining the set of (S,T) pairs associated with each node in a backward timing path comprises:
for a first node in the backward timing path, setting S equal to an arrival time defined for the first node, and setting T equal to 0;
and
for one or more following nodes in the backward timing path, setting S equal to the S of a preceding node plus a minimum delay of an intervening edge, and setting T equal to the T of the preceding node plus a current delay of the intervening edge minus the minimum delay of the intervening edge.

10 more elements

Dependencies are inferred from the claim text.