Placement method for integrated circuit design using topo-clustering

• US 6,961,916 B2
• Filed: 05/01/2002
• Issued: 11/01/2005
• Est. Priority Date: 06/12/1998
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Yeap, Gary K., Taraporevala, Feroze Peshotan, Yamamoto, Dennis, Shieh, Lilly, Chakraborty, Abhijeet, Sarrafzadeh, Majid, Boyle, Douglas B., Raje, Salil R., Malik, Sharad, Pileggi, Lawrence
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US10/136,161
• Publication Number:
  US 20020138816A1
• Time in Patent Office: 1,280 Days
• Field of Search: 716 1- 18
• US Class Current: 716/123
• 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 refining placement of integrated circuit elements utilizing a plurality of bins, comprising:

defining first window encompassing a number of said bins;

partitioning and reapportioning circuit elements among bins within the first window so as to decrease a first window, said reapportioning circuit elements among bins within the first window includes performing cluster-level moves among bins and then performing gate level moves among bins;

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

partitioning and reapportioning circuit elements among bins within the second window so as to decrease a cost function calculated over the bins within the second window.

2. The method of claim 1, wherein performing cluster-level moves comprises exchanging clusters of circuit elements between bins and performing gate level moves comprises exchanging selected circuit elements between bins.

3. The method of claim 1, wherein reapportioned circuit elements among bins within the second window includes performing cluster-level moves among bins and then performing gate level moves among bins.

4. A method of refining placement of integrated circuit elements utilizing a plurality of bins, comprising:

(a) defining a first window encompassing a number of said bins;

(b) reapportioning circuit elements among bins within the first window so as to decrease a cost function calculated over the bins within the first window, wherein said reapportioning circuit elements among bins within the first window includes performing cluster-level moves among bins and then performing gate level moves among bins;

(c) defining a second window having at least one bin in common with said first window;

(d) reapportioning circuit elements among bins within the second window so as to decrease a cost function calculated over the bins within the second window;

(e) performing quadrisection of said bins; and

(f) repeating steps (a)-(d) after performing quadrisection of said bins, wherein a size of said first window is decreased at a successive level of quadrisection.

5. A method of refining placement of integrated circuit elements utilizing a plurality of bins, comprising:

grouping topologically-related circuit elements into a plurality of clusters, wherein each of said clusters is placed into one of said bins;

defining a first window encompassing a number of said bins, wherein a size of said first window is determined from an analysis of said clusters;

reapportioning circuit elements among bins within the first window so as to decrease a cost function calculated over the bins within the first window, wherein said reapportioning circuit elements among bins within the first window includes performing cluster-level moves among bins and then performing gate level moves among bins;

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

reapportioning circuit elements among bins within the second window so as to decrease a cost function calculated over the bins within the second window.

6. The method of claim 5, wherein a size of said first window is determined from an analysis of said clusters by determining whether said clusters include a large number of disconnected clusters.

7. The method of claim 6, wherein the size of said first window is small when there is a large number of disconnected clusters.