Computer-aided design and analysis of circuits and semiconductor – Integrated circuit design processing – Physical design processing
Reexamination Certificate
2008-06-16
2011-11-29
Kik, Phallaka (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Integrated circuit design processing
Physical design processing
C716S123000, C716S124000
Reexamination Certificate
active
08069429
ABSTRACT:
A detailed placement process which optimizes cell placement with up to one hundred percent densities in a linear run time. The output from a conjugate-gradient coarse placement process is input to the detailed placement process. A dynamic programming technique is used to optimize cell placement by swapping cells between two or more rows. The search space is pruned beforehand. A greedy cleanup phase using an incremental row placer is used. Thereby, the detailed placement process handles congestion driven placements characterized by non-uniform densities expeditiously and efficiently.
REFERENCES:
patent: 4742471 (1988-05-01), Yoffa et al.
patent: 5311443 (1994-05-01), Crain et al.
patent: 5619419 (1997-04-01), D'Haeseleer et al.
patent: 5682321 (1997-10-01), Ding et al.
patent: 5726903 (1998-03-01), Kerzman et al.
patent: 5798936 (1998-08-01), Cheng
patent: 5801959 (1998-09-01), Ding et al.
patent: 5818729 (1998-10-01), Wang et al.
patent: 5825661 (1998-10-01), Drumm
patent: 5903461 (1999-05-01), Rostoker et al.
patent: 5963455 (1999-10-01), Scepanovic et al.
patent: 5974245 (1999-10-01), Li et al.
patent: 6014506 (2000-01-01), Hossain et al.
patent: 6026223 (2000-02-01), Scepanovic et al.
patent: 6080201 (2000-06-01), Hojat et al.
patent: 6080204 (2000-06-01), Mendel
patent: 6086631 (2000-07-01), Chaudhary et al.
patent: 6091892 (2000-07-01), Xue et al.
patent: 6099583 (2000-08-01), Nag
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6223332 (2001-04-01), Scepanovic et al.
patent: 6230304 (2001-05-01), Groeneveld et al.
patent: 6249902 (2001-06-01), Igusa et al.
patent: 6282693 (2001-08-01), Naylor et al.
patent: 6282694 (2001-08-01), Cheng et al.
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 6292929 (2001-09-01), Scepanovic et al.
patent: 6321366 (2001-11-01), Tseng et al.
patent: 6360356 (2002-03-01), Eng
patent: 6370673 (2002-04-01), Hill
patent: 6378114 (2002-04-01), Shenoy et al.
patent: 6381731 (2002-04-01), Grodd
patent: 6385758 (2002-05-01), Kikuchi et al.
patent: 6442743 (2002-08-01), Sarrafzadeh et al.
patent: 6446239 (2002-09-01), Markosian et al.
patent: 6449761 (2002-09-01), Greidinger et al.
patent: 6553338 (2003-04-01), Buch et al.
patent: 6594811 (2003-07-01), Katz
patent: 6671859 (2003-12-01), Naylor et al.
patent: 6701289 (2004-03-01), Garnett et al.
patent: 6756242 (2004-06-01), Regan
patent: 6961916 (2005-11-01), Sarrafzadeh et al.
patent: 6971080 (2005-11-01), Grodd
patent: 7065729 (2006-06-01), Chapman
patent: 2001/0003843 (2001-06-01), Scepanovic et al.
patent: 2001/0010090 (2001-07-01), Boyle et al.
patent: 2002/0059553 (2002-05-01), Eng
patent: 2002/0138816 (2002-09-01), Sarrafzadeh et al.
patent: 2004/0107408 (2004-06-01), Sano et al.
Koide et al. (“A new performance driven placement method with the Elmore delay model for row based VLSIs”, Proceedings of the 1995 ASP-DAC Design Automation Conference, Aug. 29, 1995, pp. 405-412).
Kahng et al. (“Optimization of linear placements for wirelength minimization with free sites”, Proceedings of the ASP-DAC '99 Asia and South Pacific Design Automation Conference, Jan. 18, 1999, vol. 1, pp. 241-244).
Chin et al. (“Interior point methods for placement”, 1994 IEEE International Symposium on Circuits and Systems, ISCAS '94, vol. 1, May 30, 1994, pp. 169-171).
Venkateswaran et al. (“Clock-skew constrained placement for row based designs”, Proceedings of 1998 International Conference on Computer Design: VLSI in Computers and Processors, Oct. 5, 1998, pp. 219-220).
Chowdhury (“Analytical approaches to the combinatorial optimization in linear placement problems”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, No. 6, Jun. 1989, pp. 630-639).
Yang et al. (“HALO: an efficient global placement strategy for standard cells”, IEEE Transactions on Computer-Aided Design Integrated Circuits and Systems, vol. 11, No. 8, Aug. 1992, pp. 1024-1031).
Hamada et al. (“An efficient multilevel placement technique using hierarchical partitioning ”, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 39, No. 6, Jun. 1992, pp. 432-439).
Kim et al. (“Combined hierarchical placement algorithm for row-based layouts”, Electronics Letters, vol. 29, No. 17, Aug. 19, 1993, pp. 1508-1510).
Doll et al. (“Iterative placement improvement by network flow methods”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 10, Oct. 1994, pp. 1189-1200).
Tsay et al. (“A row-based cell placement method that utilizes circuit structural properties”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 3, Mar. 1995, pp. 393-397).
Hossain et al. (“A new faster algorithm for iterative placement improvement”, Proceedings of Sixth Great Lakes Symposium on VLSI, Mar. 22, 1996, pp. 44-49).
Tianming et al. (“VEAP: Global optimization based efficient algorithm for VLSI placement”, Proceedings of the 1997 ASP-DAC Asia and South Pacific Design Automation Conference, Jan. 28, 1997, pp. 277-280).
Koide et al. (“Par-POPINS: a timing-driven parallel placement method with the Elmore delay model for row based VLSIs”, Proceedings of the ASP-DAC '97 Asia and South Pacific Design Automation Conference, Jan. 28, 1997, pp. 133-140).
Kleinhans et al. (“GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization”, IEEE Transactions on Computer-Aided Design, vol. 10, No. 3, Mar. 1991, pp. 356-365).
Lee et al. (“A flexible clustering and floor planning approach to standard cell placement using hierarchical simulated annealing” Proceedings of the 1991 International Conference on Circuits and Systems, vol. 2, Jun. 16, 1991, pp. 882-885).
NN86044981, “Timing-Influenced Layout Design”, IBM Technical Disclosure Bulletin, Apr. 1986, vol. 28 No. 11, pp. 4981-4987 (11 pages).
NN881174, “Placement-Preserving Timing Adjustment for Very Large-Scale Integrated Circuits”, IBM Technical Disclosure Bulletin, Nov. 1988, vol. 31,No. 6, pp. 74-77 (5 pages).
NA9003341, “CPLACE: A Standard Cell Placement Program”, IBM Technical Disclosure Bulletin, vol. 32, No. 10A, Mar. 1990, pp. 341-342 (5 pages).
Miller Ronald
Naylor William C.
Wong Yiu-Chung
Bever Hoffman & Harms LLP
Harms Jeanette S.
Kik Phallaka
Synopsys Inc.
LandOfFree
Detailed placer for optimizing high density cell placement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detailed placer for optimizing high density cell placement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detailed placer for optimizing high density cell placement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4289179