Placement-Driven Physical-Hierarchy Generation

• US 20070245281A1
• Filed: 04/12/2007
• Published: 10/18/2007
• Est. Priority Date: 04/14/2006
• Status: Abandoned Application

• Current Assignee: Magma Design Automation (Synopsys Incorporated)
• Original Assignee: Magma Design Automation (Synopsys Incorporated)
• Inventors: Avidan, Jacob, Carpenter, Roger, Cai, Hong, Balasundaram, Niranjana, Riepe, Michael, Verbeek, Menno
• Application Number:
  US11/734,757
• Publication Number:
  US 20070245281A1
• Time in Patent Office: Days
• US Class Current: 716/102
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method and system for performing placement-driven physical hierarchy generation in the context of an integrated circuit layout generation system is provided. This generation optimizes the physical hierarchy to improve placement of the cells in the layout, and the associated interconnect routability and delay. A new pre-clustering phase is introduced to maintain as much of the input logical hierarchy as possible while maintaining physical hierarchy quality. And a new cost function is described which is based on measuring the mutual affinity of cells in a virtually-flat placement. The new cost function is used during the new pre-clustering phase, as well as the common clustering, partitioning, and declustering/refinement phases of physical hierarchy generation.

Claims

1. An automated method for physical hierarchy generation, the method comprising:

receiving a virtually-flat placement of a logically hierarchical design having a plurality of cells;

calculating a placement affinity metric in response to receiving the virtually-flat placement; and

coarsening the plurality of cells by clustering cells in the logically hierarchical design using the calculated placement affinity metric.

2. The method of claim 1, further comprising pre-clustering the plurality of cells using at least one of logical relationships between the plurality of cells in the logically hierarchical design and the placement affinity metric.

3. The method of claim 1, wherein the virtually-flat placement comprises:

a set of approximate locations of cells, wherein the set of approximate locations are selected to satisfy a predetermined set of design objectives.

4. The method of claim 3, wherein the set of design objectives comprises at least one of wire length, routing congestion, and critical path delay.

5. The method of claim 1, wherein the placement affinity metric, M_pl(C), is determined by a first function that quantifies relative proximity of cells to each other in a cluster as a result of forming the cluster.

6. The method of claim 5, wherein the first function is

7. The method of claim 1, wherein coarsening comprises iteratively merging smaller clusters of cells into larger clusters of cells.

8. The method of claim 1, wherein coarsening comprises using a best choice clustering heuristic, the best choice clustering heuristic comprising computing a clustering score, wherein the clustering score is based at least in part on a pin reduction score and a placement affinity score.

9. The method of claim 8, wherein the pin reduction score, S_pl, is determined by

10. The method of claim 8, wherein the placement affinity score, S_pl, is determined by:

11. The method of claim 8, wherein the clustering score is a linear combination of the pin reduction and the placement affinity.

12. The method of claim 1, wherein coarsening the plurality of cells further comprises performing a lazy update clustering heuristic.

13. The method of claim 1, further comprising:

generating a simplified netlist responsive to coarsening the plurality of cells; and

generating an initial partitioning based on a set of design objectives and the simplified netlist.

14. The method of claim 13, further comprising refining the initial partitioning based on the placement affinity metric.

15. The method of claim 13, further comprising repeating one or more of the steps of coarsening the virtually-flat placement, generating the initial partitioning, and refining the initial partitioning.

16. An automated method for physical hierarchy generation, the method comprising:

receiving a virtually-flat placement of a logically hierarchical design comprising a plurality of cells clustered into initial partitions;

calculating a placement affinity metric; and

refining the initial partitions by moving at least one cluster between the initial partitions, wherein the at least one cluster is selected using the placement affinity metric.

17. The method of claim 16, further comprising uncoarsening clusters of cells in the initial partitions by de-clustering one or more cells previously clustered in a coarsening stage.

18. The method of claim 17, wherein the refining the initial partitions further comprises:

moving one or more de-clustered cells from a first partition to a second partition to generate a new partitioning; and

updating a refinement score responsive to moving the one or more de-clustered cells, the refinement score based at least in part on a measurement of mutual affinity of the one or more cells in the new partitioning.

19. The method of claim 18 wherein the refinement score is a linear combination of a cut set reduction score and a placement affinity score.

20. The method of claim 16, further comprising creating physical partitions based on the refined initial partitions.

21. The method of claim 20, wherein creating the physical partitions comprises partitioning all instances of a repeated block in separate physical partitions.

22. The method of claim 21, wherein the instances of the repeated block all have identical glue logic.

23. The method of claim 20, wherein creating the physical partitions comprises minimizing the number of different power domains in each physical partition.

24. The method of claim 20, wherein each physical partition has cells from only one power domain.

25. The method of claim 20, wherein creating the physical partitions comprises minimizing the number of different clock domains in each physical partition.

26. The method of claim 20, wherein each physical partition has cells from only one clock domain.

27. The method of claim 16, wherein refining the initial partitions comprises a Fiduccia-Mattheyses style k-way partition refinement process.

28. A computer readable storage medium for physical hierarchy generation, the computer readable storage medium storing instructions executable by a processing system, the instructions when executed cause the processing system to:

receive a virtually-flat placement of a logically hierarchical design having a plurality of cells;

calculate a placement affinity metric in response to receiving the virtually-flat placement; and

coarsen the plurality of cells by clustering cells in the logically hierarchical design using the calculated placement affinity metric.

29. The computer readable storage medium of claim 28, further comprising stored instructions that when executed cause the processing system to pre-cluster the plurality of cells using at least one of a set of logical relationships between the plurality of cells in the logically hierarchical design and the placement affinity metric.

30. The computer readable storage medium of claim 28, wherein the instructions to coarsen further comprise instructions that when executed cause the processing system to iteratively merge smaller clusters of cells into larger clusters of cells.

31. The computer readable storage medium of claim 28, wherein the instructions to coarsen further comprise instructions that when executed cause the processing system to use a best choice clustering heuristic, the best choice clustering heuristic comprising instructions that when executed cause the processing system to compute a clustering score, wherein the clustering score is based at least in part on a pin reduction score and a placement affinity score.

32. The computer readable storage medium of claim 28, further comprising stored instructions that when executed further cause the processing system to:

generate a simplified netlist responsive to coarsening the plurality of cells; and

generate an initial partitioning based on a set of design objectives and the simplified netlist.

33. The computer readable storage medium of claim 32, further comprising stored instructions that when executed further cause the processing system to refine the initial partitioning using the placement affinity metric.

34. The computer readable storage medium of claim 33, further comprising stored instructions that when executed cause the processing system to repeat instructions that cause it to coarsen the virtually-flat placement, generate the initial partitioning, and refine the initial partitioning.

35. A computer readable storage medium for physical hierarchy generation, the computer readable storage medium storing instructions executable by a processing system, the instructions when executed cause the processing system to:

receive a virtually-flat placement of a logically hierarchical design comprising a plurality of cells clustered into initial partitions;

calculate a placement affinity metric; and

refine the initial partitions by moving at least one cluster between the initial partitions, wherein the at least one cluster is selected using the placement affinity metric.

36. The computer readable storage medium of claim 35, the instructions when executed further cause the processing system to uncoarsen clusters of cells in the initial partitions by de-clustering one or more cells previously clustered in a coarsening stage.

37. The computer readable storage medium of claim 36, wherein refining the initial partitions further comprises instructions that when executed cause the processing system to:

move one or more de-clustered cells from a first partition to a second partition to generate a new partitioning; and

update a refinement score responsive to moving the one or more de-clustered cells, the refinement score based at least in part on a measurement of mutual affinity of the one or more cells in the new partitioning.