Tightloop method of timing driven placement

• US 6,601,226 B1
• Filed: 03/14/2000
• Issued: 07/29/2003
• Est. Priority Date: 03/14/2000
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Raj, Satish, Hill, Dwight
• Primary Examiner(s): Garbowski, Leigh M.
• Application Number:
  US09/524,772
• Time in Patent Office: 1,232 Days
• Field of Search: 713/503, 716/7, 716/9, 716/10, 716/16, 716/1, 716/2, 716/6, 716/8, 716/11, 716/5
• US Class Current: 716/113
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A tightloop method of timing driven placement. The present invention interleaves timing analyses and updates net weight based on the timing analyses as part of the cell location refinement processes of a placement algorithm. Thereby, the placement algorithm is augmented to factor in timing information such that the final placement is effective from overlap, net length, and timing perspectives.

Claims

1. A method of placing cells for an integrated circuit design, comprising the steps of:

a) initially placing cells at particular locations;

b) estimating a plurality of capacitances associated with a plurality of nets corresponding to the current x-y position of cell placements;

c) performing a timing analysis based on the plurality of capacitances;

d) determining a plurality of net weights as a function of the timing analysis, an overlap, and a net length;

e) determining a plurality of dampened net weights, wherein each dampened net weight is equal to a corresponding one of the plurality of net weights multiplied by a first weight factor, plus a corresponding previous one of the plurality of dampened net weights multiplied by one minus the first weight factor;

f) changing the cell placements according to the plurality of dampened net weights; and

g) repeating one or more of the steps b-f iteratively a plurality of times.

2. The method of claim 1, wherein steps b-f are performed as a phase in a slicing placement method.

3. The method of claim 1, wherein steps b-f are performed as a phase in a non-slicing placement method.

4. The method of claim 1, wherein the step of performing the timing analysis is comprised of the steps of:

determining a time at which data is available at an input of a path;

determining a time at which data is required at an output of the path;

calculating a set of times that data is available at a plurality of nets along the path;

calculating a set of times that data is required at the plurality of nets along the path; and

determining a plurality of slacks as a function of the set of times that data is available and the set of times that data is required.

5. The method of claim 1, wherein step c further comprises:

determining a plurality of dampened capacitances, wherein each dampened capacitance is equal to a corresponding one of the plurality of capacitances multiplied by a second weight factor, plus a corresponding previous one of the plurality of capacitances multiplied by one minus the second weight factor; and

performing a timing analysis based on the set of dampened capacitances.

6. The method of claim 1, further comprising repeating the steps of b-f and then repeating the steps of d-f iteratively a plurality of times.

7. A method for placing cells of a netlist which describes a circuit to be fabricated on a semiconductor chip, comprising the steps of:

performing a first placement of the cells;

executing a first timing analysis based on the first placement of the cells;

determining a first set of net weights according to the first timing analysis;

performing a second placement of the cells as a function of the first set of net weights;

executing a second timing analysis based on the second placement of the cells;

determining a second set of net weights according to the second timing analysis;

determining a set of dampened net weights as a function of the first set of net weights and the second set of net weights; and

performing a third placement of the cells as a function of the set of dampened net weights.

8. The method of claim 7 further comprising the steps of:

adjusting the first set of net weights as a function of a first set of overlaps; and

adjusting the second set of net weights as a function of a second set of overlaps.

9. The method of claim 7 further comprising the steps of:

adjusting the first set of net weights as a function of a first set of net lengths; and

adjusting the second set of net weights as a function of a second set of net lengths.

10. The method of claim 7, wherein the step of executing the first timing analysis is comprised of the steps of:

determining a time at which data is available at an input of a path based on the first placement of the cells;

determining a time at which data is required at an output of the path;

calculating a set of times that data is available at a plurality of nets along the path;

calculating a set of times that data is required at the plurality of nets along the path; and

determining a plurality of slacks as a function of the set of times that data is available and the set of times that data is required.

11. The method of claim 7 further comprising the steps of:

adjusting the first set of net weights as a function of a first set of drive strengths; and

adjusting the second set of net weights as a function of a second set of drive strengths.

12. A computer-readable medium having stored thereon instructions for causing a computer to implement a placement process, comprising the steps of:

a) initially placing cells at particular locations;

b) estimating a plurality of capacitances associated with a plurality of nets corresponding to the current x-y position of cell placements;

c) performing a timing analysis based on the plurality of capacitances;

d) determining a plurality of net weights as a function of the timing analysis, an overlap, a drive strength, and a net length;

e) determining a plurality of dampened net weights as a function plurality of net weights and a previous plurality of dampened net weights;

f) changing the cell placements according to the plurality of dampened net weights; and

g) repeating one or more of the steps b-e as iterative phases a plurality of times.

13. The computer-readable medium of claim 12, wherein steps b-f are performed as a phase in a slicing placement method.

14. The computer-readable medium of claim 12, wherein steps b-f bare performed as a phase in a non-slicing placement method.

15. The computer-readable medium of claim 12, wherein the step of performing the timing analysis is comprised of the steps of:

determining times at which data is available at an input of a path;

determining times at which data is required at an outputs of the path;

calculating a set of times that data is available at a plurality of nets along the path;

calculating a set of times that data is required at the plurality of nets along the path; and

determining a plurality of slacks as a function of the set of times that data is available and the set of times that data is required.

16. The computer-readable medium of claim 12, wherein step c further comprises:

determining a plurality of dampened capacitances as a function of the plurality of capacitances and a previous plurality of dampened capacitances; and

performing a timing analysis based on the plurality of dampened capacitances.

17. The computer-readable medium of claim 12, further comprising repeating the steps of b-f and then repeating steps d-f iteratively a plurality of times.

20. The method of claim 17, wherein steps b-f are performed as a phase in a slicing placement method.

21. The method of claim 17, wherein steps b-f are performed as a phase in a non-slicing placement method.

18. A method of placing cells for an integrated circuit design, comprising the steps of:

a) initially placing cells at particular locations;

b) estimating a plurality of capacitances associated with a plurality of nets corresponding to the current x-y position of cell placements;

c) determining a plurality of dampened capacitances, wherein each dampened capacitance is equal to a corresponding one of the plurality of capacitances multiplied by a second weight factor, plus a corresponding previous one of the plurality of capacitances multiplied by one minus the second weight factor;

d) performing a timing analysis based on the plurality of dampened capacitances;

e) determining a plurality of net weights as a function of the timing analysis, an overlap, and a net length;

f) changing the cell placements according to the plurality of net weights; and

g) repeating one or more of the steps b-f iteratively a plurality of times.

19. The method of claim 18, wherein step f further comprises:

determining a plurality of dampened net weights, wherein each dampened net weight is equal to a corresponding one of the plurality of net weights multiplied by a first weight factor, plus a corresponding previous one of the plurality of net weights multiplied by one minus the first weight factor; and

changing the cell placements according to the plurality of dampened net weights.

22. The method of claim 18, wherein the step of performing the timing analysis is comprised of the steps of:

determining a time at which data is available at an input of a path;

determining a time at which data is required at an output of the path;

calculating a set of times that data is available at a plurality of nets along the path;

calculating a set of times that data is required at the plurality of nets along the path; and

A determining a plurality of slacks as a function of the set of times that data is available and the set of times that data is required.

23. The method of claim 18, further comprising repeating the steps b-f and then repeating the steps of d-f iteratively a plurality of times.

24. A method for placing cells of a netlist which describes a circuit to be fabricated on a semiconductor chip, comprising:

performing a first set of phases; and

performing a second set of phases comprising;

estimating a current set of capacitances based on a previous placement of the cells;

determining a current set of dampened capacitances as a function of the current set of capacitances and a previous set of dampened capacitances;

executing a current timing analysis based on the current set of dampened capacitances and the previous placement of the cells;

determining a current set of net weights according to the current timing analysis;

determining a current set of dampened net weights as a function of the current set of net weights and a previous set of dampened net weights; and

performing a current placement of the cells as a function of the current set of dampened net weights.

25. The method of claim 24, wherein determining the current set of net weights is further determined according to a current set of overlaps.

26. The method of claim 24, wherein determining the current set of net weights is further determined according to a current set of net lengths.

27. The method of claim 24, wherein determining the current set of net weights is further determined according to a current set of drive strengths.

28. The method according to claim 24, further comprising:

performing a third set of phases comprising;

determining the current set of net weights according to the current set of overlaps;

performing the current placement of the cells as a function of the current set of net weights.

29. The method of claim 28, wherein determining the current set of net weights is further determined according to a current set of net lengths.

30. The method of claim 28, wherein determining the current set of net weights is further determined according to a current set of drive strengths.

31. The method according to claim 24, further comprising:

performing a third set of phases comprising;

determining the current set of net weights according to the current set of overlaps;

determining a current set of dampened net weights as a function of the current set of net weights and a previous set of dampened net weights; and

performing a current placement of the cells as a function of the current set of dampened net weights.

32. The method of claim 31, wherein determining the current set of net weights is further determined according to a current set of net lengths.

33. The method of claim 31, wherein determining the current set of net weights is further determined according to a current set of drive strengths.

34. The method according to claim 24, wherein performing a first set of phases comprises:

performing an initial placement of the cells;

estimating a first set of capacitances based on the initial placement of the cells;

executing a first timing analysis based on the first set of capacitances and the initial placement of the cells;

determining a first set of net weights according to the first timing analysis; and

performing a first placement of the cells a function of the first set of net weights.

35. The method of claim 34, wherein determining the current set of net weights is further determined according to a current set of overlaps.

36. The method of claim 34, wherein determining the current set of net weights is further determined according to a current set of net lengths.

37. The method of claim 34, wherein determining the current set of net weights is further determined according to a current set of drive strengths.

38. A computer-readable medium having stored thereon instructions for causing a computer to implement a placement process, comprising:

estimating a current set of capacitances based on a previous placement of the cells;

determining a current set of dampened capacitances as a function of the current set of capacitances and a previous set of capacitances;

executing a current timing analysis based on the current set of dampened capacitances and the previous placement of the cells;

determining a current set of net weights according to the current timing analysis;

determining a current set of dampened net weights as a function of the current set of net weights and a previous set of net weights; and

performing a current placement of the cells as a function of the current set of dampened net weights.

39. The computer-readable medium of claim 38, wherein determining the current set of net weights is further determined according to a current set of overlaps.

40. The computer-readable medium of claim 38, wherein determining the current set of net weights is further determined according to a current set of net lengths.

41. The computer-readable medium of claim 38, wherein determining the current set of net weights is further determined according to a current set of drive strengths.