Method and apparatus for performing buffer insertion with accurate gate and interconnect delay computation

• US 6,347,393 B1
• Filed: 05/24/1999
• Issued: 02/12/2002
• Est. Priority Date: 05/24/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Devgan, Anirudh, Quay, Stephen Thomas, Alpert, Charles Jay
• Primary Examiner(s): Nelms, David
• Assistant Examiner(s): LE, THONG QUOC
• Application Number:
  US09/317,553
• Time in Patent Office: 995 Days
• Field of Search: 716/2, 716/8, 716/17, 364/488
• US Class Current: 716/114
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

Abstract

An optimal buffer is chosen for insertion at a node by calculating a π-model of a downstream circuit to a child node where the π-model contains at least a capacitance value. The gate delay is computed at the node using an effective capacitance derived from the π-model and buffer characteristics of a particular buffer. The interconnect delay is then computed from sets of moments associated with each gate downstream from the node via a bottom-up incremental technique. Slack is computed using the gate delay for the child node and the interconnect delay for the child node and then the computed slack is compared to the slack of other buffers at the node. The node may be a sink or have one or two children.

Claims

1. A method implemented in a data processing system for optimizing buffer insertion with accurate gate and interconnect delay computations at a node in a circuit, the method comprising:

selecting a first buffer from a plurality of buffers, each buffer in the plurality of buffers having unique buffer characteristics;

calculating a π

-model of a downstream circuit to a child node;

calculating an effective capacitance for the child node using the π

-model and the buffer characteristics of the selected first buffer;

calculating a gate delay for the child node using the effective capacitance of the child node;

calculating an interconnect delay for the child node using sets of moments associated with gates downstream from the child node;

calculating slack at the child node for the selected first buffer using the gate delay for the child node and the interconnect delay for the child node;

comparing the slack for the selected buffer with slack for at least one other buffer in the plurality of buffers;

determining an optimal buffer at the child node based on comparing slacks; and

inserting the optimal buffer at the child node.

2. The method recited in claim 1 further comprising:

calculating a set of moments associated with a parent node using the sets of moments associated with gates downstream from the child node and the set of moments associated with a wire connected from the child node to the parent node; and

calculating slack for the wire at the parent node using the set of moments associated with the parent node.

3. The method recited in claim 2 further comprising:

selecting a second buffer from a plurality of buffers, each buffer in the plurality of buffers having unique buffer characteristics;

calculating a π

-model of a downstream circuit to the parent node;

calculating an effective capacitance for the parent node using the π

-model and the buffer characteristics of the selected second buffer;

calculating a gate delay for the parent node using the effective capacitance of the parent node;

calculating an interconnect delay for the parent node using sets of moments associated with each gate downstream from the parent node;

calculating slack at the parent node for the selected second buffer using the gate delay for the parent node and the interconnect delay for the parent node;

comparing the slack for the selected second buffer with slack for at least one other buffer in the plurality of buffers; and

determining an optimal buffer at the parent node based on comparing slacks.

4. The method recited in claim 1, wherein the π

-model comprises at least one non-negative capacitance value.

5. The method recited in claim 1, wherein the π

-model is represented by two capacitance values and one resistance value.

6. The method recited in claim 1, wherein each set of moments associated with each gate comprises a set of three moments for each gate, the three moments being the first three moments associated with each gate.

7. The method recited in claim 1, wherein the step of calculating a gate delay for the child node uses a curve-fitted equation.

8. The method recited in claim 1, wherein the child node is one of a sink, a child case, and a two children case.

9. The method recited in claim 1, wherein the child node has a first child and a second child and wherein the π

-model is the first π

-model, the effective capacitance is the first effective capacitance, the gate delay is the first gate delay, the interconnect delay is the first interconnect delay, the sets of moments are first sets of moments, and the slack is the first slack, the method further comprising;

calculating a second effective capacitance for the child node using a second π

-model and the buffer characteristics of the selected buffer;

calculating a second gate delay for the parent node using a second effective capacitance of the child node;

calculating a second interconnect delay for the child node using second sets of moments associated with gates downstream from the child node;

calculating a second slack at the child node for the selected buffer using the second gate delay for the child node and the second interconnect delay for the child node; and

comparing the second slack for the second child for the selected buffer with either slack for at least one other buffer in the plurality of buffers or the first slack.

10. The method recited in claim 1 further comprises:

storing the calculating π

-model for the parent node;

storing the slack for the parent node; and

storing the set of moments associated with the parent node.

15. The system recited in claim 1, wherein the π

-model is represented by two capacitance values and one resistance value.

11. A data processing system for optimizing buffer insertion with accurate gate and interconnect delay computations at a node in a circuit, the system comprising:

selecting means for selecting a first buffer from a plurality of buffers, each buffer in the plurality of buffers having unique buffer characteristics;

calculating means for calculating a π

-model of a downstream circuit to a child node;

calculating means for calculating an effective capacitance for the child node using the π

-model and the buffer characteristics of the selected first buffer;

calculating means for calculating a gate delay for the child node using the effective capacitance of the child node;

calculating means for calculating an interconnect delay for the child node using sets of moments associated with each gate downstream from the child node;

calculating means for calculating slack at the child node for the selected buffer using the gate delay for the child node and the interconnect delay for the child node;

comparing means for comparing the slack for the selected buffer with slack for at least one other buffer in the plurality of buffers;

determining means for determining an optimal buffer at the child node based on comparing slacks; and

inserting means for inserting the optimal buffer at the child node.

12. The system recited in claim 11 further comprising:

calculating means for calculating a set of moments associated with a parent node using the sets of moments associated with each gate downstream from the child node and moments associated with a wire from the child node to the parent node; and

calculating means for calculating slack for the wire at the parent node using the set of moments associated with the parent node.

13. The system recited in claim 12 further comprising:

selecting means for selecting a second buffer from a plurality of buffers, each buffer in the plurality of buffers having unique buffer characteristics;

calculating means for calculating a π

-model of a downstream circuit to the parent node;

calculating means for calculating an effective capacitance for the parent node using the π

-model and the buffer characteristics of the selected second buffer;

calculating means for calculating a gate delay for the parent node using the effective capacitance of the parent node;

calculating means for calculating an interconnect delay for the parent node using sets of moments associated with each gate downstream from the parent node;

calculating means for calculating slack at the parent node for the selected buffer using the gate delay for the parent node and the interconnect delay for the parent node;

comparing means for comparing the slack for the selected buffer with slack for at least one other buffer in the plurality of buffers; and

determining means for determining an optimal buffer at the parent node based on comparing slacks.

14. The system recited in claim 11, wherein the π

-model comprises at least one non-negative capacitance value.

16. The system recited in claim 11, wherein each set of moments associated with each gate comprises a set of three moments for each gate, the three moments being the first three moments associated with each gate.

17. The system recited in claim 11, wherein the calculating means for calculating a gate delay for the child node uses an implementing means for implementing a curve-fitted equation.

18. The system recited in claim 11, wherein the child node is one of a sink, a child case, and a two children case.

19. The system recited in claim 11, wherein the child node has a first child and a second child and wherein the π

-model is the first π

-model, the effective capacitance is the first effective capacitance, the gate delay is the first gate delay, the interconnect delay is the first interconnect delay, the sets of moments are first sets of moments, and the slack is the first slack, the method further comprising;

calculating means for calculating a second effective capacitance for the child node using a second π

-model and the buffer characteristics of the selected buffer;

calculating means for calculating a second gate delay for the parent node using a second effective capacitance of the child node;

calculating means for calculating a second interconnect delay for the child node using second sets of moments associated with each gate downstream from the child node;

calculating means for calculating a second slack at the child node for the selected buffer using the second gate delay for the child node and the second interconnect delay for the child node; and

comparing means for comparing the second slack for the second child for the selected buffer with either slack for at least one other buffer in the plurality of buffers or the first slack.

20. The system recited in claim 11 further comprises:

storing means for storing the π

-model for the parent node;

storing means for storing the slack for the parent node; and

storing means for storing the set of moments associated with the parent node.

21. A computer program product implemented in a data processing system for optimizing buffer insertion with accurate gate and interconnect delay computations at a node in a circuit, the program embodied on a computer readable medium as a series of instructions, the instructions comprising:

selecting instructions for selecting a buffer from a plurality of buffers, each buffer in the plurality of buffers having unique buffer characteristics;

calculating instructions for calculating a π

-model of a downstream circuit to a child node;

calculating instructions for calculating an effective capacitance for the child node using the π

-model and the buffer characteristics of the selected buffer;

calculating instructions for calculating a gate delay for the child node using the effective capacitance of the child node;

calculating instructions for calculating an interconnect delay for the child node using sets of moments associated with each gate downstream from the child node;

calculating instructions for calculating slack at the child node for the selected buffer using the gate delay for the child node and the interconnect delay for the child node;

comparing instructions for comparing the slack for the selected buffer with slack for at least one other buffer in the plurality of buffers; and

determining instructions for determining an optimal best buffer at the child node based on comparing the slack.

22. A circuit including an optimized buffer, the circuit comprising:

a child node;

a downstream circuit connected to the child node; and

a buffer connected to the child node opposite the downstream circuit, wherein the buffer is selected from a plurality of buffers based on effective capacitance for the child node using a π

-model of the downstream circuit and the buffer characteristics of the selected buffer, and further based on an interconnect delay for the child node using sets of moments associated with each gate downstream from the child node.