Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-06-12
2002-08-27
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06442743
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to placement in integrated circuit design.
2. State of the Art
The physical design of integrated circuits involves placement of gates within a design layout, representing a physical integrated circuit, and routing of interconnections (nets) between gates. The logical integrated circuit design is represented in the form of a netlist, i.e., a list of gates or collections of gates (macros) and nets interconnecting them. A graph representation of a netlist is shown in FIG.
1
A. Through placement and routing, the logical integrated circuit design is translated to a physical integrated circuit design. Placement and routing are performed using Electronic Design Automation (EDA) software tools running on powerful computers.
Placement and routing are closely inter-related. As integration density increases, the sheer size of integrated circuit designs challenges current methods of physical design. Furthermore, physical design is required to be more exacting in order to avoid deleterious interactions and to ensure that all design constraints are met.
A number of approaches to the placement problem have been proposed, including simulated annealing, genetic algorithms, mathematical/linear programming, bisection type approaches, etc. One widely-practiced partitioning algorithm known as FM after its originators Fiduccia and Matheyses, is used as the basis for many placement algorithms. In FM, groups of features are formed, and features are exchanged between the groups so as to minimize the number of nets extending between the groups. The FM technique, an example of a module partitioning heuristic, may be represented as follows:
1. Determine initial partition of modules.
2. Loop until no more improvement in the partition results, or until a maximum number of passes is tried:
a. Free all modules and compute module gains.
b. Loop while there remains a free module that can be moved:
i. Select next module to be moved (select free module of maximum gain, subject to area-balance criterion).
ii. Move selected module to opposite side of partition.
iii. Update module gains.
c. Reconstruct best partition of pass.
Gain refers to decrease in the number of nets crossing between opposite sides of the partition.
A major shortcoming of the foregoing technique, as well as other similar techniques, is that after a partition has been made, it is difficult or impossible for gates or modules to cross the partition boundary. This restriction often results in inferior placements. A cycling and overlapping partitioning process is described in Huang and Kahng, Partitioning-Based Standard Cell with an Exact Objective,
Proc. of the International Symposium on Physical Design,
April 1997. This approach, to a limited extent, does allow gates and modules to cross partition boundaries. However, the approach is not cluster-based (is slow) and does not exploit the full power of cycling and overlapping partitioning (produces less-than-adequate quality).
In short, none of these existing placement techniques appears well-equipped to meet the challenges of the deep sub-micron era.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 5491641 (1996-02-01), Scepanovic et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5526517 (1996-06-01), Jones et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5661663 (1997-08-01), Scepanovic et al.
patent: 5682321 (1997-10-01), Ding et al.
patent: 5682322 (1997-10-01), Boyle et al.
patent: 5699265 (1997-12-01), Scepanovic et al.
patent: 5712793 (1998-01-01), Scepanovic et al.
patent: 5748844 (1998-05-01), Marks
patent: 5838585 (1998-11-01), Scepanovic et al.
patent: 5854752 (1998-12-01), Agarwal
patent: 5903461 (1999-05-01), Rostoker et al.
patent: 5909376 (1999-06-01), Scepanovic et al.
patent: 5955776 (1999-09-01), Ishikawa
patent: 6030110 (2000-02-01), Scepanovic et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
Fiduccia et al., “A Linear-Time Heuristic for Improving Network Partitions”,IEEE 19thDesign Automation Conference, pp. 175-181 (1982).
Huang et al., “Partitioning-Based Standard-Cell Global Placement With an Exact Objective”,International Symposium on Physical Design, pp. 18-25, ACM (1997).
Kernighan et al., “An Efficient Heuristic Procedure for Partitioning Graphs”,Bell System Technical Journal, 49:291-307 (1970).
Kleinhans et al., “Gordian: VLSI Placement by Quadratic Programming and Slicing Optimization”,IEEE Transactions on Computer-Aided Design, 10(3):356-365 (1991).
Sarrafzadeh et al., “NRG: Global and Detailed Placement”,IEEE International Conference on Computer-Aided Design, pp. 532-537 (1997).
Suaris et al., “Quadrisection: A New Approach to Standard Cell Layout”,IEEE International Conference on Computer-Aided Design, pp. 474-477 (1987).
Boyle Douglas B.
Chakraborty Abhijeet
Malik Sharad
Pileggi Lawrence
Raje Salil R.
Harmon & DeNiro LLP
Monterey Design Systems
Siek Vuthe
Vierra Magen Marcus
LandOfFree
Placement method for integrated circuit design using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Placement method for integrated circuit design using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Placement method for integrated circuit design using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2951333