Method and system for placing cells using quadratic placement an

Details Method and system for placing cells using quadratic placement an Method and system for placing cells using quadratic placement an

1996-05-23

1998-10-06

Trans, Vincent N.

Boots, shoes, and leggings

364489, G06F 1750

Patent

active

058187294

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.

REFERENCES:
patent: 4908772 (1990-03-01), Chi
patent: 4918614 (1990-04-01), Modarres et al.
patent: 5119317 (1992-06-01), Narikawa et al.
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5309370 (1994-05-01), Wong
patent: 5349536 (1994-09-01), Ashtaputre et al.
patent: 5566078 (1996-10-01), Ding et al.
patent: 5638293 (1997-06-01), Scepanovic et al.
Kleinhans et al., "Gordian: VLSI Placement by Quadratic Programming and Slicing Optimization", Mar. 1991 IEEE Transactions on Computer-Aided Design vol. 10 No. 3.
Dunlop et al., "A Procedure for Placement of Standard-Cell VLSI Circuits", Jan. 1985 IEEE Transactions on Computer-Aided Design vol. CAD-4 No. 1.
Tsay et al., "Proud: A Fast Sea-of-Gates Placement Algorithm", 1988 25th ACM/IEEE Design Automation Conference, Paper 22.3.
Liang et al., "NC Algorithms for Finding Depth-First-Search Trees in Interval Graphs and Circular-Arc Graphs", IEEE, 1991, pp. 582-585.
Elias Dahlaus, "Efficient Parallel Algorithms on Chordal Graphs with a Sparse Tree Representation", IEEE, 1994, pp. 150-158.

Affiliated with

Also associated with

Rating

Method and system for placing cells using quadratic placement an does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for placing cells using quadratic placement an, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for placing cells using quadratic placement an will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-86080