Boots – shoes – and leggings
Patent
1996-03-01
1998-08-18
Louis-Jacques, Jacques H.
Boots, shoes, and leggings
364490, 364148, 395500, G06F 1750
Patent
active
057966257
ABSTRACT:
A cell placement for an integrated circuit chip is divided into two "chessboard" patterns or "jiggles". Each pattern resembles a chessboard in that it consists of alternating regions of different types or "colors" such that no region of a given color has an edge common with another region of the same color. The jiggles are offset relative to each other such that the regions of one jiggle partially overlap at least two regions of the other jiggle. Simulated annealing is performed sequentially for each color of each jiggle. During each operation, a plurality of parallel processors operate on the regions simultaneously using a previous copy of the entire chip, with one processor being assigned to one or more regions. At the end of each operation, the copy of the chip is updated. The chessboard patterns eliminate unproductive cell moves resulting from adjacent regions having a common edge. The jiggles enable cells to move to their optimal positions from their initial region to any other region on the chip. The regions can have rectangular, triangular or hexagonal shapes. An initial temperature for the actual simulated annealing operation is determined by performing simulated annealing without cell swaps with different temperature, and selecting the temperature at which a cost function such as total wirelength does not significantly change.
REFERENCES:
patent: 4495559 (1985-01-01), Gellatt, Jr. et al.
patent: 5187668 (1993-02-01), Okude et al.
patent: 5475608 (1995-12-01), Masuoka
patent: 5495419 (1996-02-01), Rostoker et al.
VLSI Cell Placement Techniques, K. Shahookar and P. Mazumder, ACM Computing Surveys vol. 23, No. 2, Jun. 1991.
TimberWolf 3.2: A New Standard Cell Placement and Global Routing Package, C. Sechen and A. Sangiovanni-Vincentelli, IEEE 23rd Design Automation Conf., 1986, Paper 26.1.
Placement of Standard Cells Using Simulated Annealing on the Connection Machine, A. Casotto and A. Sangiovanni-Vincentelli, IEEE, 1987.
A Loosely Coupled Parallel Algorithm for Standard Cell Placement, W. Sun and C. Sechen, ACM 1994.
Parallel Standard Cell Placement Algorithms with Quality Equivalent to Simulated Annealing, J.S. Rose, W.M. Snelgrove and Z.G. Vranesic, IEEE Transactions on Computer-Aided Design, vol. 7, No. 3, Mar. 1988.
Performance of a Parallel Algorithm for Standard Cell Placement on the Intel Hypercube, M. Jones and P. Banerjee, 24th ACM/IEEE Design Automation Conf., 1987, Paper 42.3.
A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells, A. Casotto, F. Romeo and A. Sangiovanni-Vincentelli, Dept. Elect. Eng. & Computer Science, U.C.B.
ProperPlace: A Portable Parallel Algorithm for Standard Cell Placement, S. Kim, J.A. Chandy, S. Parkes, B. Ramkumar, P. Banerjee, IEEE 1994.
A Cell-Replicating Approach to Mincut-Based Circuit Partitioning, C. Kring and A.R. Newton, IEEE, 1991.
Siarry et al., "Thermodynamic Optimization of Block Placement," IEEE, 1987, pp. 211-221.
Rose et al., "Temperature Measurement and Equilibrium Dynamics of Simulated Annealing placements," IEEE, 1990, pp. 253-259.
Hong et al., "Parallel Error Tolerance Scheme Based on the Hill Climbing Nature of Simulated Annealing," IEEE, 1992, pp. 685-688.
Andreev Alexander E.
Koford James S.
Pavisic Ivan
Scepanovic Ranko
Louis-Jacques Jacques H.
LSI Logic Corporation
Phan Thai
LandOfFree
Physical design automation system and process for designing inte does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Physical design automation system and process for designing inte, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Physical design automation system and process for designing inte will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1121196