Placement method for integrated circuit design using topo-clustering

• US 6,442,743 B1
• Filed: 06/12/1998
• Issued: 08/27/2002
• Est. Priority Date: 06/12/1998
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Monterey Design Systems, Inc. (Synopsys Incorporated)
• Inventors: Sarrafzadeh, Majid, Raje, Salil R., Yamamoto, Dennis, Shieh, Lilly, Yeap, Gary K., Boyle, Douglas B., Malik, Sharad, Pileggi, Lawrence, Taraporevala, Feroze Peshotan, Chakraborty, Abhijeet
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US09/097,107
• Time in Patent Office: 1,537 Days
• Field of Search: 716/10, 716/9, 716/8, 716/7, 716/12, 716/13, 716/14
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The disclosure describes a placement method for the physical design of integrated circuits in which natural topological feature clusters are discovered and exploited during the placement process is disclosed. 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. An iterative placement refinement process is done using a technique referred to as Dual Geometrically-Bounded FM (GBFM). GBFM is applied on a local basis to windows encompassing a 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 stops participating. 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 wherein, for a first cluster, said placing circuit elements by cluster includes repeatedly placing circuit elements from said first cluster in to a centralized bin until the centralized bin reaches capacity and placing remaining circuit elements from said first cluster into a bin which is located in a predetermined spiral order to the centralized bin until all circuit elements of said first cluster have been placed;

defining a continuous region specified by said bins; and

applying a placement refinement technique to said continuous region to produce a placement that is improved 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 a predetermined number of gates.

10. The method of claim 9, wherein said predetermined number of gates is less than thirty.

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 including the steps of:

creating a first planar subgraph;

creating a second planar subgraph;

repeating the preceding steps until all the nets have been removed.