Method and apparatus for routing

Details Method and apparatus for routing Method and apparatus for routing

2008-12-01

2011-11-22

Doan, Nghia (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Integrated circuit design processing

Physical design processing

C716S100000, C716S110000, C716S111000, C716S129000, C716S130000, C716S131000

Reexamination Certificate

active

08065649

ABSTRACT:
A method is provided that performs a path search that identifies several path extensions. The method performs a viability check on a particular path extension by identifying first and second circuit geometries. The first circuit geometry is associated with a particular segment of a route that would result from the particular path expansion in a design layout. The second circuit geometry is associated with a circuit element to which the particular segment connects. The viability check also determines whether connecting the segment with the first geometry and the circuit element with the second geometry is allowable based on predetermined rules. The method stores the particular path expansion in a storage medium as a viable path expansion when the viability check determines that connecting the segment with the first geometry and the circuit element with the second geometry is allowable.

REFERENCES:
patent: 4673966 (1987-06-01), Shimoyama
patent: 5371690 (1994-12-01), Engel et al.
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5673201 (1997-09-01), Malm et al.
patent: 5798936 (1998-08-01), Cheng
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 6167555 (2000-12-01), Lakos
patent: 6240542 (2001-05-01), Kapur
patent: 6256769 (2001-07-01), Tamarkin et al.
patent: 6301686 (2001-10-01), Kikuchi et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6341366 (2002-01-01), Wang et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6353918 (2002-03-01), Carothers et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
patent: 6490713 (2002-12-01), Matsumoto
patent: 6505334 (2003-01-01), Tanaka
patent: 6539521 (2003-03-01), Pierrat et al.
patent: 6543035 (2003-04-01), Ohba et al.
patent: 6609237 (2003-08-01), Hamawaki et al.
patent: 6611946 (2003-08-01), Richardson et al.
patent: 6618846 (2003-09-01), Cheng
patent: 6645842 (2003-11-01), Igarashi et al.
patent: 6651233 (2003-11-01), Teig et al.
patent: 6665849 (2003-12-01), Meuris et al.
patent: 6678876 (2004-01-01), Stevens et al.
patent: 6763508 (2004-07-01), Igarashi et al.
patent: 6779167 (2004-08-01), Igarashi et al.
patent: 6802048 (2004-10-01), Goto et al.
patent: 6829757 (2004-12-01), Teig et al.
patent: 6879934 (2005-04-01), Teig et al.
patent: 6892369 (2005-05-01), Teig et al.
patent: 6916719 (2005-07-01), Knight et al.
patent: 6938230 (2005-08-01), Frank et al.
patent: 6976237 (2005-12-01), Teig et al.
patent: 6988257 (2006-01-01), Teig et al.
patent: 6996789 (2006-02-01), Teig et al.
patent: 6996793 (2006-02-01), Kronmiller et al.
patent: 7002572 (2006-02-01), Teig et al.
patent: 7003752 (2006-02-01), Teig et al.
patent: 7010771 (2006-03-01), Teig et al.
patent: 7065731 (2006-06-01), Jacques et al.
patent: 7080342 (2006-07-01), Teig et al.
patent: 7107564 (2006-09-01), Teig et al.
patent: 7171635 (2007-01-01), Teig et al.
patent: 7174529 (2007-02-01), Hetzel
patent: 7398497 (2008-07-01), Sato et al.
patent: 7472366 (2008-12-01), Hetzel et al.
patent: 7480885 (2009-01-01), Frankle et al.
patent: 7869221 (2011-01-01), Knight et al.
patent: 2003/0121017 (2003-06-01), Andreev et al.
patent: 2003/0126582 (2003-07-01), Kobayashi et al.
patent: 2003/0192019 (2003-10-01), Goto et al.
patent: 2004/0145033 (2004-07-01), McElvain
patent: 2004/0210862 (2004-10-01), Igarashi et al.
patent: 2004/0225990 (2004-11-01), Jacques et al.
patent: 2005/0172247 (2005-08-01), Papadopoulou et al.
patent: 2005/0223348 (2005-10-01), Frank et al.
patent: 2005/0273744 (2005-12-01), Allen et al.
patent: 2009/0077522 (2009-03-01), Frankle et al.
patent: WO 2004/102339 (2004-11-01), None
Non-Final Office Action of U.S. Appl. No. 10/779,954, Mar. 31, 2006, Hetzel, Asmus G.
Notice of Allowance of U.S. Appl. No. 10/779,954, Sep. 27, 2006, Hetzel, Asmus G.
Non-Final Office Action of U.S. Appl. No. 11/195,335, May 18, 2007, Hetzel, Asmus et al.
Restriction Requirement of U.S. Appl. No. 11/195,335, Feb. 26, 2008, Hetzel, Asmus et al.
Notice of Allowance of U.S. Appl. No. 11/195,335, Aug. 21, 2008, Hetzel, Asmus et al.
NB8911253, “Polygonal Expansion Algorithm”, Nov. 1, 1989, vol. No. 32, Issue No. 6B, pp. 253-264.
U.S. Appl. No. 11/178,256, filed Jul. 8, 2005, Kronmiller, Tom, et al.
Portions of prosecution history of U.S. Appl. No. 10/335,180, Nov. 14, 2008, Frankle, Jonathan, et al.
Portions of prosecution history of U.S. Appl. No. 12/326,100, Apr. 12, 2001, Frankle, Jonathan, et al.
Portions of prosecution history of U.S. Appl. No. 10/443,315, Dec. 28, 2005, Jacques, Etienne, et al.
Updated portions of prosecution history of U.S. Appl. No. 10/779,954, Jun. 30, 2006, Hetzel, Asmus G.
Updated portions of prosecution history of U.S. Appl. No. 10/195,335, Aug. 11, 2008, Hetzel, Asmus, et al.
Portions of prosecution history of U.S. Appl. No. 10/066,387, Apr. 8, 2005, Kronmiller, Tom, et al.
Portions of prosecution history of U.S. Appl. No. 11/178,256, May 8, 2007, Kronmiller, Tom, et al.
Portions of prosecution history of U.S. Appl. No. 10/174,661, Jul. 14, 2005, Teig, Steven.
Portions of prosecution history of U.S. Appl. No. 10/174,662, Nov. 9, 2004, Teig, Steven.
Portions of prosecution history of U.S. Appl. No. 10/175,390, Aug. 26, 2005, Teig, Steven.
International Search Report and Written Opinion for PCT/US2004/014380, Jan. 24, 2005 (mailing date), Cadence Design Systems, Inc.
International Preliminary Examination Report for PCT/US2004/014380, Jun. 22, 2005 (completion date), Cadence Design Systems, Inc.
Author Unknown, “Congestion Driven Placement System Using Mid-Cut Partitioning,” IBM Technical Disclosure Bulletin, Feb. 1, 2002, Issue 454, NNRD454151 United Kingdom.
Author Unknown, “Wireless Routing Subject to Constraints,” IBM Technical Disclosure Bulletin, Jul. 1, 1984, vol. 27, Issue 2, NN8407978, USA.
Cong, Jason, et al. “Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs,” Proceedings of Design Automation Conference (DAC 1998), Jun. 15-19, 1998, pp. 356-361, ACM, New York, New York, USA.
Fernández, Antonio, et al., “Efficient VLSI Layouts for Homogeneous Product Networks,” IEEE Transactions on Computers, Oct. 1997, pp. 1070-1082, vol. 46, No. 10, IEEE.
Lou, Jinan, et al., “Estimating Routing Congestion Using Probabilistic Analysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Jan. 2002, pp. 32-41, vol. 21, No. 1, IEEE.
Shahookar, K., et al., “VLSI Cell Placement Techniques,” ACM Computing Surveys, Jun. 1991, p. 143-220, vol. 23, Issue 2, ACM, New York, New York, USA.
Tseng, Hsiao-Ping, et al., “A Gridless Multilayer Router for Standard Cell Circuits Using CTM Cells,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Oct. 1999, pp. 1462-1479, vol. 18, No. 10, IEEE.
Wang, Maogang, et al., “Modeling and Minimization of Routing Congestion,” Proceedings of the Asia and South Pacific Design Automation (ASP-DAC 2000), Jun. 9, 2000, pp. 185-190, IEEE.
Zhang, Yiqian, et al., “A Gridless Router Based on Hierarchical PB Corner Stitching Structure,” IEEE 2002 International Conference on Communications. Circuits and Systems and West Sino Expositions, Jun. 29-Jul. 1, 2002, pp. 1438-1443, vol. 2, IEEE.

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4266394