Boots – shoes – and leggings
Patent
1994-10-05
1997-10-28
Teska, Kevin J.
Boots, shoes, and leggings
364491, 395500, 257208, 326 41, G06F 1750
Patent
active
056823215
ABSTRACT:
A large number of microelectronic circuit cells that are interconnected by a set of wiring nets are optimally placed on an integrated circuit chip such that all interconnects can be routed and the total wirelength of the interconnects is minimized. Cells are first grouped into disjoint clusters by an optimization-driven clustering technique, which uses both local and global connectivity information among the cells. This technique uses Rent's rule for combining pairs of neighboring clusters, and selects among pairs of clusters having the same Rent's exponent using distance information derived from global optimization processing. Clusters are prevented from growing to an excessive size by limiting the number of cells per cluster and the maximum area per cluster to predetermined maximum values. After the clusters are generated, they are placed using an optimization-driven placement technique, preferably "Gordian". Finally, the cells within each cluster are de-clustered and locally placed using a partitioning technique, preferably "min-cut".
REFERENCES:
patent: 5140402 (1992-08-01), Murakata
patent: 5222031 (1993-06-01), Kaida
patent: 5224056 (1993-06-01), Chene et al.
patent: 5224057 (1993-06-01), Igarashi et al.
patent: 5341308 (1994-08-01), Mendel
C. Ding, C. Ho and M.J. Irwin, "A New Optimization Driven Clustering Algorithm for Large Circuits," ACM/SIGDA Physical Design Workshop, pp. 13-19, Sep. 1993.
C. Fiduccia and R. Mattheyses, "A Linear-Time Heuristic For Improving Network Partitions," DAC, pp. 175-181, Jun. 1982.
J. Garbers, H.J. Promel and A. Stenger, "Finding Clusters in VLSI Circuits," ICCAD, pp. 520-523, Nov. 1990.
L. Hagen and A.B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering," UCLA CS Dept. TR-019973, Oct. 1991.
J.M. Kleinhans, G. Sigl, F.M. Johannes and K.J. Antreich, "Gordian: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans. on CAD, pp. 356-365, Mar. 1991.
B.W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Technical Journal, 49(2), pp. 291-307, Feb. 1970.
U. Lauther, "A Min-Cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation," DAC, pp. 1-10, Jun. 1976.
T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, J. Wiley, 1990.
R.M. Ling and P. Banerjee, "Optimization by Simulated Evolution with Application to Standard Cell Placement," DAC, pp. 20-25, Jun. 1990.
Mallela and L.K. Grover, "Clustering Based Simulated Annealing for Standard Cell Placement," DAC, pp. 312-317, Jun. 1988.
T. Ng, J. Oldfield and V. Pitchumani, "Improvements of a Mincut Partition Algorithm," ICCAD, pp. 470-473, Nov. 1987.
B. Preas and M. Lorenzetti, Physical Design Automation of VLSI Systems, Benjamin/Cummings, 1988.
C. Sechen and K.W. Lee, "An Improved Simulated Annealing Algorithm for Row-Based Placement," ICCAD, pp. 4578-481, Nov. 1987.
R.S. Tsay, E.S. Kuh and C.P. Hsu, "Proud: a Fast Sea-of-Gate Placement Algorithm," DAC, pp. 318-323, Dec. 1988.
Ding Cheng-Liang
Irwin Mary Jane
Wang Ting-Chi
LSI Logic Corporation
Nguyen Tan
Teska Kevin J.
LandOfFree
Cell placement method for microelectronic integrated circuit com does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cell placement method for microelectronic integrated circuit com, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell placement method for microelectronic integrated circuit com will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1030002