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. Initial placement and placement refinement may be
performed hierarchically using topocluster trees. A topocluster tree may
be used to drive initial placement. An iterative placement refinement
process then follows, using a technique referred to herein as
Geometrically-Bounded FM (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.
During placement refinement using GBFM, cluster size is adjusted
iteratively from large to small as determined by horizontal cuts within
the topocluster tree. 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.
Topocluster trees may also be used for quadrisection. Following the
foregoing global placement process, the circuit is then ready for detailed
placement in which cells are assigned to placement rows.
