Legalization of VLSI circuit placement with blockages using hierarchical row slicing

• US 7,934,188 B2
• Filed: 04/24/2008
• Issued: 04/26/2011
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: Siemens Industry Software Inc. (Siemens AG)
• Original Assignee: International Business Machines Corporation
• Inventors: Dotson, Michael W., Viswanathan, Natarajan, Alpert, Charles J., Ramji, Shyam, Nam, Gi-Joon
• Primary Examiner(s): Lin; Sun J
• Application Number:
  US12/108,599
• Publication Number:
  US 20090271752A1
• Time in Patent Office: 1,097 Days
• Field of Search: 716/8, 716/9, 716/10, 716/11, 716/118, 716/119, 716/122, 716/123, 716/124, 716/125, 716/132, 716/135
• US Class Current: 716/119
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A hierarchical method of legalizing the placement of logic cells in the presence of blockages selectively classifies the blockages into at least two different sets based on size (large and small). Movable logic cells are relocated first among coarse regions between large blockages to remove overlaps among the cells and the large blockages without regard to small blockages (while satisfying capacity constraints of the coarse regions), and thereafter the movable logic cells are relocated among fine regions between small blockages to remove all cell overlaps (while satisfying capacity constraints of the fine regions). The coarse and fine regions may be horizontal slices of the placement region having a height corresponding to a single circuit row height of the design. Cells are relocated with minimal perturbation from the previous placement, preserving wirelength and timing optimizations. The legalization technique may utilize more than two levels of granularity with multiple relocation stages.

Claims

1. A method of legalizing a placement of logic cells in an integrated circuit design, comprising:

receiving an input placement having a plurality of blockages and a plurality of movable logic cells, by executing first program instructions in a computer system;

selectively classifying the blockages into at least two different sets based on size, wherein blockages in a first set of the at least two different sets are larger than blockages in a second set of the at least two different sets, by executing second program instructions in the computer system;

relocating one or more of the movable logic cells to coarse regions defined between adjacent blockages in the first set to remove overlaps among the movable logic cells and the blockages in the first set without regard to the blockages in the second set, by executing third program instructions in the computer system; and

thereafter relocating one or more of the movable logic cells to fine regions defined between adjacent blockages in the second set to remove all cell overlaps, by executing fourth program instructions in the computer system.

2. The method of claim 1 wherein:

the movable logic cells are relocated to the coarse regions while satisfying capacity constraints of the coarse regions; and

the movable logic cells are relocated to the fine regions while satisfying capacity constraints of the fine regions.

3. The method of claim 1 wherein the coarse regions and fine regions are horizontal slices of a placement region of the integrated circuit design.

4. The method of claim 3 wherein each horizontal slice has a height corresponding to a single circuit row height of the integrated circuit design.

5. The method of claim 3 wherein a given movable logic cell is relocated to an adjacent slice when the adjacent slice has a relocation score which exceeds a predetermined threshold and is higher than relocation scores for other adjacent slices.

6. The method of claim 5 wherein a given relocation score is computed as a weighted sum of a change in a half-perimeter wirelength associated with a logic cell movement and a combination of source slice utilization and target slice utilization.

7. A computer system comprising:

one or more processors which process program instructions;

a memory device connected to said one or more processors; and

said program instructions residing in said memory device for legalizing a placement of logic cells in an integrated circuit design by receiving an input placement having a plurality of blockages and a plurality of movable logic cells, selectively classifying the blockages into at least two different sets based on size, wherein blockages in a first set of the at least two different sets are larger than blockages in a second set of the at least two different sets, relocating one or more of the movable logic cells to coarse regions defined between adjacent blockages in the first set to remove overlaps among the movable logic cells and the blockages in the first set without regard to the blockages in the second set, and thereafter relocating one or more of the movable logic cells to fine regions defined between adjacent blockages in the second set to remove all cell overlaps.

8. The computer system of claim 7 wherein the movable logic cells are relocated to the coarse regions while satisfying capacity constraints of the coarse regions, and the movable logic cells are relocated to the fine regions while satisfying capacity constraints of the fine regions.

9. The computer system of claim 7 wherein the coarse regions and fine regions are horizontal slices of a placement region of the integrated circuit design.

10. The computer system of claim 9 wherein each horizontal slice has a height corresponding to a single circuit row height of the integrated circuit design.

11. The computer system of claim 9 wherein a given movable logic cell is relocated to an adjacent slice when the adjacent slice has a relocation score which exceeds a predetermined threshold and is higher than relocation scores for other adjacent slices.

12. The computer system of claim 11 wherein a given relocation score is computed as a weighted sum of a change in a half-perimeter wirelength associated with a logic cell movement and a combination of source slice utilization and target slice utilization.

13. A computer program product comprising:

a computer-readable storage medium; and

program instructions residing in said storage medium to cause a computer to perform;

legalizing a placement of logic cells in an integrated circuit design by receiving an input placement having a plurality of blockages and a plurality of movable logic cells, selectively classifying the blockages into at least two different sets based on size, wherein blockages in a first set of the at least two different sets are larger than blockages in a second set of the at least two different sets, relocating one or more of the movable logic cells to coarse regions defined between adjacent blockages in the first set to remove overlaps among the movable logic cells and the blockages in the first set without regard to the blockages in the second set, and thereafter relocating one or more of the movable logic cells to fine regions defined between adjacent blockages in the second set to remove all cell overlaps.

14. The computer program product of claim 13 wherein the movable logic cells are relocated to the coarse regions while satisfying capacity constraints of the coarse regions, and the movable logic cells are relocated to the fine regions while satisfying capacity constraints of the fine regions.

15. The computer program product of claim 13 wherein the coarse regions and fine regions are horizontal slices of a placement region of the integrated circuit design.

16. The computer program product of claim 13 wherein each horizontal slice has a height corresponding to a single circuit row height of the integrated circuit design.

17. The computer program product of claim 13 wherein a given movable logic cell is relocated to an adjacent slice when the adjacent slice has a relocation score which exceeds a predetermined threshold and is higher than relocation scores for other adjacent slices.

18. The computer program product of claim 13 wherein a given relocation score is computed as a weighted sum of a change in a half-perimeter wirelength associated with a logic cell movement and a combination of source slice utilization and target slice utilization.