Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-07-18
2006-07-18
Dinh, Paul (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
07080336
ABSTRACT:
For a placer that partitions a region of a circuit layout into a plurality of sub-regions, some embodiments provide a method of computing placement costs. For a set of sub-regions, the method identifies a connection graph that connects the set of sub-regions. The connection graph has at least one edge that is at least partially diagonal. The method then identifies a placement cost from an attribute of the connection graph.
REFERENCES:
patent: 4593363 (1986-06-01), Burstein et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4855929 (1989-08-01), Nakajima
patent: 5097422 (1992-03-01), Corbin, II et al.
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5375069 (1994-12-01), Satoh et al.
patent: 5532934 (1996-07-01), Rostoker
patent: 5566078 (1996-10-01), Ding et al.
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5587923 (1996-12-01), Wang
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5633479 (1997-05-01), Hirano
patent: 5634093 (1997-05-01), Ashida et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5637920 (1997-06-01), Loo
patent: 5640327 (1997-06-01), Ting
patent: 5650653 (1997-07-01), Rostoker et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5742086 (1998-04-01), Rostoker et al.
patent: 5757089 (1998-05-01), Ishizuka
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 5777360 (1998-07-01), Rostoker et al.
patent: 5784289 (1998-07-01), Wang
patent: 5798936 (1998-08-01), Cheng
patent: 5811863 (1998-09-01), Rostoker et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5859449 (1999-01-01), Kobayashi et al.
patent: 5889677 (1999-03-01), Yasuda et al.
patent: 5898597 (1999-04-01), Scepanovic et al.
patent: 5914887 (1999-06-01), Scepanovic et al.
patent: 5973376 (1999-10-01), Rostoker et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6035108 (2000-03-01), Kikuchi
patent: 6058254 (2000-05-01), Scepanovic et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6068662 (2000-05-01), Scepanovic et al.
patent: 6070108 (2000-05-01), Andreev et al.
patent: 6123736 (2000-09-01), Pavisic et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6134702 (2000-10-01), Scepanovic et al.
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6216252 (2001-04-01), Dangelo et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6247167 (2001-06-01), Raspopovic et al.
patent: 6249902 (2001-06-01), Igusa et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6260179 (2001-07-01), Ohsawa et al.
patent: 6262487 (2001-07-01), Igarashi et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6295634 (2001-09-01), Matsumoto
patent: 6301686 (2001-10-01), Kikuchi et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6327693 (2001-12-01), Cheng et al.
patent: 6327694 (2001-12-01), Kanazawa
patent: 6330707 (2001-12-01), Shinomiya et al.
patent: 6378121 (2002-04-01), Hiraga
patent: 6385758 (2002-05-01), Kikuchi et al.
patent: 6401234 (2002-06-01), Alpert et al.
patent: 6405358 (2002-06-01), Nuber
patent: 6407434 (2002-06-01), Rostoker et al.
patent: 6412097 (2002-06-01), Kikuchi et al.
patent: 6412102 (2002-06-01), Andreev et al.
patent: 6415422 (2002-07-01), Mehrotra et al.
patent: 6436804 (2002-08-01), Igarashi et al.
patent: 6442743 (2002-08-01), Sarrafzadeh et al.
patent: 6448591 (2002-09-01), Juengling
patent: 6463575 (2002-10-01), Takahashi
patent: 6473891 (2002-10-01), Shively
patent: 6480991 (2002-11-01), Cho et al.
patent: 6490713 (2002-12-01), Matsumoto
patent: 6516455 (2003-02-01), Teig et al.
patent: 6519751 (2003-02-01), Sriram et al.
patent: 6543043 (2003-04-01), Wang et al.
patent: 6546540 (2003-04-01), Igarashi et al.
patent: 6557145 (2003-04-01), Boyle et al.
patent: 2001/0003843 (2001-06-01), Scepanovic et al.
patent: 2001/0009031 (2001-07-01), Nitta et al.
patent: 2002/0069397 (2002-06-01), Teig et al.
patent: 2002/0073390 (2002-06-01), Teig et al.
patent: 2002/0100007 (2002-07-01), Teig et al.
patent: 2002/0124231 (2002-09-01), Teig et al.
patent: 2002/0133798 (2002-09-01), Teig et al.
patent: 2002/0147958 (2002-10-01), Teig et al.
patent: 2002/0166105 (2002-11-01), Teig et al.
patent: 2002/0170027 (2002-11-01), Teig et al.
patent: 2002/0174412 (2002-11-01), Teig et al.
patent: 2002/0182844 (2002-12-01), Igarashi et al.
patent: 2002/0199165 (2002-12-01), Teig et al.
patent: 2003/0005399 (2003-01-01), Igarashi et al.
patent: 2003/0018947 (2003-01-01), Teig et al.
patent: 2003/0023943 (2003-01-01), Teig et al.
patent: 2003/0025205 (2003-02-01), Shively
patent: 2003/0043827 (2003-03-01), Teig et al.
patent: 2003/0056187 (2003-03-01), Teig et al.
patent: 2003/0063568 (2003-04-01), Teig et al.
patent: 2003/0063614 (2003-04-01), Teig et al.
patent: 2003/0064559 (2003-04-01), Teig et al.
patent: 2003/0066042 (2003-04-01), Teig et al.
patent: 2003/0066043 (2003-04-01), Teig et al.
patent: 2003/0066044 (2003-04-01), Teig et al.
patent: 2003/0066045 (2003-04-01), Teig et al.
patent: 2003/0079193 (2003-04-01), Teig et al.
patent: 2003/0088841 (2003-05-01), Teig et al.
patent: 2003/0088844 (2003-05-01), Teig et al.
patent: 2003/0088845 (2003-05-01), Teig et al.
patent: 2003/0101428 (2003-05-01), Teig et al.
patent: 2003/0115566 (2003-06-01), Teig
patent: 64-15947 (1989-01-01), None
patent: H03-173471 (1991-07-01), None
patent: H05-102305 (1993-04-01), None
patent: H05-243379 (1993-09-01), None
patent: H07-86407 (1995-03-01), None
patent: H09-162279 (1997-06-01), None
patent: 411296560 (1999-10-01), None
patent: 2000-82743 (2000-03-01), None
Ahuja, R. et al., Faster Algorithms for the Shortest Path Problem, Journal of the Association for Computing Machinery, vol. 37, No. 2, Apr. 1990, pp. 213-223.
Brady, L. et al., Channel Routing on a 60° Grid, extended abstract, pp. 956-931.
Brambilla, A. et al., Statistical Method for the Analysis of Interconnects Delay in Submicrometer Layouts, IEEE, Aug. 2001, pp. 957-966.
Carothers, K., A Method of Measuring Nets Routability for MCM's General Area Routing Problems, 1999, pp. 186-192.
Chen, H. et al., Physical Planning of On-Chip Interconnect Architectures, 2002, IEEE, International Conference, pp. 30-35.
Cheng, K. et al., Manhattan or Non Manhattan? A Study of Alternative VLSI Routing Architectures, pp. 47-52, 2000.
Cheng, K., Steiner Problem in Octilinear Routing Model, a Thesis Submitted for the Degree of Master of Science, National University Singapore, 1995, pp. 1-122.
Chip Model with Wiring Cost Map, Aug. 1983, IBM Technical Disclosure Bulletin, vol. 26, iss. 3A, pp. 929-933.
Cong, J. et al., Efficient Heuristics for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design, Cadence Design Systems and UCLA Computer Science Department, pp. 88-95.
Cong, J. et al., Performance-Driven Multi-Layer General Routing for PCB/MCM Designs, UCLA Computer Science Department, 1998, pp. 356-361.
Enbody, R. et al., Near-Optimaln-Layer Channel Routing, 23rdDesign Automation Conference, 1986, pp. 708-714.
Fang, S. et al., Constrained Via Minimization with Practical Considerations for Multi-Layer VLSI/PCB Routing Problems, 28thACM/IEEE Design Automation Conference, 1991, pp. 60-65.
Horn, I. et al., Estimation of the Number of Routing Layers and Total Wirelength in a PCB Through Wiring Distribution Analysis, 1996, pp. 1-6.
Hong, X. et al., Performance-Driven Steiner Tree Algorithms for Global Routing, 30thACM/IEEE Design Automation Conference, 1993, pp. 177-181.
Hu, J et al.: “A Timing-Constrained algorithm for Simultaneous Global Routing of Multiple Nets” IEEE/ACM International Conference on Computer Aided Design. ICCAD—2000. IEEE/ACM Digest of Technical Papers (CAT. No. 00CH37140), Proceedings of International Conference on Computer Aided Design (ICCAD), San Jose, CA USA, Nov. 5-9, 2000. pp. 99-103.
Kastner R et al.: “Predictable Routing” IEEE/ACM International Conference on Computer Aided Design. ICCAD—2000. IEEE/ACM Dige
Ganley Joseph L.
Teig Steven
Cadence Design Systems Inc.
Stattler Johansen & Adeli LLP
LandOfFree
Method and apparatus for computing placement costs 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 and apparatus for computing placement costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for computing placement costs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3536693