Method for hierarchical time drive circuit layout by rebudgeting timing constraints of plurality of logical blocks after placement

• US 5,778,216 A
• Filed: 06/30/1995
• Issued: 07/07/1998
• Est. Priority Date: 06/30/1995
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Venkatesh, S. V.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Ki S.
• Application Number:
  US08/497,699
• Time in Patent Office: 1,103 Days
• Field of Search: 395/921, 395/919, 395/500, 395/550, 395/600, 395/558, 395/555, 364/488, 364/489, 364/490, 364/491, 364/578
• US Class Current: 713/503
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for performing a hierarchial timing driven layout of a circuit based upon gate-level design data and circuit timing constraints, the circuit including a plurality of cells, includes: partitioning the plurality of cells into a plurality of logical blocks, a first logical block including a first plurality of cells; budgeting a block timing constraint for each of the plurality of logical blocks in response to the gate-level design data, to the circuit timing constraints, and to the partitioning of the plurality of cells into the plurality of logical blocks; placing the plurality of logical blocks within a circuit floorplan, each logical block associated with a block location within the circuit floorplan; rebudgeting the block timing constraint for at least one of the plurality of logical blocks in response to the placement of the plurality of logical blocks within the circuit floorplan; placing the first plurality of cells within a block location associated with the first logical block; and rebudgeting the timing constraint for at least one of the plurality of logical blocks in response to the placement of the first plurality of cells within the first logical block.

Claims

1. In a computer system including a memory, a method for performing a hierarchial timing driven layout of a circuit based upon gate-level design data and circuit timing constraints, the circuit including a plurality of cells, the method comprising the steps of:

partitioning the plurality of cells into a plurality of logical blocks, a first logical block including a first plurality of cells;

budgeting a block timing constraint for each of the plurality of logical blocks in response to the gate-level design data, to the circuit timing constraints, and to the partitioning of the plurality of cells into the plurality of logical blocks;

placing the plurality of logical blocks within a circuit floorplan, each logical block associated with a block location within the circuit floorplan;

rebudgeting the block timing constraint for at least one of the plurality of logical blocks in response to the placement of the plurality of logical blocks within the circuit floorplan;

placing the first plurality of cells within a block location associated with the first logical block; and

rebudgeting the timing constraint for at least one of the plurality of logical blocks in response to the placement of the first plurality of cells within the first logical block.

2. The method of claim 1, wherein a second logical block includes a second plurality of cells, the method further comprising the steps of:

placing the second plurality of cells within a block location associated with the second logical block; and

rebudgeting the timing constraint for at least one of the plurality of logical blocks in response to the placement of the second plurality of cells within the second logical block.

3. The method of claim 1, wherein a second logical block includes a second plurality of cells, the method further comprising the steps of:

determining a predicted delay for the second logical block in response to the gate level design data;

comparing the predicted delay for the second logical block to the block timing constraint for the second logical block; and

if the predicted delay for the second logical block exceeds the block timing constraint for the second logical block, rearranging the first plurality of cells within the block location associated with the first logical block, and rebudgeting the timing constraint for at least the second logical block in response to the rearranging.

4. The method of claim 1, further comprising the steps of:

determining a predicted delay for the circuit in response to the timing constraint for each of the plurality of logical blocks;

comparing the predicted delay for the circuit to the circuit timing constraints; and

placing the plurality of logical blocks within another circuit floorplan, when the predicted delay for the circuit exceeds the circuit timing constraints.

5. The method of claim 1, further comprising the steps of:

determining a predicted delay for the circuit in response to the timing constraint for each of the plurality of logical blocks;

comparing the predicted delay for the circuit to the circuit timing constraints; and

repartitioning the plurality of cells into another plurality of logical blocks when the predicted delay for the circuit exceeds the circuit timing constraints.

6. The method of claim 1, further comprising the steps of:

comparing a predicted delay for the circuit to the circuit timing constraints, the predicted delay formed in response to at least the timing constraint for each of the plurality of logical blocks; and

redesigning the circuit, when the predicted delay for the circuit exceeds the circuit timing constraints.

7. A circuit formed in accordance with the method described in claim 1.

24. The method of claim 2,

wherein the step of placing the first plurality of cells places the first plurality of cells in response to the block timing constraint for the first logical block;

and

wherein the step of placing the second plurality of cells places the second plurality of cells in response to the block timing constraint for the second logical block.

25. The method of claim 24, wherein the step of placing the first plurality of cells is performed independently of the step of placing the second plurality of cells.

8. A computer system for performing hierarchial timing driven layout of a circuit based upon gate-level design data and circuit timing constraints, the circuit including a plurality of cells, the computer system comprising:

a memory for storing the gate-level design data and the circuit timing constraints;

partitioning means, coupled to the memory for partitioning the plurality of cells into a plurality of logical blocks, a first logical block including a first plurality of cells;

budgeting means coupled to the memory and to the partitioning means, for budgeting a block timing constraint for each of the plurality of logical blocks in response to the gate-level design data, to the circuit timing constraints, and to the partitioning of the plurality of cells into the plurality of logical blocks;

first placing means coupled to the memory and to the partitioning means for placing the plurality of logical blocks within a circuit floorplan, each logical block associated with a block location within the circuit floorplan;

first rebudgeting means coupled to the memory, to the budgeting means, and to the first placing means, for rebudgeting the block timing constraint for at least one of the plurality of logical blocks in response to placement of the plurality of logical blocks within the circuit floorplan;

second placing means coupled to the memory and to the partitioning means for placing the first plurality of cells within a block location associated with the first logical block; and

second rebudgeting means coupled to the memory, to the second placing means and the first rebudgeting means, for rebudgeting the timing constraint for at least one of the plurality of logical blocks in response to placement of the first plurality of cells within the first logical block.

9. The computer system of claim 8, wherein a second logical block includes a second plurality of cells, the computer system further comprising:

third placing means coupled to the memory and to the partitioning means for placing the second plurality of cells within a block location associated with the second logical block; and

third rebudgeting means coupled to the memory, to the third placing means and the second rebudgeting means, for rebudgeting the timing constraint for at least one of the plurality of logical blocks in response to placement of the second plurality of cells within the second logical block.

10. In a computer system including a memory, a method of determining a timing model for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the method comprising the steps of:

determining a slack budget factor for each of the plurality of nets, in response to the gate-level design data and the circuit timing constraints;

determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

determining the timing model for the logical block, in response to the net constraint for each of the plurality of nets, to the timing models for the plurality of cells and to the circuit timing constraints, wherein the timing model for the logical block includes a load-sensitive component.

11. The method of claim 10, wherein the slack budget factor for each of the plurality of nets is also determined in response to historically based length estimates for each of the plurality of nets.

12. The method of claim 10, wherein the timing model determining step comprises the step of:

determining a load sensitive delay factor of one of the plurality of cells.

13. The method of claim 10, wherein signals have required arrival times at outputs of the logical block, wherein for any one of the signals no two required arrival times exist which differ based on the path taken by the one signal.

14. The method of claim 10, wherein a signal has a first required arrival time and a second required arrival time at an output of the logical block, said first and second required arrival times dependent on the path taken by the signal, the net constraint determining step further comprises the steps of:

determining possible timing pairs for each of the plurality of nets in response to the slack budget factor for each of the plurality of nets and to the first required arrival time of the signal and the second required arrival time of the signal; and

determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data, and to the possible timing pairs.

15. The method of claim 14, wherein the possible timing pairs for each of the plurality of nets includes a required arrival time and an arrival time.

16. A circuit formed with a timing model for a logical block in accordance with the method described in claim 10.

17. In a computer system including a memory, a method of determining a timing constraint for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the method comprising the steps of:

determining a slack budget factor for each of the plurality of nets, in response to the gate-level design data and to the circuit timing constraints;

determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

determining the timing constraint for the logical block, in response to the net constraint for each of the plurality of nets, to the timing models for the plurality of cells and to the circuit timing constraints.

18. The method of claim 17, wherein the slack budget factor for each of the plurality of nets is also determined in response to historically based length estimates for each of the plurality of nets.

19. The method of claim 17, wherein a signal has a first required arrival time and a second required arrival time at an output of the logical block, and wherein the net constraint determining step comprises the steps of:

determining possible timing pairs for each of the plurality of nets in response to the slack budget factor for each of the plurality of nets and to the first required arrival time of the signal and the second required arrival time of the signal; and

determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the possible timing pairs.

20. A circuit formed with a timing constraint for a logical block in accordance with the method described in claim 17.

21. A computer system for determining a timing model for a logical block within a circuit, the computer system comprising:

a memory for storing gate-level design data including a plurality of cells and plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints;

a slack budget factor module, coupled to the memory, for determining a slack budget factor for each of the plurality of nets, in response to the gate-level design data and to the circuit timing constraints;

a zero slack algorithm module, coupled to the memory and the slack budget factor module, for determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

a block budgeter, coupled to the memory and to the zero slack algorithm module, for determining the timing model for the logical block, in response to the timing models for the plurality of cells, to the net constraint for each of the plurality of nets and to the circuit timing constraints.

22. The computer system of claim 21, wherein the block budgeter further comprises:

a load sensitive delay factor determining module for determining a load sensitive delay factor of one of the plurality of cells.

23. A computer system for determining a timing constraint for a logical block within a circuit, the computer system comprising:

a memory for storing gate-level design data including a plurality of cells and plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints;

a slack budget factor module, coupled to the memory, for determining a slack budget factor for each of the plurality of nets, in response to the gate-level design data and to the circuit timing constraints;

a zero slack algorithm module, coupled to the memory and the slack budget factor module, for determining a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

a block budgeter, coupled to the memory and to the zero slack algorithm module, for determining the timing constraint for the logical block, in response to the timing models for the plurality of cells, to the net constraint for each of the plurality of nets and to the circuit timing constraints.

26. A computer program product, for a computer system including a processor and a memory, for performing hierarchial timing driven layout of a circuit based upon gate-level design data and circuit timing constraints, the circuit including a plurality of cells, the computer program product comprising:

a computer readable storage medium comprising;

(a) code that directs the processor to partition the plurality of cells into a plurality of logical blocks, a first logical block including a first plurality of cells;

(b) code that directs the processor to budget a block timing constraint for each of the plurality of logical blocks in response to the gate-level design data, to the circuit timing constraints, and to the partitioning of the plurality of cells into the plurality of logical blocks;

(c) code that directs the processor to place the plurality of logical blocks within a circuit floorplan, each logical block associated with a block location within the circuit floorplan;

(d) code that directs the processor to rebudget the block timing constraint for at least one of the plurality of logical blocks in response to the placement of the plurality of logical blocks within the circuit floorplan;

(e) code that directs the processor to place the first plurality of cells within a block location associated with the first logical block; and

(f) code that directs the processor to rebudget the timing constraint for at least one of the plurality of logical blocks in response to the placement of the first plurality of cells within the first logical block.

27. The computer program product of claim 26, wherein a second logical block includes a second plurality of cells, and wherein the computer readable storage medium further comprises:

code that directs the processor to place the second plurality of cells within a block location associated with the second logical block; and

code that directs the processor to rebudget the timing constraint for at least one of the plurality of logical blocks in response to the placement of the second plurality of cells within the second logical block.

28. The computer program product of claim 27,

wherein the code for placing the first plurality of cells comprises code that directs the processor to place the first plurality of cells in response to the block timing constraint for the first logical block;

and

wherein the code for placing the second plurality of cells comprises code that directs the processor to place the second plurality of cells in response to the block timing constraint for the second logical block.

29. The computer program product of claim 26,

wherein a second logical block includes a second plurality of cells;

wherein the code (f) includes code that directs the processor to rebudget the timing constraint for the second logical block, thereby establishing a new timing constraint for the second logical block; and

wherein the computer readable storage medium further comprises;

code that directs the processor to place the second plurality of cells within a block location associated with the second logical block;

code that directs the processor to determine a predicted delay for the second logical block in response to the gate level design data; and

code that directs the processor to compare the predicted delay for the second logical block to the block timing constraint for the second logical block;

code that directs the processor to rearrange the second plurality of cells within the block location associated with the second logical block in response to the new timing constraint for the second logical block, when the predicted delay for the second logical block exceeds the block timing constraint for the second logical block.

30. The computer program product of claim 26, wherein the computer readable storage medium further comprises:

code that directs the processor to determine a predicted delay for the circuit in response to the timing constraint for each of the plurality of logical blocks;

code that directs the processor to compare the predicted delay for the circuit to the circuit timing constraints; and

code that directs the processor to place the plurality of logical blocks within another circuit floorplan, when the predicted delay for the circuit exceeds the circuit timing constraints.

31. The computer program product of claim 26, wherein the computer readable storage medium further comprises:

code that directs the processor to determine a predicted delay for the circuit in response to the timing constraint for each of the plurality of logical blocks;

code that directs the processor to compare the predicted delay for the circuit to the circuit timing constraints; and

code that directs the processor to repartitioning the plurality of cells into another plurality of logical blocks, when the predicted delay for the circuit exceeds the circuit timing constraints.

32. A computer system for performing hierarchial timing driven layout of a circuit based upon gate-level design data and circuit timing constraints, the circuit including a plurality of cells, the system including a processor and a memory, the system comprising:

an input device, coupled to the memory for inputting the design data and circuit timing constraints;

an output device, coupled to the processor and to the memory for outputting circuit layout information; and

a computer readable storage medium comprising;

(a) code that directs the processor to partition the plurality of cells into a plurality of logical blocks, a first logical block including a first plurality of cells;

(b) code that directs the processor to budget a block timing constraint for each of the plurality of logical blocks in response to the gate-level design data, to the circuit timing constraints, and to the partitioning of the plurality of cells into the plurality of logical blocks;

(c) code that directs the processor to place the plurality of logical blocks within a circuit floorplan, each logical block associated with a block location within the circuit floorplan;

(d) code that directs the processor to rebudget the block timing constraint for at least one of the plurality of logical blocks in response to the placement of the plurality of logical blocks within the circuit floorplan;

(e) code that directs the processor to place the first plurality of cells within a block location associated with the first logical block; and

(f) code that directs the processor to rebudget the timing constraint for at least one of the plurality of logical blocks in response to the placement of the first plurality of cells within the first logical block.

33. The computer system of claim 32,

wherein a second logical block includes a second plurality of cells;

wherein the code (f) includes code that directs the processor to rebudget the timing constraint for the second logical block, thereby establishing a new timing constraint for the second logical block; and

wherein the computer readable storage medium further comprises;

code that directs the processor to place the second plurality of cells within a block location associated with the second logical block;

code that directs the processor to determine a predicted delay for the second logical block in response to the gate level design data; and

code that directs the processor to compare the predicted delay for the second logical block to the block timing constraint for the second logical block;

code that directs the processor to rearrange the second plurality of cells within the block location associated with the second logical block in response to the new timing constraint for the second logical block, when the predicted delay for the second logical block exceeds the block timing constraint for the second logical block.

34. A computer program product, for a computer system including a processor and a memory, for determining a timing model for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the computer program product comprising:

a computer readable storage medium comprising;

code that directs the processor to determine a slack budget factor for each of the plurality of nets, in response to the gate-level design data and the circuit timing constraints;

code that directs the processor to determine a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

code that directs the processor to determine the timing model for the logical block, in response to the net constraint for each of the plurality of nets, to the timing models for the plurality of cells and to the circuit timing constraints.

35. The computer system of claim 34, the computer system for determining a timing model for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the computer system further comprising:

the computer program product of claim 34;

an input device, coupled to the memory for inputting the design data and circuit timing constraints; and

an output device, coupled to the processor and to the memory for outputting circuit layout information.

36. A computer program product, for a computer system including a processor and a memory, for determining a timing constraint for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the computer program product comprising:

a computer readable storage medium comprising;

code that directs the processor to determine a slack budget factor for each of the plurality of nets, in response to the gate-level design data and to the circuit timing constraints;

code that directs the processor to determine a net constraint for each of the plurality of nets, in response to the slack budget factor for each of the plurality of nets, to the gate-level design data and to the circuit timing constraints; and

code that directs the processor to determine the timing constraint for the logical block, in response to the net constraint for each of the plurality of nets, to the timing models for the plurality of cells and to the circuit timing constraints.

37. The computer system of claim 36, the computer system for determining a timing constraint for a logical block within a circuit, the memory having gate-level design data, including a plurality of cells and a plurality of nets for the logical block, and timing models for each of the plurality of cells, and circuit timing constraints, the computer system further comprising:

the computer program product of claim 36;

an input device, coupled to the memory for inputting the design data and circuit timing constraints; and

an output device, coupled to the processor and to the memory for outputting circuit layout information.