Method and system for placing cells using quadratic placement and a spanning tree model
First Claim
1. A computer controlled method for placing cells of an integrated circuit design represented as an unplaced netlist comprising the computer implemented steps of:
- (a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net;
(b) performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist;
(c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist;
(d) generating second connectivity matrices for each multi-pin net of said netlist utilizing said spanning tree connectivity relationships wherein said second connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and
(e) performing said global quadratic optimization based placement on said design utilizing said second connectivity matrices to produce a placed netlist.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method for placement of elements within an integrated circuit design using a spanning tree model and a quadratic optimization based placement. The system utilizes a conjugate-gradient quadratic formula based placement system (e.g., GORDIAN) which inputs an integrated circuit design in a netlist form and generates a connectivity matrix for each multi-pin net within the design. The quadratic placement system performs global optimization using a conjugate gradient solution to minimize wire lengths of cells in nets. Partitioning is also performed. The system and method herein utilizes a clique model of a multi-pin net to generate first connectivity matrices for the multi-pin nets which are run through the global optimization processes. This first run provides a rough placement of the elements of the multi-pin nets. A spanning tree process is then run on the initial cell placement and subsequent connectivity matrices are constructed using the spanning tree model, not the clique model for multi-pin nets within a defined size range. Although biased toward the initial placement, the overall placement process as described herein is more physically realistic and efficient using the spanning tree model which requires much less data for storage and processing thus allowing faster convergence. A placed netlist is the product.
-
Citations
20 Claims
-
1. A computer controlled method for placing cells of an integrated circuit design represented as an unplaced netlist comprising the computer implemented steps of:
-
(a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist; (d) generating second connectivity matrices for each multi-pin net of said netlist utilizing said spanning tree connectivity relationships wherein said second connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) performing said global quadratic optimization based placement on said design utilizing said second connectivity matrices to produce a placed netlist. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer controlled method for placement of cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said method comprising the computer implemented steps of:
-
(a) placing said cells of said netlist utilizing connectivity relationships based on clique models that represent spatial affinities for cells of multi-pin nets of said design and generating a rough placement of said cells; and (b) performing second and subsequent processes on said cells of said netlist to determine and revise a second placement of said cells of said netlist, said step (b) comprising the further steps of; (1) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in said rough placement of said cells of said netlist; (2) placing said cells of said netlist utilizing said spanning tree connectivity relationships to represent spatial affinities for cells of said multi-pin nets wherein said spanning tree connectivity relationships require less memory for storage than said connectivity relationships based on clique models; (3) revising said spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations determined in step (2); and (4) repeating steps (2) and (3) until a final placed netlist is performed. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A computer system including a processor coupled to bus and a memory unit coupled to said bus, said system programmed to include placement logic for placing cells of an integrated circuit design represented as an unplaced netlist having cells and connections between cells, said placement logic comprising:
-
(a) first matrix logic generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; (b) first placement logic coupled to said first matrix logic performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist; (c) spanning tree logic generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing spanning tree procedures on said multi-pin nets utilizing cell locations of said rough placement -of said cells of said netlist; (d) second matrix logic coupled to said spanning tree logic and generating second and subsequent connectivity matrices for each multi-pin net utilizing said spanning tree connectivity relationships wherein said second and subsequent connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and (e) second placement logic performing said global quadratic optimization based placement utilizing said second and subsequent connectivity matrices to produce a placed netlist. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification