US 7,010,767 B2Granted

Insertion of repeaters without timing constraints

AssigneeCadence Design Systems, Inc.

InventorsShauki Elassaad, Alexander Saldanha

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method/process for repeater insertion in the absence of timing constraints. Delays are optimized for multi-receiver and multi-layer nets and can be introduced in the early steps of design planning. It serves as a tool for interconnect prediction as well as planning. In the presented formulation, no restrictions are made on where the repeaters are added or what the topology of the net is. The tabulated results demonstrate improvement (speed ups) using the method/process of the present invention. The present invention runs in linear time and achieves better results that the existing dynamic programming formulation and other published heuristics. Polarity in a circuit design is corrected by traversing the circuit and carrying backwards a cost of fixing the polarity. On a subsequent traversal, buffers inserted fix the polarity.

Claims23

Dependent claims

A method of inserting buffers in a circuit design, comprising the steps of:

preparing a physical hierarchy of the circuit design with placed macros;
performing global routing on the physical hierarchy;
determining a number of buffers to be inserted on each edge of nets of the global routing for boosting timing performance of the nets;
calculating a position for each buffer;
and
inserting a buffer configured to boost timing performance at each calculated position;
wherein:
said step of determining a number of buffers comprises the steps of:
identifying a set of at least one edge in said nets for inserting buffers;
and
determining an optimal number of buffers to be inserted on each edge said step of determining an optimal number of buffers comprises the step of, calculating, for each edge, the optimal number of buffers based on an optimal timing for the edge, a delay of the edge, and an impedance of the edge;
and
said step of calculating the optimal number of buffers comprises calculating
C
x
i
=
T
opt
-
D
i
-
1
-
(
R
eq
i
+
1
2
⁢
R
i
)
⁢
C
i
(
R
eq
i
+
R
i
)
⁢
f
i
;
where Cxi is a capacitance contribution of a branch of a merged segment on an edge as seen by a driving node of the segment;
Topt is the delay of an optimal stage;
Di is delay of the edge;
Reqi is an equivalent resistance of the merged segment;
fi is fanout of the branch;
Ri is a resistance of the edge;
and
Ci is a capacitance of the edge.

56 more elements

A method of inserting buffers in a circuit design, comprising the steps of:

preparing a physical hierarchy of the circuit design with placed macros;
performing global routing on the physical hierarchy;
determining a number of buffers to be inserted on each edge of nets of the global routing for boosting timing performance of the nets;
calculating a position for each buffer;
inserting a buffer configured to boost timing performance at each calculated position;
uniformly distributing a capacitance of each branch of the nets at a corresponding branch point;
determining a load at each branch point;
and
checking if a buffer inserted at each branch point is capable of handling the load determined for that branch point;
wherein said steps of determining a number of buffers and calculating a position for each buffer comprise:
identifying a driver of a net to have buffers inserted;
performing a breadth first search (BFS) of the net starting at the identified net driver and processing all connected edges;
performing a depth first search (DFS) starting at a next stage in the net;
and
for each edge, determining a number of buffers to be inserted on each edge of nets of the global routing for boosting timing performance of the nets, and calculating a position for each buffer.

12 more elements

A method of inserting buffers in a circuit design, comprising the steps of:

preparing a physical hierarchy of the circuit design with placed macros;
performing global routing on the physical hierarchy;
determining a number of buffers to be inserted on each edge of nets of the global routing for boosting timing performance of the nets;
calculating a position for each buffer;
inserting a buffer configured to boost timing performance at each calculated position;
uniformly distributing a capacitance of each branch of the nets at a corresponding branch point;
determining a load at each branch point;
and
checking if a buffer inserted at each branch point is capable of handling the load determined for that branch point;
wherein said steps of determining a number of buffers and calculating a position of each buffer comprises:
identifying a driver of a net to have buffers inserted;
performing a breadth first search (BFS) of the net starting at the identified net driver and processing all connected edges;
performing a depth first search (DFS) starting at a next stage in the net;
for each edge, determining a number of buffers to be inserted on each edge of nets of the global routing, wherein the buffers are for boosting timing performance of the nets;
and
calculating a position for each buffer;
wherein the calculated position for each buffer position is based on a combination of stage delay, branch resistance, resistance of merged branch segments, branch capacitance, and branch fanout.

14 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/919,740Filed 1 Aug 2001 · us provisional application
Priority: 1 Nov 2000
Published: US 2004/0257207 A123 Dec 2004
Granted: 7 Mar 2006
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 30/3947
Routing: global
G06F 30/327
Circuit design at the digital level: logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
G06F 30/392
Circuit design at the physical level: floor-planning or layout, e.g. partitioning or placement
G06F 2119/12
Details relating to the type or aim of the analysis or the optimisation: timing analysis or timing optimisation