Method and apparatus for specifying a cost function that represents the estimated distance between an external state and a set of states in a space Number:7,047,512 from the United States Patent and Trademark Office (PTO) owispatent Some embodiments of the invention provide a method of specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon. Based on the projected vectors, the method identifies a set of distances that includes the distance between the polygon and each point in a set of points in the external state. The method then uses the identified set of distance to specify the cost function.<H represents, specifying, Method, and, appa, 7047512.html, Patent, pto, 7047512

Title: Method and apparatus for specifying a cost function that represents the estimated distance between an external state and a set of states in a space

Abstract: Some embodiments of the invention provide a method of specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon. Based on the projected vectors, the method identifies a set of distances that includes the distance between the polygon and each point in a set of points in the external state. The method then uses the identified set of distance to specify the cost function.

Patent Number: 7,047,512 Issued on 05/16/2006 to Teig, et al.

Inventors: Teig; Steven (Menlo Park, CA); Caldwell; Andrew (Santa Clara, CA)
Assignee: Cadence Design Systems, Inc. (San Jose, CA)

Appl. No.: 227016

Filed: August 23, 2002

Current U.S. Class: 716/12 ; 716/13; 716/14

Current International Class: G06F 17/50 (20060101)

Field of Search: 716/8-15

References Cited [Referenced By]

U.S. Patent Documents


4777606	October 1988	Fournier
5224057	June 1993	Igarashi et al.
5578840	November 1996	Scepanovic et al.
5657242	August 1997	Sekiyama et al.
5663891	September 1997	Bamji et al.
5717600	February 1998	Ishizuka
5757089	May 1998	Ishizuka
5757656	May 1998	Hershberger et al.
5811863	September 1998	Rostoker et al.
5822214	October 1998	Rostoker et al.
5838583	November 1998	Varadarajan et al.
5856927	January 1999	Greidinger et al.
5877091	March 1999	Kawakami
5880969	March 1999	Hama et al.
5889329	March 1999	Rostoker et al.
5889677	March 1999	Yasuda et al.
5898597	April 1999	Scepanovic et al.
5973376	October 1999	Rostoker et al.
5980093	November 1999	Jones et al.
6006024	December 1999	Guruswamy et al.
6067409	May 2000	Scepanovic et al.
6110222	August 2000	Minami et al.
6128767	October 2000	Chapman
6154873	November 2000	Takahashi
6154874	November 2000	Scepanovic et al.
6175950	January 2001	Scepanovic et al.
6209123	March 2001	Maziasz et al.
6219823	April 2001	Hama et al.
6226560	May 2001	Hama et al.
6230306	May 2001	Raspopovic et al.
6247167	June 2001	Raspopovic et al.
6247853	June 2001	Papadopoulou et al.
6253363	June 2001	Gasanov et al.
6262487	July 2001	Igarashi et al.
6286128	September 2001	Pileggi et al.
6289495	September 2001	Raspopovic et al.
6292929	September 2001	Scepanovic et al.
6324674	November 2001	Andreev et al.
6324675	November 2001	Dutta et al.
6327693	December 2001	Cheng et al.
6327694	December 2001	Kanazawa
6330707	December 2001	Shinomiya et al.
6349403	February 2002	Dutta et al.
6407434	June 2002	Rostoker et al.
6412102	June 2002	Andreev et al.
6415427	July 2002	Nitta et al.
6434730	August 2002	Ito et al.
6436804	August 2002	Igarashi et al.
6442745	August 2002	Arunachalam et al.
6490713	August 2002	Matsumoto et al.
6505331	January 2003	Bracha et al.
6601227	July 2003	Trimberger
6609237	August 2003	Hamawaki et al.
6645842	November 2003	Igarashi et al.
6656644	December 2003	Hasegawa et al.
6665852	December 2003	Xing et al.
2001/0003843	June 2001	Scepanovic et al.
2001/0038612	November 2001	Vaughn et al.
2002/0043988	April 2002	Or-Bach et al.
2002/0100009	July 2002	Xing et al.
2002/0104061	August 2002	Xing et al.
2002/0107711	August 2002	Xing et al.
2002/0182844	December 2002	Igarashi et al.
2003/0005399	January 2003	Igarashi et al.
2003/0009737	January 2003	Xing
2003/0014725	January 2003	Sato et al.
2003/0025205	February 2003	Shively
2003/0121017	June 2003	Andreev et al.
2003/0188281	October 2003	Xing
2004/0044979	March 2004	Aji et al.
2004/0088670	May 2004	Stevens et al.

Foreign Patent Documents


02-262354	Oct., 1990	JP
11-296560	Oct., 1999	JP

Other References

Xing et al., "Shotest Path Search Using Tiles and Piecewise Linear Cost Propagation," IEEE, Feb. 2002, pp. 145-158. cited by examiner .
Reeves et al., "A Distributed Algorithm for Delay-Constrained Unicast Routing," IEEE, Apr. 2000, pp. 239-250. cited by examiner .
Jun Dong Cho, "Wiring Space and Length Estimation in Two-Dimensional Arrays," IEEE, May 2000, pp. 612-615. cited by examiner .
Lai et al., "GMNF-DVMRP: A Modified Version of Distance Vector Multicast Routing Protocol," IEEE, 1997, pp. 65-68. cited by examiner .
Chen et al., "Distance Vector Routing Protocols for Networks with Unidirectional Link," IEEE, 2001, pp. 473-478. cited by examiner .
Zaumen et al., "Steady-State Response of Shortest-Path Routing Algorithms*," IEEE, 1992, pp. 323-332. cited by examiner .
NB8911253 (TDB-ACC-NO), IBM Technical Disclosure Bulletin, Nov. 1989, pp. 253-264. cited by examiner .
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. cited by other .
Dayan, T. et al., Layer Assignment for Rubber Band Routing, UCSC-CRI-93-04, Jan. 20, 1993. cited by other .
Dayan, T., Rubber-Band Based Topological Router, A Dissertation, UC Santa Cruz, Jun. 1997. cited by other .
Hama, T. et al., Curvilinear Detailed Routing Algorithm and its Extension to Wire-Spreading and Wire-Fattening. cited by other .
Hama, T. et al., Topological Routing Path Search Algorithm with Incremental Routability Test, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 2, Feb. 1999, pp. 142-150. cited by other .
Kobayashi, K. et al., A New Interactive Analog Layout Methodology based on Rubber-Band Routing, UCSC-CRL-96-12, Jun. 13, 1996. cited by other .
Lim, A. et al, A Fast Algorithm To Test Planar Topological Routability, Technical Report 94-012, pp. 1-16. cited by other .
Lu, Y., Dynamic Constrained Delaunay Triangulation and Application to Multichip Module Layout, A Thesis for Master of Science, UC Santa Cruz, Dec. 1991. cited by other .
Maley, F.M., Testing Homotopic Routability Under Polygonal Wiring Rules, Algorithmica 1996, 15:1-16. cited by other .
Morton, P. B. et al., An Efficient Sequential Quadratic Programming Formulation of Optimal Wire Spacing for Cross-Talk Noise Avoidance Routing, UCSC-CRL-99-05, Mar. 10, 1999. cited by other .
Staepelaere, D. et al., Geometric Transformations for a Rubber-Band Sketch, A Thesis for a Master of Science in Computer Engineering, UCSC, Sep. 1992. cited by other .
Staepelaere, D. et al., Surf: A Rubber-Band Routing System for Multichip Modules, pp. 18-26, 1993. cited by other .
Su, J. et al., Post-Route Optimization for Improved Yield Using Rubber-Band Wiring Model, 1997 International Conference on Computer-Aided Design, pp. 700-706, Nov. 1997. cited by other .
Wei-Ming Dai, W. et al., Routability of a Rubber-Band Sketch. 28.sup.th ACM-IEEE Design Automation Conference, 1991. pp. 45-65. cited by other .
Xing, Z. et al., A Minimum Cost Path Search Algorithm Through Tile Obstacles, slide presentation. cited by other .
Xing, Z. et al., Shortest Path Search Using Tiles and Piecewise Linear Cost Propagation, IEEE, 2002, pp. 145-158. cited by other .
Xu, A More Efficient Distance Vector Routing Algorithm, UCSC-CRL-96-18, Mar. 1997. cited by other .
Yu, M.-F. et al., Fast and Incremental Routability Check of a Topological Routing Using a Cut-Based Encoding, UCSC-CRL-97-07, Apr. 14, 1997. cited by other .
Yu, M.-F. et al, Interchangeable Pin Routing with Application to Package Layout, UCSC-CRL-96-10, Apr. 25, 1996. cited by other .
Yu, M.-F. et al., Pin Assignment and Routing on a Single-Layer Pin Grid Array, UCSC-CRL-95-15, Feb. 24, 1995. cited by other .
Yu, M.-F. et al., Planar Interchangeable 2-Terminal Routing, UCSC-CRL-95-49, Oct. 19, 1995. cited by other .
Yu, M.-F. et al., Single-Layer Fanout Routing and Routability Analysis for Ball Grid Arrays, UCSC-CRL-95-18, Apr. 25, 1995. cited by other .
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. cited by other .
Bagga, J. et al., Internal, External, and Mixed Visibility Edges of Polygons. cited by other .
Berger, B. et al., Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, Journal of the Association for Computing Machinery, pp. 500-542, Mar. 1995. cited by other .
Chen et al., Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing, May 1994, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions vol.: 13 Issues, pp. 603-609. cited by oth- er .
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. cited by other .
Chiang, C. et al., Wirability of Knock-Knee Layouts with 45.degree. Wires, IEEE Transactions on Circuits and Systems, vol. 38, Issue 6, pp. 613-624, Jun. 1991. cited by other .
Cong, J. et al., Efficient Heuristics for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physcial Design, Cadence Design Systems, pp. 88-95. cited by other .
Cong, J. et al., Multilevel Approach to Full Chip Gridless Routing, Nov. 2001, IEEE, pp. 396-403. cited by other .
Cong, J. et al., Performance Driven Multi-Layer General Routing for PCB/MCM Designs, UCLA Computer Science Department, 1998, pp. 356-361. cit- ed by other .
Gao, S. et al., Channel Routing of Multiterminal Nets, Journal of the Association for Computing Machinery, vol. 41, No. 4, Jul. 1994, pp. 791-818. cited by other .
Gonzalez, T. et al., A Linear Time-Algorithm for Optimal Routing, Journal of the Association for Computing Machinery, vol. 35, No. 4, Oct. 1988, pp. 810-831. cited by other .
Guibas, L. et al., Optimal Shortest Path Queries in a Simple Polygon, 1987 ACM, pp. 50-63. cited by other .
Hachtel, G.D. et al., Linear Complexity Algorithms for Hierarchical Routing, Jan. 1989, IEEE pp. 64-80. cited by other .
Hightower, D., A Solution to Line-Routing Problems on the Continuous Plane, Bell Laboratories, Inc., pp. 11-34. cited by other .
Iso, N. et al., Efficient Routability Checking for Global Wires in Planar Layouts, IEICE Trans. Fundamentals, vol. E80-A, No. 10, Oct. 1997, pp. 1878-1882. cited by other .
Khoo, K. et al., An Efficient Multilayer MCM Router Based on Four-Via Routing, 30.sup.th ACM/IEEE Design Automation Conference, 1993, pp. 590-595. cited by other .
Ladage, L. et al., Resistance Extraction Using a Routing Algorithm, 30.sup.th ACM/IEEE Design Automation Conference, 1993, pp. 38-42. cited by other .
Leiserson, C. et al., Algorithms for Routing and Testing Routability of Planar VLSI Layouts, pp. 69-78, May 1985. cited by other .
Lipski, W. et al., A Unified Approach to Layout Wirability, Mathematical Systems Theory, 1987, pp. 189-203. cited by other .
Lodi, E. et al., A 2d Channel Router for the Diagonal Model, pp. 111-125, Apr. 1991. cited by other .
Lodi, E. et al., Lecture Notes in Computer Science, A 4d Channel router for a two layer diagonal model, pp. 464-476, Jul. 1988. cited by other .
Lodi, E. et al., Routing in Times Square Mode, pp. 41-48, Jun. 1990. cited by other .
Lodi, E. et al., Routing Multiterminal Nets in a Diagonal Model, pp. 899-902, 1988. cited by other .
Nestor, J. A New Look at Hardware Maze Routing, Proceedings of the 12.sup.th ACM Symposium on Great Lakes Symposium on VLSI, pp. 142-147, Apr. 2002. cited by other .
Overtone, G., EDA Underwriter 2 Finding Space in a Multi-Layer Board, Electronic Engineering, Morgan-Grampian LTD, vol. 67, No. 819, pp. 29-30. cited by other .
Powers, K. et al., The 60.degree. Grid: Routing Channels in Width d/square root 3, VLSI, 1991, Proceedings., First Great Lakes Symposium on Kalamazoo, MI, USA, pp. 214-291, Mar. 1991. cited by other .
Schiele, W. et al., A Gridless Router for Industrial Design Rule, 27.sup.th ACM-IEEE Design Automation Conference, pp. 626-631, 1990. cited by other .
Sekiyama, Y. et al., Timing-Oriented Routers for PCB Layout Design of High-Performance Computers, International Conference on Computer Aided Design, pp. 332-335, Nov. 1991. cited by other .
Soukup, J. et al., Maze Router Without a Grid Map, IEEE, 1992, pp. 382-385. cited by other .
Takashima, Y. et al, Routability of FPGAs with Extremal Switch-Block Structures, IEICE Trans. Fundamentals, vol. E81-A, No. 5, May 1998, pp. 850-856. cited by other .
Yan et al., Three-Layer Bubble-Sorting--Based Non-Manhattan Channel Routing, ACM Transactions on Design Automation of Electronic Systems, vol. 5, No. 3, Jul. 2000, pp. 726-734. cited by other .
Zhou, H. et al., An Optimal Algorithm for River Routing with Crosstalk Constraints, 1996. cited by other .
Zhou, H. et al., Optimal River Routing with Crosstalk Constraints, ACM Transactions on Design Automation of Electronic Systems, vol. 3, No. 3, Jul. 1998, pp. 496-514. cited by other .
U.S. Appl. No. 10/228,736, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/229,311, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/229,108, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/215,563, filed Aug. 9, 2002, Steven Teig, Application with some of the same parent provisional applications as the present application. Related application that describes the path search technology described in the present application. cited by other .
U.S. Appl. No. 10/215,896, filed Aug. 9, 2002, Steven Teig, Application with some of the same parent provisional applications as the present application. Related application that describes the path search technology described in the present application. cited by other .
U.S. Appl. No. 10/219,675, filed Aug. 14, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/219,608, filed Aug. 14, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/233,202, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/229,196, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/288,870, filed Nov. 6, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/076,121. cited by other .
U.S. Appl. No. 10/219,923, filed Aug. 14, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/286,254, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/219,706, filed Aug. 14, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/231,423, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/230,503, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/222,088, filed Aug. 14, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/228,679, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/229,679, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/229,170, filed Aug. 26, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/286,630, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/230,504, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/215,923, filed Aug. 9, 2002, Steven Teig, The present application is a continuation of this application. cited by other .
U.S. Appl. No. 10/226,483, filed Aug. 23, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/226,774, filed Aug. 23, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/232,795, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/231,369, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/233,312, filed Aug. 28, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/226,482, filed Aug. 23, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/285,844, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/286,253, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/28,033, filed Nov. 5, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/335,179, filed Dec. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/285,758, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,923. cited by other .
U.S. Appl. No. 10/286,598, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/286,584, filed Oct. 31, 2002, Steven Teig, Continuation of U.S. Appl. No. 10/215,896. cited by other .
U.S. Appl. No. 10/335,074, filed Dec. 31, 2002, Steven Teig et al., CIP of U.S. Appl. No. 10/215,923, 10/215,896, and 10/215,563. cited by other .
U.S. Appl. No. 10/334,665, filed Dec. 31, 2002, Steven Teig et al., CIP of U.S. Appl. No. 10/215,923, 10/215,896, and 10/215,563. cited by other .
U.S. Appl. No. 10/335,243, filed Dec. 31, 2002, Steven Teig et al., CIP of U.S. Appl. No. 10/215,923, 10/215,896, and 10/215,563. cited by other .
U.S. Appl. No. 10/335,062, filed Dec. 31, 2002, Steven Teig, CIP of U.S. Appl. No. 10/215,923, 10/215,896, and 10/215,563. cited by other .
U.S. Appl. No. 10/066,060, filed Jan. 31, 2002, Steven Teig, Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,160, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,095, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,047, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/061,641, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,094, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563 and 10/215,896. cited by other .
U.S. Appl. No. 10/076,121, filed Feb. 12, 2002, Steven Teig, Parent application of U.S. Appl. No. 10/215,563 and 10/215,896. cited by other .
U.S. Appl. No. 10/062,995, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,102, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
U.S. Appl. No. 10/066,187, filed Jan. 31, 2002, Steven Teig et al., Parent application of U.S. Appl. No. 10/215,563. cited by other .
Cho J.D., Wiring Space and Length Estimation in Two-Dimensional Arrays, May 2000, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 19, Iss. 5, pp. 612-615. cited by other .
Cong J. et al., DUNE--A Multilayer Gridless Routing System, May 2001, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, iss. 5, pp. 633-647. cited by other .
Dion J. et al., Contour: A Tile-based Gridless Router, Mar. 1995, Digital Western Research Laboratory, research Report 95-3, pp. 1-22. cited by oth- er .
Schulz U., Hierarchical Physical Design System, CompEuro '89, VLSI and Computer Peripherals. VSLI and Microelectronic Applications in Intelligent Peripherals and their Interconnection Networks. Proceedings, May 8-12, 1989, pp. 5/20-5/24. cited by other .
Tseng H-P. et al., A Gridless Multilayer Router for Standard Cell Circuits Using CTM Cells, Oct. 1999, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, iss. 10, pp. 1462-1479. cited by other.

Primary Examiner: Siek; Vuthe
Attorney, Agent or Firm: Stattler, Johansen & Adeli LLP

Parent Case Text

CLAIM OF BENEFIT TO PRIOR APPLICATIONS

This patent application is a continuation of the U.S. patent application entitled "Method and Apparatus for Identifying a Path Between Source and Target States in a Space with More than Two Dimensions," having Ser. No. 10/215,923, and filed Aug. 9, 2002. This application also claims the benefit of the U.S. Provisional Patent Application entitled "Method and Apparatus for Routing," having Ser. No. 60/396,571, and filed Jul. 15, 2002; U.S. Provisional Patent Application entitled "Method and Apparatus for Routing and Interconnect Architectures," having Ser. No. 60/388,518, and filed Jun. 12, 2002; and U.S. Provisional Patent Application entitled "Interconnect Method, Apparatus, and Architecture for Integrated Circuits and Integrated-Circuit Layouts," having Ser. No. 60/385,975, and filed Jun. 4, 2002.

Claims

We claim:

1. For a region of a design layout having a plurality of states, a method of identifying a set of distances between a first state and a set of states in the region, the method comprising: a) identifying a polygon that encloses the set of states; b) projecting vectors from one or more vertices of the polygon in various directions outward from the vertices toward other areas in the region; and c) based on the projected vectors, identifying the set of distances between the first state and the set of states, wherein the first state is a first point and the set of distances includes only the distance between the polygon and the first point, wherein identifying the set of distances comprises: if the first point is between two projected vectors that emanate from the same vertex, identifying the distance between the first point and the vertex from which the two projected vectors emanate; and if the first point is between two projected vectors that emanate from the different vertices, identifying the distance, along a direction parallel to the two projected vectors, between the first point and the polygon.

2. The method of claim 1, wherein projecting vectors comprises projecting vectors from all vertices of the polygon.

3. The method of claim 1, wherein identifying the distance between the first point and the vertex from which the two projected vectors emanate comprises identifying the distance between the first point and the vertex according to an interconnect model of the region that specifies a set of interconnect lines for connecting the first point and the vertex.

4. For a region of a design layout having a plurality of states, a method of identifying a set of distances between a first state and a set of states in the region, the method comprising: a) identifying a polygon that encloses the set of states; b) projecting vectors from one or more vertices of the polygon in various directions outward from the vertices toward other areas in the region; and c) based on the projected vectors, identifying the set of distances between the first state and the set of states, wherein the first state is a surface and the set of distances comprises two or more distances between the polygon and the surface.

5. The method of claim 4, wherein the surface has a plurality of vertices, wherein identifying the set of distances comprises: at each intersection point on the boundary of the surface that is intersected by one of the projected vectors, computing a distance between the intersection point and the polygon; and at each vertex of the surface that does not intersect one of the projected vectors, computing a distance between the endpoint and the polygon.

6. The method of claim 5, wherein computing the distance at an intersection point comprises computing the distance between the intersection point and the polygon in the direction of the projected vector that intersects the intersection point.

7. The method of claim 5, wherein computing the distance at each vertex of the surface that does not intersect one of the projected vectors comprises: if the surface vertex is between two projected vectors that emanate from the same polygon vertex, identifying the distance between the surface vertex and the polygon vertex from which the two projected vectors emanate; and if the surface vertex is between two projected vectors that emanate from the different polygon vertices, identifying the distance, along a direction parallel to the two projected vectors, between the surface vertex and the polygon.

8. The method of claim 7, wherein identifying the distance between the surface vertex and the polygon vertex from which the two projected vectors emanate comprises identifying the distance between the surface vertex and the polygon vertex according to an interconnect model of the region that specifies a set of interconnect lines for connecting the surface vertex and the polygon vertex.

9. For a region of a design layout having a plurality of states, a method of identifying a set of distances between a first state and a set of states in the region, the method comprising: a) identifying a polygon that encloses the set of states; b) projecting vectors from one or more vertices of the polygon in various directions outward from the vertices toward other areas in the region; and c) based on the projected vectors, identifying the set of distances between the first state and the set of states, wherein the polygon is a first polygon, wherein identifying the first polygon comprises: i) identifying a second polygon that encloses the set of states; ii) identifying a third polygon that encloses the set of states; and iii) specifying the first polygon as an intersection of the second and third polygons.

Description

FIELD OF THE INVENTION

The invention is directed towards method and apparatus for specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space.

BACKGROUND OF THE INVENTION

A best-first search is an iterative search that at each iteration tries to extend the partial solution with the best estimated cost. Best-first searches have often been used to identify the shortest path between source and target points in a multi-point search space. One such best-first search is the A* search. To identify a path between source and target points, the A* search starts one or more paths from the source and/or target points. It then iteratively identifies one or more path expansions about the lowest cost path, until it identifies a path that connects the source and target points. The typical cost of a path expansion in an A* search is an {circumflex over (F)} cost, which is the cost of the path leading up to the path expansion plus an estimated cost of reaching a target point from the path expansion.

FIGS. 1 6 provide an example of an A* path search that uses such an {circumflex over (F)} cost. In this example, the search process has to find the shortest path between a source point 105 and a target point 110 in a region 120. The source and target points are part of a multi-point grid 115 that is imposed over the region.

As shown in FIG. 2, the search process initially identifies four path expansions from the source point 105 to four points 202 208 that neighbor the source point in the Manhattan directions. In FIGS. 2 6, the search process represents each path expansion by using a path identifier, called a "drop." More specifically, the search process represents each path expansion from one grid point (a start point) to another point (a destination point) by (1) specifying a drop, (2) associating the drop with the expansion's destination point, and (3) defining the specified drop's previous drop to be the drop of the expansion's start point. Drops allow the search to keep track of the paths that it explores.

The search process specifies four drops 210 216 for the expansions to the four points 202 208, as illustrated in FIG. 2. It also specifies a drop 218 for the source point 105. The source point drop 218 is the previous drop of drops 210 216. The source point drop's previous drop is null, as it is the first drop in the path search.

For each drop 210 216, the search process computes an {circumflex over (F)} cost based on the following formula: {circumflex over (F)}=G+H. where (1) G specifies the cost of a path from the source point to the drop's grid point through the sequence of expansions that led to the drop, and (2) H specifies the estimated lower-bound cost from the drop's grid point to the target point. When computed in this manner, the {circumflex over (F)} cost of a drop is the estimated cost of the cheapest path that starts at the source point, traverses through the sequence of expansions that led to the drop, and traverses from the drop to the target point.

To simplify the description of the example illustrated in FIGS. 1 6, the distance between each pair of horizontally or vertically adjacent grid points is 1. Accordingly, in FIG. 2, the G cost of each drop 210 216 is 1, as the grid point of each of these drops is one grid unit away from the source point. In FIGS. 2 6, a drop's H cost is computed as the Manhattan distance between the drop's point and the target point. Hence, the H cost of drops 210, 212, 214, and 216 are respectively one, three, three, and three, as these distances are respectively the Manhattan distances of the points of these drops from the target point.

After costing these drops, the search process stores the drops 210 216 in a priority queue that is sorted based on their {circumflex over (F)} costs. It then retrieves the drop with the lowest {circumflex over (F)} cost from the priority queue. This drop is drop 210. Since this drop's corresponding point (i.e., point 202) is not the target point, the search process then identifies a path expansion from the retrieved drop's point 202 to point 305. As shown in this figure, this expansion is the only viable expansion from the retrieved drop's point 202 as the search has previously reached all other unblocked neighboring grid points (i.e., the grid points that are not blocked by an obstacle 315) through less expensive paths. The search process specifies a drop 310 for this expansion, and computes this drop's G, H, and {circumflex over (F)} costs, which are respectively 2, 2, and 4. It then stores this specified drop in the priority queue.

After storing drop 310 in the priority queue, the search process might retrieve either drop 310, drop 212, or drop 214 from the priority queue, as each of these drops has an {circumflex over (F)} cost of 4. However, if the search process retrieved drop 310, it will not expand from this drop to its neighboring points that are not blocked by obstacle 315 since all these neighboring points were previously reached less expensively. Also, if the search process retrieves drop 214, it will identify drops that will be more expensive than drop 212.

When the search process retrieves drop 212 from the priority queue, it checks whether this drop's point is the target point. When it discovers that it is not, the process (1) identifies expansions to three neighboring points 402 406 about this drop's point, as shown in FIG. 4, (2) specifies three drops 408 412 for the three identified expansions, as shown in FIG. 4, (3) computes each specified drop's G, H, and {circumflex over (F)} costs, (4) defines each specified drop's previous drop (which in this case is drop 212), and (5) stores each newly specified drop in the priority queue based on its {circumflex over (F)} cost.

Next, as illustrated respectively in FIGS. 5 and 6, the search process performs these six operations first for drop 408 and then for drop 510, since these two drops are the ones with the lowest {circumflex over (F)} costs during the next two iterations of the search process. As illustrated in FIG. 5, the drop 510 is specified for an expansion about drop 408's point 402.

As shown in FIG. 6, one of the expansions about drop 510 reaches the point 110. The search process creates, costs, and stores a drop 615 for this expansion. It then retrieves this drop in its next iteration, and then realizes that this drop's point is the target point. Accordingly, at this juncture, it terminates its path search operation. It then commences a path-embedding, back-trace operation that uses the previous-drop references of the drops 615, 510, 408, 212, and 218 to identify the sequence of drops that reached the target point 110 from the source point 105. This operation embeds a path along the grid points associated with the identified sequence of drops. FIGS. 7 and 8 illustrate the back-trace operation and the resulting embedded path.

The A* search is not suitable for finding the lowest-cost path in a graph with non-zero dimensional states. This is because the A* search computes a single cost value for the expansion to any state in the graph, while the actual cost can vary across a non-zero dimensional state. Accordingly, there is a need for a path search process that can identify the lowest-cost path in a graph with non-zero dimensional states.

SUMMARY OF THE INVENTION

Some embodiments of the invention provide a method of specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon. Based on the projected vectors, the method identifies a set of distances that includes the distance between the polygon and each point in a set of points in the external state. The method then uses the identified set of distance to specify the cost function.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features of the invention are set forth in the appended claims. However, for purpose of explanation, several embodiments of the invention are set forth in the following figures.

FIGS. 1 8 provide an example of an A* path search that uses such an {circumflex over (F)} cost.

FIG. 9 illustrates a portion of a layer that has been triangulated into four triangular faces, each of which has a space, three nodes, and three edges, while FIG. 10 provides examples of topological routes that are formed by via nodes, Steiners, walls, joints, and nodes.

FIGS. 11 and 12 illustrate examples of line and surface PLF's.

FIG. 13 presents an example of filtering a first filtered PLF by a second filter PLF, where both PLF's are defined across a line. FIG. 14 illustrates the minimum PLF for the two PLF's of FIG. 13.

FIG. 15 illustrates a Q* path search process of some embodiments of the invention.

FIGS. 16 19 provide examples for describing the process of FIG. 15.

FIG. 20 illustrates a process that propagates a PLF that is defined over a point to a line or a surface. FIGS. 21 and 22 illustrate examples of propagating a PLF from a point P to a line L and to a surface S.

FIG. 23 illustrates a process for propagating a PLF from a line to another line or from a surface to a line, and FIGS. 24 and 25 provides examples for describing this process.

FIGS. 26 31 illustrate how some embodiments identify the propagation vectors that emanate from the knot locations of a line PLF or surface PLF.

FIG. 32 illustrates a process for propagating a G PLF from a line to a surface.

FIG. 33 illustrates an example for propagating a G PLF from a line to a surface.

FIG. 34 illustrates a process for propagating a PLF from a line to a point or from a surface to a point. FIGS. 35 and 36 describe the process of FIG. 34.

FIG. 37 presents an example that illustrates an expansion from a start surface to a destination surface.

FIGS. 38A and 38B illustrate how to compute the flow across an edge after a potential expansion.

FIGS. 39 and 41 illustrate processes that generate PLF's that express costs of expansions to an edge or a hole, while FIGS. 40 and 42 present examples that describe these processes.

FIGS. 43 45 illustrate how to add two surface PLF's.

FIG. 46 illustrates a process that performs filtering and minimum operations for an expansion to a line.

FIGS. 47 49 illustrate how to filter two surface PLF's.

FIGS. 50 and 51 illustrate how some embodiments compute an H function.

FIG. 52 illustrates a conceptual diagram of a computer system that is used in some embodiments.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, numerous details are set forth for purpose of explanation. However, one of ordinary skill in the art will realize that the invention may be practiced without the use of these specific details. In other instances, well-known structures and devices are shown in block diagram form in order not to obscure the description of the invention with unnecessary detail.

Some embodiments of the invention provide a path search process that can identify the lowest-cost path between source and target states in a multi-layer graph with non-zero dimensional states. Such a path traverses through intermediate states often but not always. In some embodiments described below, a zero-dimensional state is a point, a one-dimensional state is a line, a two-dimensional state is a surface, a three-dimensional state is a volume, etc.

The invention's path search can be used in many different applications. However, the embodiments described below use the path search in a topological router that defines topological routes for nets in a design layout of an integrated circuit. Accordingly, in these embodiments, the multi-layer graph that the invention's path search explores is a tessellated region of an IC layout. In this tessellated region, the source, intermediate, and target states for a path search are zero-, one-, or two-dimensional topological particles. In other embodiments, the source, target, and intermediate states might be higher dimensional states (e.g., three-dimensional volumes, etc.).

The invention's path search operations can be used in different types of path searches, such as breadth-first searches, best-first searches, etc. In the embodiments described below, however, the invention's path search is described as a best-first search. This best-first search is referred to below as the Q* search. The following sections provide (i) an overview of the tessellated layout region that the Q* search explores, (ii) an overview of the Q* search, (iii) the overall flow of the Q* search, (iv) an example of a Q* search, (v) a description of the Q* search's costing of an expansion about a path, (vi) a description of the mathematical operations used by the Q* search, (vii) a description of an H function computed by the Q* engine.

I. Overview of the Region for the Path Search

In the embodiments described below, the Q* search process is used in a topological router that defines topological routes that connect the routable elements (e.g., pins) of nets in a region of a design layout. One such topological router is described in United States Patent Application entitled "Method and Apparatus for Routing Nets in an Integrated Circuit Layout", having the serial number ** and filed on Aug. 9, 2002 with the Express Mail Number EV169571226US. This application is incorporated in the present application by reference.

The topological router that is described in the above-incorporated application initially tessellates the IC-layout region, and then embeds topological routes in the tessellated region. At times, this router further tessellates the region after embedding a route. The topological router can tessellate (i.e., decompose) the region in different types of polygons, such as rectangles, etc. In the embodiments described below, each layer of the IC-layout region is decomposed into triangular faces. The above-incorporated application describes in detail the triangulation and embedding operations. However, the triangulation and embedding operations are briefly described below, to describe the tessellated region that Q* search explores in some embodiments.

A. Triangulated Region After the Initial Triangulation

The initial triangulation results in numerous triangular faces. Each resulting face has 3 edges, 3 nodes, a space representing the topological regions inside the face, and possibly a set of holes representing potential vias within the space. Nodes, edges, spaces, and holes are illustrated in FIG. 9, which presents a portion of an IC-layout layer after the initial triangulation. This figure illustrates four triangular faces, each with three nodes, three edges between the three nodes, and a space.

Some embodiments define nodes at the four corners of the layout region on each layer, at the vertices of the obstacle and pin geometries in the region, and at some or all virtual pins in the region (where virtual pins or "vpins" are points defined at the boundary of the region to account for the propagation of previously defined global routes into the region). Edges are defined between certain pairs of nodes in order to triangulate the region. Some embodiments define each edge as an ordered list of topological particles in the tessellated region. After the initial triangulation, each edge's ordered list starts and ends with a node, and has a topological particle, called an "exit," between the two nodes. For each edge, FIG. 9 illustrates two nodes and an exit between the two nodes.

The topological router defines a hole between each overlapping pair of spaces that have sufficiently large overlap to accommodate a via. To determine whether two spaces have sufficient overlap, the topological router maintains for each space a polygon that specifies the legal area where the center of vias can be in the space. The topological router then identifies the intersection of the polygons of each pair of overlapping spaces. For each overlapping space pair that has a sufficiently large polygon intersection, the router then specifies a hole to represent a potential via that can be anywhere in the identified polygonal intersection. A hole is part of both spaces that it connects. A space can contain several holes, one for each sufficiently overlapping space in an adjacent layer. FIG. 9 illustrates holes in several spaces. The topological router performs its hole-identification process for a space each time it creates or modifies a space. The above-incorporated application further described how some embodiments identify holes.

B. Triangulated Region with Embedded Routes

After the initial triangulation, the topological router embeds topological routes in the decomposed topological region. The topological router defines a topological route as an ordered list of topological particles in the decomposed topological r