Boots – shoes – and leggings
Patent
1994-09-13
1997-04-08
Teska, Kevin J.
Boots, shoes, and leggings
364491, 364489, 364488, G06F 1500
Patent
active
056194196
ABSTRACT:
A method of cell placement for an integrated circuit chip includes performing a chaotic improvement operation on an initial cell placement. At least some of the cells are relocated to new locations that provide lower interconnect wirelength and congestion. For each cell, the centroid of the net of cells to which the cell is connected is computed. The cell is then moved toward the centroid by a distance that is equal to the distance from the current position of the cell to the centroid multiplied by a "chaos" factor .lambda.. The value of .lambda. is selected such that the cell relocation operations will cause the placement to converge toward an optimal configuration without chaotic diversion, but with a sufficiently high chaotic element to prevent the optimization operation from becoming stuck at local fitness maxima. The chaotic placement operation can generate illegal placements in which two or more cells can occupy one location, some locations can contain no cells and/or two or more cells can partially overlap. Cell overlap is reduced and the spatial distribution of the placement improved by computing a density map representing cell densities in incremental blocks of the placement respectively, computing, from the density map, a warp map representing first repulsive forces exerted at centers of said blocks by cell densities in surrounding blocks respectively, interpolating, from the warp map, second repulsive forces acting on selected cells in the placement and spatially distributing the selected cells in accordance with the second repulsive forces. Overlapping cells are then moved away from each other by a separate cell-to-cell repulsive force based on cell overlap to reduce any remaining overlap. The chaotic placement and spatial distribution phases are repeated, with the scale of movement for chaotic placement being progressively decreased and the scale of movement for spatial distribution being progressively increased. A final phase is then performed in which only the cell-to-cell repulsive force is used to eliminate the remaining overlap.
REFERENCES:
patent: 4593363 (1986-06-01), Burstein et al.
patent: 5191542 (1993-03-01), Murofushi
patent: 5208764 (1993-05-01), Rusu et al.
patent: 5225991 (1993-07-01), Dougherty
patent: 5341308 (1994-08-01), Mendel
patent: 5349536 (1994-09-01), Ashtaputre et al.
patent: 5363313 (1994-11-01), Lee
patent: 5475608 (1995-12-01), Masuoka
patent: 5495419 (1996-02-01), Rostoker et al.
Wipfler, M. Wiesel and Mlynski, D.A., A Combined Force and Cut Algorithm for Hierarchical VLSI Layout; Design Automation Conference, 1982 Jan. 1982.
Friedman, M., McDonald, Donlan, LT.B., McDonald, J. and Brooksbank, D.; The R.P.I. Wafer Scale Integration Silicon Compiler; International Conference on Computer Design, Jan. 1984.
Odowara, G., Hiraide, T. and Nishina, O.; Partitioning and Placement Technique for CMOS Gate Arrays; Transactions on Computer Aided Design, Jan. 1987.
Murofushi, M., Yamada, M., and Mitsuhashi, T.; FOLM-planner: A New Floorplanner with a Frame Overlapping Floorplan Model Suitable for SOG (Sea of Gates) Type Gate Arrays; International Conference on Computer Aided Design, Jan. 1990.
Boyle Douglas B.
D'Haeseleer Patrik
Louis-Jacques Jacques
LSI Logic Corporation
Teska Kevin J.
LandOfFree
Method of cell placement for an itegrated circuit chip comprisin 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 of cell placement for an itegrated circuit chip comprisin, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of cell placement for an itegrated circuit chip comprisin will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2401300