Placement method for integrated circuit design using topo-clustering

• US 20020138816A1
• Filed: 05/01/2002
• Published: 09/26/2002
• Est. Priority Date: 06/12/1998
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Chakraborty, Abhijeet, Sarrafzadeh, Majid, Yeap, Gary K., Boyle, Douglas B., Raje, Salil R., Malik, Sharad, Pileggi, Lawrence, Taraporevala, Feroze Peshotan, Yamamoto, Dennis, Shieh, Lilly
• Granted Patent: US 6,961,916 B2
• Time in Patent Office: Days
• US Class Current: 716/11
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The present invention, generally speaking, provides a placement method for the physical design of integrated circuits in which natural topological feature clusters (topo-clusters) are discovered and exploited during the placement process. Topo-clusters may be formed based on various criteria including, for example, functional similarity, proximity (in terms of number of nets), and genus. Genus refers to a representation of a netlist in terms of a number of planar netlists—netlists in which no crossing of nets occurs. Topo-clusters drive initial placement, with all of the gates of a topo-cluster being placed initially in a single bin of the placement layout or within a group of positionally-related bins. The portion of a topo-cluster placed within a given bin is called a quanto-cluster. An iterative placement refinement process then follows, using a technique referred to herein as Geometrically-Bounded FM (GBFM), and in particular Dual GBFM. In GBFM, FM is applied on a local basis to windows encompassing some number of bins. From iteration to iteration, windows may shift position and vary in size. When a region bounded by a window meets a specified cost threshold in terms of a specified cost function, that region does not participate. The cost function takes account of actual physical metrics—delay, area, congestion, power, etc. “Dual” refers to the fact that each iteration has two phases. During a first phase, FM is performed within a region on a quanto-cluster basis. During a second phase, FM is performed within the region on a gate basis. GBFM occurs in the context of recursive quadrisection. Hence, after GBFM has been completed, a further quadrisection step is performed in which each bin is divided into four bins, with a quarter of the gates of the original bin being placed in the center of each of the resulting bins. GBFM then follows, and the cycle repeats until each bin contains a fairly small number of gates. Following the foregoing global placement process, the circuit is then ready for detailed placement in which cells are assigned to placement rows.

Claims

1. A method of placing circuit elements on an integrated circuit design layout, comprising the steps of:

grouping circuit elements into clusters based on topological relatedness of the circuit elements of a cluster;

placing circuit elements by cluster within bins defined on the circuit design layout;

defining a plurality of regions, at least some including multiple bins; and

applying a placement refinement technique to at least some of said regions to produce a placement that is improved within at least some of the regions, as measured by a cost function.

2. The method of claim 1, wherein said placement refinement technique comprises moving at least one of circuit elements and clusters between bins within a region.

3. The method of claim 2, wherein within at least some regions both circuit elements and clusters are moved between bins.

4. The method of claim 3, wherein clusters are moved between bins first, and circuit elements are moved between bins afterward.

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

shifting a set of windows by a program-controlled shift amount relative to the integrated circuit design layout to thereby define a set of different regions; and

applying said placement refinement technique to at least some of said different regions.

6. The method of claim 5, comprising the further steps of repeating said shifting and applying steps a program-controlled number of times.

7. The method of claim 6, comprising the further steps of, for each of a plurality of iterations:

defining a plurality of regions using a set of windows of a program-controlled size;

applying said placement refinement technique to at least some of said regions;

shifting the set of windows by a program-controlled shift amount relative to the integrated circuit design layout to thereby define a set of different regions;

applying said placement refinement technique to at least some of said different regions; and

repeating said shifting and applying steps a program-controlled number of times.

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

quadrisecting said bins;

defining a plurality of different regions; and

again applying said placement refinement technique to at least some of the plurality of different regions.

9. The method of claim 8, comprising repeating the steps of quadrisection and again applying said placement refinement technique until each bin contains at most N gates.

10. The method of claim 9, wherein N<

30.

11. The method of claim 1, wherein grouping circuit elements comprises grouping circuit elements by similar function.

12. The method of claim 1, wherein grouping circuit elements comprises grouping circuit elements by netlist proximity.

13. The method of claim 1, wherein grouping circuit elements comprises grouping circuit elements based on genus analysis.

14. The method of claim 1, wherein placing circuit elements by cluster comprises, for a first cluster:

placing up to a maximum number of circuit elements from said first cluster in a centralized bin;

if circuit elements remain within said first cluster, placing up to a maximum number of circuit elements in a next bin forming part of a spiral pattern of bins; and

repeating the preceding steps until all circuit elements of the cluster have been placed.

15. The method of claim 14, wherein placing circuit elements by cluster comprises, for each succeeding cluster:

placing up to a maximum number of circuit elements from said succeeding cluster in a next bin in said spiral pattern;

if circuit elements remain within said succeeding cluster, placing up to a maximum number of circuit elements in a next bin forming part of said spiral pattern; and

repeating the preceding steps until all circuit elements of the succeeding cluster have been placed.

17. The method of claim 16, wherein the design elements are integrated circuit elements.

19. The method of claim 18, comprising the further steps of:

performing quadrisection of said bins; and

repeating said steps of selecting a window and performing N-way partitioning of circuit elements.

16. A method of forming clusters of topologically-related design elements for placement on a layout, comprising the steps of:

forming a hypergraph representing topological relatedness of said design elements;

determining planar sub-graphs of the hypergraph; and

based on said planar subgraphs, forming a plurality of clusters of design elements, each cluster including a plurality of design elements.

18. A method of refining placement of circuit elements placed within bins on an integrated circuit design layout in accordance with an initial placement, comprising the steps of:

selecting a first window surrounding a number of bins N greater than two;

performing N-way partitioning of circuit elements within said first window during which circuit elements within the first window are reapportioned among bins within the first window so as to decrease a cost function calculated over the bins within the first window;

selecting a second window having at least one bin in common with said first window; and

performing N-way partitioning of circuit elements within said second window during which circuit elements within the second window are reapportioned among bins within the second window so as to decrease a cost function calculated over the bins within the second window.

20. A method of refining placement of integrated circuit elements placed in accordance with an initial placement within bins on a design layout representing an integrated circuit, the method comprising the steps of:

defining a window encompassing a plurality of bins; and

performing multi-way partitioning of integrated circuit elements between bins within the window based on a geometric cost function.

21. The method of claim 20, wherein the geometric cost function is a function of at least one of distance and area.

22. The method of claim 20, wherein multi-way partitioning comprises exchanging the entire contents of selected bins.

23. The method of claim 20, wherein multi-way partitioning comprises exchanging selected gates between bins.

24. The method of claim 20, comprising the further steps of:

shifting the window so as to overlap a previous window; and

again performing multi-way partitioning of integrated circuit elements between bins within the window based on the geometric cost function.

25. A computer-readable medium including instructions for placing circuit elements on an integrated circuit design layout, including instructions for:

grouping circuit elements into clusters based on topological relatedness of the circuit elements of a cluster;

placing circuit elements by cluster within bins defined on the circuit design layout;

defining a plurality of regions, at least some including multiple bins; and

applying a placement refinement technique to at least some of said regions to produce a placement that is improved within at least some of the regions, as measured by a cost function.

26. A computer-readable medium including instructions for forming clusters of topologically-related design elements for placement on a layout, including instructions for:

forming a hypergraph representing topological relatedness of said design elements;

determining planar sub-graphs of the hypergraph; and

based on said planar subgraphs, forming a plurality of clusters of design elements, each cluster including a plurality of design elements.

27. A computer-readable medium including instructions for refining placement of circuit elements placed within bins on an integrated circuit design layout in accordance with an initial placement, including instructions for:

selecting a first window surrounding a number of bins N greater than two;

performing N-way partitioning of circuit elements within said first window during which circuit elements within the first window are reapportioned among bins within the first window so as to decrease a cost function calculated over the bins within the first window;

selecting a second window having at least one bin in common with said first window; and

performing N-way partitioning of circuit elements within said second window during which circuit elements within the second window are reapportioned among bins within the second window so as to decrease a cost function calculated over the bins within the second window.

28. A computer-readable medium including instructions for refining placement of integrated circuit elements placed in accordance with an initial placement within bins on a design layout representing an integrated circuit, including instructions for:

defining a window encompassing a plurality of bins; and

performing multi-way partitioning of integrated circuit elements between bins within the window based on a geometric cost function.

29. A system for placing circuit elements on an integrated circuit design layout, comprising:

means for grouping circuit elements into clusters based on topological relatedness of the circuit elements of a cluster;

means for placing circuit elements by cluster within bins defined on the circuit design layout;

means for defining a plurality of regions, at least some including multiple bins; and

means for applying a placement refinement technique to at least some of said regions to produce a placement that is improved within at least some of the regions, as measured by a cost function.

30. A method of forming clusters of topologically-related design elements for placement on a layout comprising the steps of:

forming a hypergraph representing topological relatedness of said design elements;

determining planar sub-graphs of the hypergraph; and

based on said planar subgraphs, forming a plurality of clusters of design elements, each cluster including a plurality of design elements.