Constrained optimization with linear constraints to remove overlap among cells of an integrated circuit

• US 20040225982A1
• Filed: 05/09/2003
• Published: 11/11/2004
• Est. Priority Date: 05/09/2003
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Naylor, William C., Donelly, Ross A., Woolever, Jason R.
• Granted Patent: US 6,948,143 B2
• Time in Patent Office: Days
• US Class Current: 716/9
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method and system of constrained optimization with linear constraints to remove overlap among cells of an integrated circuit. A coarse placement using well known methods may provide an initial placement of cells. Overlapping cells are separated. Any cell moved to its initial placement may be fixed so as not to be moved during subsequent placements. A plurality of linear inequalities representing allowable placements of a plurality of cells of a layout is generated. An objective function measuring cell movement subject to the constraints of the plurality of inequalities is minimized. The objective function minimizes cell movement from the initial cell placement. In this novel manner, large and small cells may be automatically simultaneously placed, deriving speed and quality advantages over prior art methods.

Claims

1. A computer implemented method for placing circuit elements of an integrated circuit design comprising:

accessing a layout of said design with an initial cell placement;

generating a plurality of linear inequalities to represent allowable placements of a plurality of cells of a layout to remove cell overlap; and

minimizing an objective function measuring cell movement subject to constraints of said plurality of inequalities to arrive at a new cell placement, said objective function minimizing cell movement from said initial cell placement.

2. The method of claim 1 wherein said minimizing comprises solving said objective function subject to said constraints using quadratic programming, wherein said objective function is a quadratic expression.

3. The method of claim 1 wherein said minimizing comprises solving said objective function subject to said constraints using linear programming.

4. The method of claim 1 wherein said minimizing comprises using reduced matrix methods to solve said objective function subject to said constraints.

5. The method of claim 1 further comprising combining cells into a multi-cell entity when movement of said cells causes said cells to abut.

6. The method of claim 5 further comprising determining if fragmenting said multi-cell entity reduces said objective function.

7. The method of claim 6 wherein said determining comprises solving a set of linear relations.

8. The method of claim 6 wherein said determining comprises traversing a tree structure.

9. The method of claim 6 further comprising fragmenting said multi-cell entity to reduce said objective function.

34. The computer readable medium of claim 1 wherein said minimizing comprises using reduced matrix methods to solve said objective function subject to said constraints.

10. A computer implemented method of optimizing a placement of cells of an integrated circuit comprising:

accessing a layout having an initial cell placement;

assigning cells to legal positions;

moving a cell toward its initial placement location;

combining cells into a multi-cell entity if said moving said cell causes said cell to abut another cell; and

determining if fragmenting said multi-cell entity reduces an objective function minimizing displacement from said initial cell placement.

11. The method of claim 10 wherein said moving comprises selecting a cell with the largest weighted displacement from its initial placement.

12. The method of claim 11 wherein a weighting factor is related to said cell'"'"'s area.

13. The method of claim 10 further comprising fixing the location of said cell if said cell is located in said cell'"'"'s initial placement location.

14. The method of claim 10 wherein said determining comprises solving a set of linear relations.

15. The method of claim 10 wherein said determining comprises traversing a tree structure.

16. The method of claim 10 further comprising fragmenting said multi-cell entity to reduce said objective function.

17. A method of fragmenting a multi-cell entity comprising:

constructing a set of relationships for each cell in said multi-cell entity, said relationships describing a plurality of optimizations and constraints upon the location of said cells;

solving said set of relationships for inter-cell interactions; and

fragmenting said multi-cell entity between two cells of said multi-cell entity having the greatest attractive inter-cell interaction.

18. The method of claim 17 wherein said plurality of optimizations comprise a displacement from an initial cell placement location.

19. The method of claim 18 wherein said displacement is weighted by the area of a cell.

20. The method of claim 17 wherein said plurality of optimizations are modeled as spring forces.

21. The method of claim 17 wherein said constraints comprise adjacent constituent cells of said multi-cell entity abutting but not overlapping.

22. The method of claim 17 wherein said constraints are modeled as spring forces.

23. The method of claim 17 wherein said solving comprises pivoting a matrix.

24. A method of fragmenting a multi-cell entity comprising:

constructing a spanning tree graph describing a plurality of optimizations and constraints upon the location of cells comprising said multi-cell entity;

traversing said spanning tree graph to determine inter-cell interactions; and

fragmenting said multi-cell entity between two cells of said multi-cell entity having the greatest attractive inter-cell interaction.

25. The method of claim 24 wherein said optimizations comprise a displacement from an initial cell placement location.

26. The method of claim 25 wherein said displacement is weighted by the area of a cell.

27. The method of claim 24 wherein said optimizations are modeled as spring forces.

28. The method of claim 24 wherein said constraints comprise adjacent constituent cells of said multi-cell entity abutting but not overlapping.

29. The method of claim 24 wherein said constraints are modeled as spring forces.

30. The method of claim 24 wherein said solving does not comprise a matrix pivot operation.

31. A computer readable medium comprising instructions which when executed by a computer system causes said computer system to implement a process comprising:

accessing a layout of said design with an initial cell placement;

generating a plurality of linear inequalities to represent allowable placements of a plurality of cells of a layout to remove cell overlap; and

minimizing an objective function measuring cell movement subject to constraints of said plurality of inequalities to arrive at a new cell placement, said objective function minimizing cell movement from said initial cell placement.

32. The computer readable medium of claim 31 wherein said minimizing comprises solving said objective function subject to said constraints using quadratic programming, wherein said objective function is a quadratic expression.

33. The computer readable medium of claim 31 wherein said minimizing comprises solving said objective function subject to said constraints using linear programming.

35. The computer readable medium of claim 31 further comprising combining cells into a multi-cell entity when movement of said cells causes said cells to abut.

36. The computer readable medium of claim 35 further comprising determining if fragmenting said multi-cell entity reduces said objective function.

37. The computer readable medium of claim 36 wherein said determining comprises solving a set of linear relations.

38. The computer readable medium of claim 36 wherein said determining comprises traversing a tree structure.

39. The computer readable medium of claim 36 further comprising fragmenting said multi-cell entity to reduce said objective function.