Placement method for integrated circuit design using topo-clustering

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. 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.