1997-02-11
2000-05-23
Teska, Kevin J.
G06F 1750
Patent
active
060674091
ABSTRACT:
A system for determining an affinity associated with relocating a cell located on a surface of a semiconductor chip to a different location on the surface is disclosed herein. Each cell may be part of a cell net containing multiple cells. The system initially defines a bounding box containing all cells in the net which contains the cell. The system then establishes a penalty vector based on the bounding box and borders of a region containing the cell, computes a normalized sum of penalties for all nets having the cell as a member, and calculates the affinity based on the normalized sum of penalties. Also included in the disclosed system are methods and apparatus for capacity and utilization planning of the use of the floor, or the surface area, and the methods and apparatus for parallelizing the process of affinity based placements using multiple processors. Finally, method and apparatus for connecting the cells based on a Steiner Tree method is disclosed.
REFERENCES:
patent: 3603771 (1971-09-01), Isett
patent: 3617714 (1971-11-01), Kernighan
patent: 4306286 (1981-12-01), Cocke et al.
patent: 4342090 (1982-07-01), Caccoma et al.
patent: 4484292 (1984-11-01), Hong et al.
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 4554625 (1985-11-01), Otten
patent: 4577276 (1986-03-01), Dunlop et al.
patent: 4593363 (1986-06-01), Burnstein et al.
patent: 4612618 (1986-09-01), Pryor et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4624339 (1986-11-01), Wagner et al.
patent: 4630219 (1986-12-01), Digiacomo et al.
patent: 4656580 (1987-04-01), Hitchcock, Sr. et al.
patent: 4675829 (1987-06-01), Clemenson
patent: 4686629 (1987-08-01), Noto et al.
patent: 4688072 (1987-08-01), Heath et al.
patent: 4697242 (1987-09-01), Holland et al.
patent: 4754408 (1988-06-01), Carpenter et al.
patent: 4763288 (1988-08-01), Deering et al.
patent: 4815003 (1989-03-01), Putatunda et al.
patent: 4829446 (1989-05-01), Draney
patent: 4831725 (1989-05-01), Dunham et al.
patent: 4850027 (1989-07-01), Kimmel
patent: 4872125 (1989-10-01), Catlin
patent: 4908772 (1990-03-01), Chi
patent: 4910680 (1990-03-01), Hiwatashi
patent: 4918614 (1990-04-01), Modarres et al.
patent: 4961152 (1990-10-01), Davis
patent: 4965739 (1990-10-01), Ng
patent: 5051895 (1991-09-01), Rogers
patent: 5051938 (1991-09-01), Hyduke
patent: 5062054 (1991-10-01), Kawakami et al.
patent: 5119313 (1992-06-01), Shaw et al.
patent: 5124927 (1992-06-01), Hopewell et al.
patent: 5136686 (1992-08-01), Koza
patent: 5140402 (1992-08-01), Murakata
patent: 5140526 (1992-08-01), McDermith
patent: 5140530 (1992-08-01), Guha et al.
patent: 5144563 (1992-09-01), Date et al.
patent: 5157778 (1992-10-01), Bischoff et al.
patent: 5159682 (1992-10-01), Toyonaga et al.
patent: 5187668 (1993-02-01), Okude et al.
patent: 5191542 (1993-03-01), Murofishi
patent: 5200908 (1993-04-01), Date et al.
patent: 5202840 (1993-04-01), Wong
patent: 5208759 (1993-05-01), Wong
patent: 5218551 (1993-06-01), Agrawal et al.
patent: 5222029 (1993-06-01), Hooper et al.
patent: 5222031 (1993-06-01), Kaida
patent: 5224056 (1993-06-01), Chene et al.
patent: 5224057 (1993-06-01), Igarashi et al.
patent: 5225991 (1993-07-01), Dougherty
patent: 5231590 (1993-07-01), Kumar et al.
patent: 5239465 (1993-08-01), Hattori et al.
patent: 5245550 (1993-09-01), Miki et al.
patent: 5249259 (1993-09-01), Harvey
patent: 5251147 (1993-10-01), Finnerty
patent: 5255345 (1993-10-01), Shaefer
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5267177 (1993-11-01), Sato et al.
patent: 5303161 (1994-04-01), Burns et al.
patent: 5309371 (1994-05-01), Shikata et al.
patent: 5341308 (1994-08-01), Mendel
patent: 5349536 (1994-09-01), Ashtaputre et al.
patent: 5363313 (1994-11-01), Lee
patent: 5392222 (1995-02-01), Noble
patent: 5398195 (1995-03-01), Kim
patent: 5404313 (1995-04-01), Shiohara et al.
patent: 5404561 (1995-04-01), Castelaz
patent: 5465218 (1995-11-01), Handa
patent: 5491641 (1996-02-01), Scepanovic et al.
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5521837 (1996-05-01), Frankle et al.
patent: 5557533 (1996-09-01), Koford et al.
patent: 5568322 (1996-10-01), Azami et al.
patent: 5568636 (1996-10-01), Koford
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5587923 (1996-12-01), Wang
patent: 5590063 (1996-12-01), Golio et al.
patent: 5615128 (1997-03-01), Scepanovic et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5638292 (1997-06-01), Ueda
patent: 5638293 (1997-06-01), Scepanovic et al.
patent: 5640327 (1997-06-01), Ting
patent: 5661663 (1997-08-01), Scepanovic et al.
patent: 5682321 (1997-10-01), Ding et al.
patent: 5682322 (1997-10-01), Boyle et al.
patent: 5694602 (1997-12-01), Smith
patent: 5699265 (1997-12-01), Scepanovic et al.
patent: 5712793 (1998-01-01), Scepanovic et al.
patent: 5742510 (1998-04-01), Rostoker et al.
patent: 5745363 (1998-04-01), Rostoker et al.
patent: 5757657 (1998-05-01), Hathaway et al.
patent: 5798936 (1998-08-01), Cheng
patent: 5858143 (1999-08-01), Fournier
Rose, et al., "Parallel Standard Cell Placement Algorithms with Quality Equivalent to Simulated Annealing," 1988 IEEE, IEEE Transactions on Computer Aided Design, vol. 7, No. 3, Mar. 1988, pp. 387-396.
Sanchis, Laura, "Multiple-Way Network Partitioning," 1989 IEEE, IEEE Transactions on Computers, vol. 38, No. 1, Jan. 1989, pp. 62-81.
King, et al., "ESP: Placement by Simulated Evolution," 1989 IEEE, IEEE Transactions on Computer-Aided Design, vol. 8, No. 3, Mar. 1989, pp. 245-256.
Adachi, et al., "A Parallel Implementation of Nonlinear Steady State Analysis Based on Time-Domain Newton-Raphson Algorithm," 1989 IEEE, IEEE International Symposium on Circuits and Systems, vol. 2, pp. 889-892.
Schulz, U., "Hierarchical Physical Design System," 1989 IEEE, IEEE Comput. Soc. Press, pp. 5/20-5/24.
Banerjee, et al., "Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube Multi1processors," 1990 IEEE, IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 1, Jan. 1990, pp. 91-106.
Qian, et al., "Load Balancing on Generalized Hypercube and Mesh Multiprocessors with LAL," 1991 IEEE, 11th International Conference on Distributed Computing Systems, May 20-24, 1991, pp. 402-409.
Mayrhofer, et al., "Congestion-Driven Placement Using a New Multi-Partitioning Heuristic," 1990 IEEE, 1990 International Conference on Computer-Aided Design, pp. 332-335.
Bapat, et al., "Sharp-Looking Geometric Partitioning," 1991 IEEE, 1991 European Design Automation Conference, pp. 172-176.
Wu, et al., "Glue-Logic Partitioning for Floorplans with A Rectilinear Datapath," 1991 IEEE, Proceedings of the European Conference on Design Automation, pp. 162-166.
Chen, et al., "A Fast Parallel Algorithm for Slicing Floorplans," 1993 IEEE, 1993 IEEE International Symposium on Circuits and Systems, vol. 3, May 3-6, 1993, pp. 1774-1777.
Ganley, et al., "Thumbnail Rectilinear Steiner Trees," 1995 IEEE, VLSI 1995 5th Great Lakes Symposium, pp. 46-49.
Scherber, et al., "Palace: A Parallel and Hierarchical Layout Analyzer and Circuit Extractor," 1996 IEEE, Proceedings on European Design and Test Conference, Mar. 11-14, 1996, pp. 357-361.
Tragoudas, S., "Min-Cut Partitioning on Underlying Tree and Graph Structures," 1996 IEEE, IEEE Transactions on Computers, vol. 45, No. 4, Apr. 1996, pp. 470-474.
Chandy, et al., "A Parallel Circuit-Partitioned Algorithm for Timing Driven Cell Placement," 1997 IEEE, Proceedings on International Conference on Computer Design, Jan. 1, 1997, pp. 621-627.
John A. Chandy and Prithviraj Banerjee, "A Parallel Circuit-Partitioned Algorithm for Timing Driven Cell Placement," International Conference on Computer Design, 1997.
Laura A. Sanchis, "Multiple-Way Network Partitioning," IEEE Transactions on Computers, vol. 38, No. 1, Jan. 1989.
Minshine Shih and Ernest S. Kuh, "Circuit Partitioning Under Capacity and I/O Constraints," IEEE Custom Integrated Circuits Conference, 1994.
Laura A. Sanchis, "Multiple-Way Network Partitioning with Different Cost Functions," IEEE Transactions on Computers, vol. 42, Iss. 12, pp. 1500-1504, Dec. 1993.
Xiaoshu Qian and Qing Yang, "Load Balancing on
Andreev Alexander E.
Jones Edwin
Koford James S.
Pavisic Ivan
Scepanovic Ranko
Do Thuan
LSI Logic Corporation
Teska Kevin J.
LandOfFree
Advanced modular cell placement system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Advanced modular cell placement system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Advanced modular cell placement system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1842713