Method and apparatus for costing routes of nets

Details Method and apparatus for costing routes of nets Method and apparatus for costing routes of nets

2005-05-10

2005-05-10

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06892369

ABSTRACT:
Some embodiments of the invention provide a method of costing routes for a set of nets. The method identifies at least one route for each net, where each route has a particular length. It also identifies an estimated route length for each net. It then computes a cost that includes an exponential expression for each net. Each net's exponential expression includes a base and an exponent. The exponent of each net's exponential expression includes the length of the net's route divided by the estimated route length for the net.

REFERENCES:
patent: 4615011 (1986-09-01), Linsker
patent: 4673966 (1987-06-01), Shimoyma
patent: 4777606 (1988-10-01), Fournier
patent: 4782193 (1988-11-01), Linsker
patent: 4855929 (1989-08-01), Nakajima
patent: 5224057 (1993-06-01), Igarashi et al.
patent: 5360948 (1994-11-01), Thornberg
patent: 5375069 (1994-12-01), Satoh et al.
patent: 5519836 (1996-05-01), Gawlick et al.
patent: 5532934 (1996-07-01), Rostoker
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5633479 (1997-05-01), Hirano
patent: 5634093 (1997-05-01), Ashida et al.
patent: 5635736 (1997-06-01), Funaki et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5637920 (1997-06-01), Loo
patent: 5650653 (1997-07-01), Rostoker et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5659484 (1997-08-01), Bennett et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5717600 (1998-02-01), Ishizuka
patent: 5723908 (1998-03-01), Fuchida 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: 5811863 (1998-09-01), Rostoker et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5856927 (1999-01-01), Greidinger et al.
patent: 5859449 (1999-01-01), Kobayashi et al.
patent: 5877091 (1999-03-01), Kawakami
patent: 5880969 (1999-03-01), Hama et al.
patent: 5889329 (1999-03-01), Rostoker 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: 5978572 (1999-11-01), Toyonaga et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6006024 (1999-12-01), Guruswamy et al.
patent: 6035108 (2000-03-01), Kikuchi
patent: 6038383 (2000-03-01), Young et al.
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: 6085032 (2000-07-01), Scepanovic et al.
patent: 6088519 (2000-07-01), Koford
patent: 6110222 (2000-08-01), Minami et al.
patent: 6111756 (2000-08-01), Moresco
patent: 6123736 (2000-09-01), Pavisic et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6154873 (2000-11-01), Takahashi
patent: 6154874 (2000-11-01), Scepanovic et al.
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6166441 (2000-12-01), Geryk
patent: 6175870 (2001-01-01), Gawlick 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: 6219823 (2001-04-01), Hama et al.
patent: 6219832 (2001-04-01), Buzbee
patent: 6226560 (2001-05-01), Hama et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6247167 (2001-06-01), Raspopovic et al.
patent: 6247853 (2001-06-01), Papadopoulou 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: 6286128 (2001-09-01), Pileggi et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6292929 (2001-09-01), Scepanovic 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: 6349403 (2002-02-01), Dutta 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: 6415427 (2002-07-01), Nitta et al.
patent: 6434730 (2002-08-01), Ito et al.
patent: 6436804 (2002-08-01), Igarashi et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
patent: 6463575 (2002-10-01), Takahashi
patent: 6473891 (2002-10-01), Shively
patent: 6490713 (2002-12-01), Matsumoto
patent: 6505331 (2003-01-01), Bracha et al.
patent: 6519751 (2003-02-01), Sriram et al.
patent: 6526555 (2003-02-01), Teig 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: 6567967 (2003-05-01), Greidinger et al.
patent: 6586281 (2003-07-01), Gabara et al.
patent: 6601227 (2003-07-01), Trimberger
patent: 6609237 (2003-08-01), Hamawaki et al.
patent: 6618846 (2003-09-01), Cheng
patent: 6645842 (2003-11-01), Igarashi et al.
patent: 6656644 (2003-12-01), Hasegawa et al.
patent: 6665852 (2003-12-01), Xing et al.
patent: 20010003843 (2001-06-01), Scepanovic et al.
patent: 20010038612 (2001-11-01), Vaughn et al.
patent: 20020043988 (2002-04-01), Or-Bach et al.
patent: 20020100009 (2002-07-01), Xing et al.
patent: 20020104061 (2002-08-01), Xing et al.
patent: 20020107711 (2002-08-01), Xing et al.
patent: 20020174413 (2002-11-01), Tanaka
patent: 20020182844 (2002-12-01), Igarashi et al.
patent: 20030005399 (2003-01-01), Igarashi et al.
patent: 20030009737 (2003-01-01), Xing
patent: 20030014725 (2003-01-01), Sato et al.
patent: 20030025205 (2003-02-01), Shively
patent: 20030121017 (2003-06-01), Andreev et al.
patent: 20030188281 (2003-10-01), Xing
patent: 20030217338 (2003-11-01), Holmes et al.
patent: 20040015805 (2004-01-01), Kidd et al.
patent: 20040040007 (2004-02-01), Harn
patent: 20040044979 (2004-03-01), Aji et al.
patent: 20040088670 (2004-05-01), Stevens et al.
patent: 64-15947 (1989-01-01), None
patent: 02-262354 (1990-10-01), None
patent: 03-173471 (1991-07-01), None
patent: 04-000677 (1992-01-01), None
patent: 05-102305 (1993-04-01), None
patent: 05-243379 (1993-09-01), None
patent: 07-086407 (1995-03-01), None
patent: 09-162279 (1997-06-01), None
patent: 11-296560 (1999-10-01), None
patent: 2000-082743 (2000-03-01), None
Juttner et al., “Lagrange Relaxation Based Method for the QoS Routing Problem,” IEEE, Apr. 26, 2001, pp. 859-868.*
U.S. Appl. No. 10/066,060, filed Jan. 31, 2002, Steven Teig.
U.S. Appl. No. 10/066,160, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/066,095, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/066,047, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/061,641, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/066,094, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/076,121, filed Feb. 12, 2002, Steven Teig et al.
U.S. Appl. No. 10/062,995, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/066,102, filed Jan. 31, 2002, Steven Teig.
U.S. Appl. No. 10/066,187, filed Jan. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/286,584, filed Oct. 31, 2002, Steven Teig.
U.S. Appl. No. 10/335,087, filed Dec. 31, 2002, Steven Teig et al.
U.S. Appl. No. 10/335,239, filed Dec. 31, 2002, Steven Teig et al.
Chen, H.F. et al., A Faster Algorithm for Rubber-Band Equivalent Transformation for Planar VLSI Layouts, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 2, Feb. 1996, pp. 217-227.
Chip Model with Wiring Cost Map, Aug. 1983, IBM Technical Disclosure Bulletin, vol. 26, issu. 3A, pp. 929-933.
Dayan, T. et al., Layer Assignment for Rubber Band Routing, UCSC-CRI-93-04, Jan. 20, 1993.
Dayan, T., Rubber-Band Based Topological Router, A Dissertation, UC Santa Cruz, Jun. 1997.
Dood, P. et al. A Two-Dimensional Topological Compactor with Octagonal Geometry, 28thACM/IEEE

Affiliated with

Also associated with

Rating

Method and apparatus for costing routes of nets 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 costing routes of nets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for costing routes of nets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3379075