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.