REGISTER  |  SIGN IN
United States Patent7058917
Teig , ; et al.June 6, 2006
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 first polygon that encloses the set of states. It then identifies vectors to project from the vertices of the first polygon. Based on the projected vectors, the method specifies a first cost function. The method also identifies a second polygon that encloses the set of states. It also identifies vectors to project from the vertices of the second polygon. Based on the projected vectors, the method specifies a second cost function. The method then derives a third cost function from the specified cost functions.
Inventors:Teig; Steven (Menlo Park, CA), Caldwell; Andrew  (Santa Clara, CA)
Assignee:Cadence Design Systems, Inc. (San Jose, CA)
Appl. No.:10/226,482
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-14
U.S. Patent Documents
20010003843June 2001Scepanovic et al.
20010038612November 2001Vaughn et al.
20020043988April 2002Or-Bach et al.
20020100009July 2002Xing et al.
20020104061August 2002Xing et al.
20020107711August 2002Xing et al.
20020182844December 2002Igarashi et al.
20030005399January 2003Igarashi et al.
20030009737January 2003Xing
20030014725January 2003Sato et al.
20030025205February 2003Shively
20030121017June 2003Andreev et al.
20030188281October 2003Xing
20040044979March 2004Aji et al.
20040088670May 2004Stevens et al.
4777606October 1988Fournier
5224057June 1993Igarashi et al.
5578840November 1996Scepanovic et al.
5657242August 1997Sekiyama et al.
5663891September 1997Bamji et al.
5717600February 1998Ishizuka
5757089May 1998Ishizuka
5757656May 1998Hershberger et al.
5811863September 1998Rostoker et al.
5822214October 1998Rostoker et al.
5838583November 1998Varadarajan et al.
5856927January 1999Greidinger et al.
5870312February 1999Scepanovic et al.
5877091March 1999Kawakami
5880969March 1999Hama et al.
5889329March 1999Rostoker et al.
5889677March 1999Yasuda et al.
5898597April 1999Scepanovic et al.
5973376October 1999Rostoker et al.
5980093November 1999Jones et al.
6006024December 1999Guruswamy et al.
6067409May 2000Scepanovic et al.
6110222August 2000Minami et al.
6128767October 2000Chapman
6154873November 2000Takahashi
6154874November 2000Scepanovic et al.
6175950January 2001Scepanovic et al.
6209123March 2001Maziasz et al.
6216258April 2001Mohan et al.
6219823April 2001Hama et al.
6226560May 2001Hama et al.
6230306May 2001Raspopovic et al.
6247167June 2001Raspopovic et al.
6247853June 2001Papadopoulou et al.
6253363June 2001Gasanov et al.
6262487July 2001Igarashi et al.
6286128September 2001Pileggi et al.
6289495September 2001Raspopovic et al.
6292929September 2001Scepanovic et al.
6324674November 2001Andreev et al.
6324675November 2001Dutta et al.
6327693December 2001Cheng et al.
6327694December 2001Kanazawa
6330707December 2001Shinomiya et al.
6349403February 2002Dutta et al.
6407434June 2002Rostoker et al.
6412102June 2002Andreev et al.
6415426July 2002Chang et al.
6415427July 2002Nitta et al.
6434730August 2002Ito et al.
6436804August 2002Igarashi et al.
6442745August 2002Arunachalam et al.
6490713December 2002Matsumoto
6505331January 2003Bracha et al.
6601227July 2003Trimberger
6609237August 2003Hamawaki et al.
6645842November 2003Igarashi et al.
6656644December 2003Hasegawa et al.
6665852December 2003Xing et al.
6859916February 2005Teig et al.
6895569May 2005Teig et al.
Foreign Patent Documents
02-262354Oct., 1990JP
11-296560Oct., 1999JP
Other References
US. 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,202, 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/227,016, 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/288,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. Nos. 10/215,923, 10/215,563 and 10/215,896. cited by other .
U.S. Appl. No. 10/334,665, filed Dec. 31, 2002, Steven Teig et al., CIP of U.S. Appl. Nos. 10/215,923, 10/215,563 and 10/215,896. cited by other .
U.S. Appl. No. 10/335,243, filed Dec. 31, 2002, Steven Teig et al., CIP of U.S. Appl. Nos. 10/215,923, 10/215,563 and 10/215,896. cited by other .
U.S. Appl. No. 10/335,062, filed Dec. 31, 2002, Steven Teig, CIP of U.S. Appl. Nos. 10/215,923, 10/215,563 and 10/215,896. 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. Nos. 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. Nos. 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 .
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 Physical 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 .
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., Hierarachical 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: Smith; Matthew
Assistant Examiner: Tat; Binh
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 multi-state space representing a region of a design layout, a method of specifying a cost function that represents the estimated distance between an external state and a set of states in the space, the method comprising: a) identifying a first polygon that encloses the set of states; b) projecting vectors from one or more vertices of the first polygon; c) based on the projected vectors, specifying a first cost function; d) identifying a second polygon that encloses the set of states; e) projecting vectors from one or more vertices of the second polygon; f) based on the projected vectors, specifying a second cost function; and g) deriving a third cost function from the specified first and second cost functions.

2. The method of claim 1, wherein projecting vectors from vertices of the polygon comprises only projecting vectors in between which the external state is positioned.

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

4. The method of claim 1, wherein specifying a cost function based on the projected vectors comprises: using the projected vectors to identify a set of distances that includes the distance between the polygon and each point in a set of points in the external state; and using the identified set of distances to specify a cost function.

5. The method of claim 4, wherein the external state is a first point and the set of distances includes only the distance between the polygon and the first point.

6. The method of claim 5, wherein identifying the distance 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 projected vectors emanate; 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.

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

8. The method of claim 4, wherein the external state is a line.

9. The method of claim 8, wherein identifying the distance comprises: at each intersection of the line and one of the projected vectors, computing a distance; at each endpoint of the line that does not intersect one of the projected vectors, computing a distance.

10. The method of claim 9, wherein computing the distance at an intersection of the line and one of the projected vectors comprises computing the distance between a point on the line that the projected vector intersects and the polygon in the direction of the projected vector that intersects the line at the point.

11. The method of claim 10, wherein computing the distance at each endpoint of the line that does not intersect one of the projected vectors comprises: if endpoint is between two projected vectors that emanate from the same vertex, identifying the distance between the endpoint and the vertex from which the projected vectors emanate; if the endpoint 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 endpoint and the polygon.

12. The method of claim 11, wherein identifying the distance between the endpoint and the vertex from which the projected vectors emanate comprises identifying the distance between the endpoint and the vertex according to an interconnect model that specifies a set of interconnect lines for connecting the endpoint and the vertex.

13. The method of claim 4, wherein the external state is a surface.

14. The method of claim 13, wherein the surface has a plurality of vertices, wherein identifying the distance comprises: at each intersection of one of the projected vectors and the boundary of the surface, computing a distance; at each vertex of the surface that does not intersect one of the projected vectors, computing a distance.

15. The method of claim 14, wherein computing the distance at an intersection of the surface boundary and one of the projected vectors comprises computing the distance between a point on the boundary that the projected vector intersects and the polygon in the direction of the projected vector that intersects the boundary at the point.

16. The method of claim 14, wherein computing the distance at each vertex of the surface that does not intersect one of the projected vectors comprises: if 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 projected vectors emanate; 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.

17. The method of claim 16, wherein identifying the distance between the surface vertex and the polygon vertex from which the projected vectors emanate comprises identifying the distance between the surface vertex and the polygon vertex according to an interconnect model that specifies a set of interconnect lines that can be used to connect the surface vertex and the polygon vertex.

18. The method of claim 4, wherein the design layout specifies a set of interconnect line directions for connecting the external state and the set of states, wherein the projected vectors are projected in one or more of the specified interconnect line directions.

19. The method of claim 4, wherein one polygon is a four-sided polygon that is aligned with the coordinate system of the design layout, while the other polygon is a four-sided polygon that is rotated by a particular angle with respect to the coordinate system.

20. The method of claim 4, wherein deriving a third cost function comprises defining the third cost function as the minima of the specified first and second cost functions.

21. A computer readable medium that stores a computer program for specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space representing a region of a design layout, the computer program comprising instructions for: a) identifying a first polygon that encloses the set of states; b) projecting vectors from one or more vertices of the first polygon; c) based on the projected vectors, specifying a first cost function; d) identifying a second polygon that encloses the set of states; e) projecting vectors from one or more vertices of the second polygon; f) based on the projected vectors, specifying a second cost function; and g) deriving a third cost function from the specified first and second cost functions.
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 first polygon that encloses the set of states. It then identifies vectors to project from the vertices of the first polygon. Based on the projected vectors, the method specifies a first cost function. The method also identifies a second polygon that encloses the set of states. It also identifies vectors to project from the vertices of the second polygon. Based on the projected vectors, the method specifies a second cost function. The method then derives a third cost function from the specified cost functions.

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 Ser. No. 10/215,563 and filed on Aug. 9, 2002. 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 region. Each embedded topological route is a graph that has several vertices and one or more wire segments that connect some or all the vertices. In the embodiments described below, the wire segments are referred to as walls and the vertices can be nodes, holes, "joints," "via nodes," and "Steiners."

A "joint" is a topological particle that the topological router defines along an edge (i.e., in the edge's ordered list) when this router embeds a path that crosses the edge. A joint divides a previously undivided exit of an edge into two exits. Via nodes are topological particles that the router creates when it embeds a topological path (all or some of a topological route) that utilizes a hole. Specifically, to embed a path of a net that uses a hole, the router converts the hole into two via nodes, one in each space connected by the hole, and establishes an association between the two via nodes (e.g., has them refer to one another). A Steiner is a Steiner point (i.e., a vertex that connects to more than two walls) that is generated at the juncture between a pre-existing path of a net and a newly embedded path of the net. When the router embeds a path that crosses an edge, it defines a joint at the intersection of the edge and the net's path. A joint divides a previously undivided exit of an edge into two exits.

FIG. 10 illustrates two embedded topological paths 1000 and 1002. Both of these paths traverse several triangular faces on layer 2. Path 1000 also traverses two triangular faces on layer 3, as it is a multi-layer route. Path 1000 is specified by the following ordered list of particles: node 1004, wall 1006, joint 1008, wall 1010, joint 1012, wall 1014, via node 1016, via node 1018, wall 1020, joint 1022, wall 1024, and node 1026. Path 1002 is specified by the following ordered list of particles: node 1028, wall 1030, joint 1032, wall 1034, joint 1036, wall 1038, Steiner 1040, wall 1042, and node 1044. FIG. 10 also illustrates a wall 1046 of another portion of path 1002's route.

As shown in this figure, the embedded routes divide the faces that they completely cross into several spaces. For instance, these paths divide the face formed by vertices 1004, 1048, and 1050 into three spaces. Also, this figure illustrates that each joint is at the intersection of a route with an edge, and abuts two exits on its edge. The Steiner 1040 of path 1002 connects walls 1038, 1042, and 1046. In addition, multi-layer route 1000 includes two via nodes 1016 and 1018. These via nodes enable this path to traverse layers 2 and 3. The topological router generated these two via nodes from the hole 905 of FIG. 9 when it embedded the path 1000. FIG. 10 also illustrates that a wall is specified between each to non-wall, non-via particles on a path.

Each net has a representation of its connectivity and topology. Each edge has an ordered list of the routes that cross it. In other words, a route's topological particles that are on edges appear on their edge's ordered list (e.g., linked list) in the topological order that their route crosses their edge. For the example illustrated in FIG. 10, the topological router specifies the edge between nodes 1048 and 1050 as an ordered list of the following particles: node 1050, exit 1052, joint 1008, exit 1054, joint 1036, exit 1056, and node 1048. In this edge's ordered list, joints 1008 and 1036 of paths 1000 and 1002 appear in the order that their routes cross this edge.

Every particle that is within a face or is on an edge of the face is associated with one or more spaces of the face. Some particles can be part of multiple spaces. Each space contains its face's nodes and exits just after the initial triangulation. The topological router stores each edge's capacity and length, and also stores the wire flow (route flow) across each edge.

In the embodiments described below, certain particles (such as joints, via nodes, walls, and Steiners) that define a route are moveable, while other route-defining particles (such as pin-geometry nodes) have a fixed location. The topological router does not need to specify and store the location of moveable route-defining particles, as the routes are topologically defined. However, in the embodiments described below, the topological router specifies and stores locations for the route-defining particles in order to be able to compute wirelength accurately.

II. Introduction to the Q* Path Search

The Q* path search can identify the lowest-cost path between source and target states in a multi-layer graph with non-zero dimensional states. In the embodiments described below, the source, intermediate, and target states in the graph are zero-, one-, or two- dimensional topological particles in the tessellate region. In other words, these states are points (i.e., nodes), lines (i.e., edge- and wall-segments to which a path can expand), and surfaces (i.e., portions of holes polygons to which a path can expand).

In some embodiments, the Q* search process has two phases: (1) a path exploration phase, during which the process identifies a path between the specified source and target particles, and (2) a path-embedding phase, during which the process embeds the identified path. During the path exploration phase, the Q* search starts at one or more paths from the source and/or target particles. It then iteratively identifies one or more expansions about the lowest cost path, until it identifies a path that connects the source and target states. Each identified expansion about a path is from a "current particle" (also called "start particle"), reached by the path, to a "destination particle" that neighbors the current particle.

The embodiments described below cost each expansion based on an {circumflex over (F)} cost that can be expressed as: {circumflex over (F)}=G+H. (1) The {circumflex over (F)}, G, and H are functions that are defined over the entire destination particle of an expansion or one or more portions of this destination particle. Specifically, the {circumflex over (F)} cost is a function that expresses the estimated cost of a path that traverses from a source through the expansion's destination particle to a target. The G cost is a function that expresses the cost of the path that has reached the expansion's destination particle. The H cost is a function that expresses an estimated cost of a path from the expansion's destination particle to the target set. In the embodiments described below, the H cost function expresses the lower-bound estimate of the shortest path from the expansion's destination particle to the target set. Accordingly, in these embodiments, the {circumflex over (F)} cost function expresses the estimated cost of a lowest-cost path from the source through the expansion's destination particle to a target. Also, in these embodiments, the G function and hence the {circumflex over (F)} function account for several different types of path costs, such as a distance cost, route-piercing cost, via cost, wire-shoving costs, etc. Hence, the {circumflex over (F)} function of equation (1) allows the embodiments described below to identify the lowest-cost path between the source and target sets. Other embodiments, however, might utilize a different {circumflex over (F)} function, as further described below.

In the embodiments described below, the G, H, and {circumflex over (F)} functions are convex piecewise linear functions ("PLF"), although in other embodiments they might be other types of functions. In the embodiments described below, each PLF's domain is either a point, a line, or a surface in the tessellated region. In the discussion below, PLF's that are defined over a point are called point PLF's, PLF's that are defined across lines are called line PLF's, and PLF's that are defined across surfaces are called surface PLF's.

A point PLF maps the point over which it is defined to a single value. A line PLF is a PLF with a domain that is a line. Such a PLF can be specified by a sequence of vertices, called knots, that represent the endpoints of its line segments. FIG. 11 illustrates an example of a line PLF 1110 that has four line segments. This PLF specifies a PLF-value for each point P that is offset by an amount Q along an edge 1105 (i.e., for each real number Q that defines a point P on the edge at Q .cndot. u, where u is a unit vector of L). Each knot of a line PLF can be specified in terms of an offset value Q and a PLF-value V. Also, the knots of a line PLF can be sorted in an order based on their offset values. Accordingly, the five knots K1 K5 that are at the endpoints of PLF 1110's four line segments can represent this PLF of FIG. 11. These five knots can be represented by the following ordered list of offset and PLF-value pairs: (Q1, V1), (Q2, V2), (Q3, V3), (Q4, V4), (Q5, V5).

A surface PLF is a set of one or more planar surfaces, called facets. FIG. 12 illustrates an example of a surface PLF. This PLF 1210 has four facets (F1 F4), each of which has a different slope. This PLF is defined across a surface 1205. For each x-y value in the surface 1205, the surface PLF 1210 provides a PLF-value (V).

Each surface PLF can be represented by a set of knots, a set of edges between the knots, and a set of facets defined by the edges. Using this approach, the surface PLF 1210 of FIG. 12 can be represented by a list of knots K1 K10, a list of edges E1 E13, and a list of facets F1 F4. Some embodiments represent (1) a surface-PLF knot with an x,y coordinate, a PLF-value at that coordinate, and a list of edges that are incident upon the knot, (2) a surface-PLF edge by a pair of references to two knots that the edge connects, and (3) a surface-PLF facet by a list of edges, a normal vector (e.g., x, y, z coordinate values), and a z-intercept, where z is the axis in which the PLF-values are defined. For instance, in the example in FIG. 12, the list of edges for the knot K1 specifies edges E1 and E2, the list of knots for edge E4 specifies knots K3 and K4, and the list of edges for facet F1 identifies edges E1 E4. For facet F1, a normal vector N1 and a z-intercept are also specified.

In the embodiments described below, the Q* search maintains another function for each topological particle that can serve as a source, intermediate, or target state in the tessellated region. This function is called a filter function. In the embodiments described below, the filter function is a PLF. A particle's filter function expresses the lowest path cost that the search process has been able to identify from the source set to each point on the particle during a path search. As further described below, the Q* search in the embodiments described below uses the particle filter functions to determine whether a potential expansion to a destination particle is a viable one (i.e., whether the expansion provides a cheaper path to any portion of the destination particle than previously identified expansions to the destination particle). This search makes this determination for an expansion when it initially identifies the expansion and also later if it expands about it.

Filtering is when a first PLF F1 (a filtered PLF) is compared with a second PLF F2 (a filter PLF) to determine whether any portion of the F1 needs to be discarded. The filter and filtered PLF's have overlapping domains (i.e., domain(F1).andgate.domain(F2).noteq.null). In the embodiments described below, filtering discards the portion of the filtered PLF F1 that is larger than the corresponding portion of the filter PLF (i.e., discards every portion of F1 where F1(V).gtoreq.F2(V)). FIG. 13 presents an example of filtering a first filtered PLF 1305 by a second filter PLF 1310, where both PLF's are defined across a line 1350. Each PLF is represented by its sequence of knots, which is sorted by the domain-offset values. Knots K1 K5 specify the first PLF while knots K6 K10 specify the second PLF 1310. As shown in this figure, this filtering discards portion 1315 of PLF 1305 as the PLF-values of this portion are larger than the PLF-values of the corresponding portion 1320 of filter PLF 1310. After the filtering operation, two portions 1325 and 1330 of the PLF 1305 remain. Knots K1 K3 and K11 specify the first remaining portion 1325, while knots K12 and K5 specify the second remaining portion (where knots K11 and K12 are at the intersection of the PLF's 1305 and 1310).

Filtering PLF's will be further described below. The filtering that is described below not only filters the first PLF, but also defines the second filter PLF to be the minimum of the first and second PLF's. A minimum of two PLF's F1 and F3 is another PLF F3 that specifies a PLF-value for each location V in the intersection of F1's domain and F2's domain that is equal to the smallest PLF-value specified by the first and second PLF's for that location (i.e., F3(V).ident.min(F1(V), F2(V)). FIG.
14 illustrates the minimum PLF 1405 for the two PLF's 1305 and 1310 of FIG. 13. The portion 1325 and 1330 of this minimum function corresponds to the remaining portion of the filtered PLF 1305, while the portion 1320 of this minimum function is from the original filter PLF 1310. Knots K1 K3, K11, K8, K9, K12, and K5 specify the minimum function 1405.

III. Overall Flow of the Q* Path Search Process

For some embodiments, FIG. 15 illustrates a Q* search process that identifies and embeds the lowest-cost path between specified source and target particles in the tessellated region. The process 1500 initially sets (at 1502) a variable Current_Drop to null. The process 1500 uses drops to represent path expansions. Specifically, this process represents an expansion from one topological particle (called a "start particle" or "current particle") to another topological particle (called a "destination particle") by a "drop" that associates with the destination particle and refers back to the drop of the start particle. One of ordinary skill will realize that other embodiments might not use drops or might implement drops differently.

At 1504, the process 1500 initializes filter and H PLF's for each topological particle in the tessellated region that can serve as a start, intermediate, or target particle for a path search. For each such topological particle, the process 1500
maintains (1) the filter PLF to express the lowest path cost that the process has been able to identify from the source set to the particle during a path search, and (2) the H PLF to express the estimated distance between the particle and the target set. The process 1500 stores the H PLF for each particle so that it only has to compute the H PLF once for each particle. In some embodiments, the process initializes the filter and H PLF's to "infinite". Also, in the embodiments described below, nodes, exits, and holes are the topological particles that can serve as start particles during a path search, while nodes, holes, exits, and walls are the topological particles that can serve as intermediate and target particles during the path search.

Next, for each source particle of the path search, the process 1500 (at 1506) identifies and sets the particle's H PLF and sets the particle's filter PLF to zero. The generation of a particle's H PLF is described below. At 1506, for each source particle, the process 1500 also specifies a drop, defines the source particle as the drop's particle, defines the drop's prior drop as null, sets the drop's G PLF to zero, and sets the drop's {circumflex over (F)} PLF equal to the source particle's H PLF. The process stores the specified drops in a storage structure. In the embodiments described below, the storage structure is a priority queue (e.g., a heap) that is sorted based on the minimum of the {circumflex over (F)} PLF of each drop.

At 1508, the process then retrieves from the priority queue a drop with the smallest minimum {circumflex over (F)} value. Next, the process filters (at 1510) the retrieved drop's G PLF with the filter PLF of this drop's particle. As further described below, the process performs this filtering operation to ensure that the retrieved drop is still valid. After the process 1500 stored the retrieved drop in the priority queue, it might have created and stored other drops that represent cheaper expansions to the retrieved drop's particle. These cheaper expansions would have modified the filter PLF of the retrieved drop's particle.

FIG. 16 illustrates one such situation. This figure illustrates a G PLF 1605 of a first expansion to a line 1610. This G PLF is also the filter function of the line 1610 after the first expansion. FIG. 16 illustrates a G PLF 1615 of a second expansion to the line 1610. The second expansion's G PLF 1615 is smaller than the first expansion's G PLF 1605 over the entire line 1610 except for the portion 1625 of the line. After the second expansion is identified, the filter function of the line
1610 is set to the minimum of the second expansion's G PLF and the filter function's original PLF (which, as mentioned above, is identical to the first expansion's G PLF). This new filter function is the PLF 1620 in FIG. 16.

Accordingly, after retrieving a drop from the priority queue, the process 1500 filters (at 1510) the drop's G PLF with its particle's filter function to ensure that the drop still represents the best valid expansion to one or more portions of its particle. In the example illustrated in FIG. 16, the filtering of the G PLF 1605 of the first expansion to (i.e., the first drop on) the line 1610 with the line's filter PLF 1620 after the second expansion results in the PLF 1630. This PLF 1630
corresponds to the portion of the original PLF 1605 of the first expansion that is smaller than the second-expansion's PLF 1615. This PLF 1630 is defined over a much smaller domain (i.e., segment 1625) than the original PLF 1605 for the first expansion. Filtering one function against another will be further described below.

At 1512, the process determines whether any portion of the Current_Drop's G PLF remains after the filtering operation. If the process determines (at 1512) that at least one portion of the Current_Drop's G PLF remains after the filtering, the process determines (at 1514) whether the filtering operation at 1510 resulted in two or more convex pieces of the retrieved drop's G PLF.

If the filtering did not result in two or more convex pieces, the process specifies (at 1516) the retrieved drop's {circumflex over (F)} PLF again, as some portions of this drop's G PLF might have been discarded because of the filtering operation, and such a modification would discard some portions of this drop's {circumflex over (F)} PLF. Next, the process determines (at 1518) whether the retrieved drop's {circumflex over (F)} PLF minimum is greater than the lowest {circumflex over (F)} PLF minimum of the drops that are currently stored in the priority queue. If so, the process stores (at 1522) the retrieved drop again in the priority queue, and then transitions back to 1508 to select another drop. Otherwise, the process specifies (at 1520) the retrieved drop as the Current_Drop and then transitions to 1532, which will be further described below.

If the process determines (at 1514) that the filtering at 1510 resulted in two or more convex pieces of the retrieved drop's G PLF, the process specifies (at 1524) a drop for each remaining piece and sets their parameters as follows. The process defines each specified drop's particle as the retrieved drop's particle. It also sets each specified drop's previous drop identically to the retrieved drop's previous drop (which might be null). The process also sets each specified drop's G PLF equal to the portion of the retrieved drop's G PLF for which the drop was specified. It also sets each specified drop's {circumflex over (F)} PLF equal to the sum of (1) the specified drop's G PLF, and (2) the portion of the retrieved drop's H PLF with the same domain as the specified drop's G PLF.

At 1526, the process then determines whether any of the drops created at 1524 has the lowest {circumflex over (F)} PLF minimum of all the drops stored in the priority queue. If not, the process stores (at 1528) the drops specified at 1524 in the priority queue based on the minimum of the {circumflex over (F)} PLF of each drop. From 1528, the process transitions back to 1508 to select another drop. On the other hand, if the process determines (at 1526) that at least one drop specified at 1524
has the lowest {circumflex over (F)} PLF minimum of all the drops stored in the priority queue, the process identifies (at 1530) as the Current_Drop a drop that was specified at 1524 and that has the lowest {circumflex over (F)} PLF minimum. At 1530, the process also stores the remaining specified drops in the priority queue based on the minimum of the {circumflex over (F)} PLF of each drop.

From 1530, the process transitions to 1532. The process also transitions to 1532 from 1520. At 1532, the process determines whether the Current_Drop's particle is a target. If not, the process tries (at 1534) to expand the path search about the Current_Drop. Specifically, at 1534, the process tries to identify one or more potential expansions about the Current_Drop. Some embodiments identify potential expansions about the Current_Drop by (1) identifying a set of valid spaces to which a path can expand from the Current_Drop's particle, and (2) identifying destination particles in each identified space. A valid space is one that contains the Current_Drop's particle but does not contain the particle of the prior drop in a path search (i.e., does not contain the particle of the Current_Drop's previous drop). FIG. 17 illustrates an example of a valid expansion space for a planar expansion. This figure illustrates a path search 1705 that has a last drop 1710 and a second-to-last drop
1715. The particles of both these drops are part of space 1725. The particle of drop 1710 is also part of space 1720. Consequently, space 1720 is a valid expansion space for drop 1710, but space 1725 is not. There can be multiple viable expansion spaces as a retrieved drop's particle (such as a node) can be in multiple spaces. One of ordinary skill will realize that other embodiments might identify potential expansions about the Current_Drop differently. For instance, some embodiments might define a valid space for an expansion differently. One such embodiment might not require that the Current_Drop's particle to be part of the valid space.

After the process identifies (at 1534) a set of valid spaces to which the path can expand from the Current_Drop's particle, it identifies (at 1534) potential destination particles in each identified space. In some embodiments, a path can expand towards exits, walls and holes, as well as the selected net's nodes, in a valid expansion space. One of ordinary skill will realize that other embodiments might specify other potential expansion particles in a valid expansion space.

In the example illustrated in FIG. 17, the path search can expand from drop 1710 to exit 1745, hole 1750, and wall 1725. Wall 1725 belongs to a route 1730 of another net. The path generation process 1500 might allow a path expansion to the wall of another net's previously defined path because it might allow later defined routes to rip up earlier defined routes. In such cases, expanding to the walls of another net's path is assessed a penalty, as further described below.

In some situations, the process 1500 cannot identify (at 1534) any potential expansions to another particle. However, when the process identifies one or more potential expansions at 1534, the process performs the following four operations at
1534. First, it specifies the H PLF of each potential expansion's destination particle if it had not previously been set for the path search. The generation of the H PLF is described below. Second, the process specifies a G PLF for each potential expansion. The generation of the G PLF for an expansion (i.e., the costing of an expansion) is described below. Third, it filters the G PLF of each potential expansion with the filter PLF of the expansion's destination particle. This filtering operation also sets the destination particle's filter PLF equal to the minimum of the filtered G PLF and the destination particle's previous filter PLF. Filtering two PLF's is described below. Fourth, the process specifies a drop for each convex piece (if any) of a G PLF of a potential expansion that remains after the filtering operation. For each specified drop, the process (1) sets the drop's G PLF equal to the remaining piece of the filtered G PLF for which the drop was created, (2) associates the drop with its expansion's destination particle, (3) sets the drop's previous drop to the Current-Drop, and (4) sets the drop's {circumflex over (F)} PLF to the sum of the drop's G PLF and the portion of its destination particle's H PLF that is defined over the domain of the drop's G PLF. The process stores each drop it creates at 1534 in the priority queue.

From 1534, the process transitions to 1536. The process also transitions to 1536 if it determines at 1512 that no portion of a retrieved drop's G PLF remains after the filtering at 1510. At 1536, the process determines whether the priority queue that stores the drops is empty. If so, the process has failed to find a path between the specified source and target sets. Accordingly, it returns (at 1538) a notification specifying its failure and then ends. On the other hand, when the process determines (at 1536) that the priority queue is not empty, the process transitions back to 1508 to retrieve the next lowest-cost drop from this priority queue and then to perform the subsequent operations for this drop.

The process has found a path between the source and target sets when it determines (at 1532) that the Current_Drop's particle is a target. In this situation, the process transitions from 1532 to 1540. At 1540, the process 1500 performs a back trace operation to embed topologically the identified path between the source set and the target. Starting at the Current_Drop on the target, this operation "back traces" the sequence of drops that reached the target and generates an ordered list of topological particles that define the topological path. Generation of such an ordered list entails creation of wall particles between each pair of non-wall, non-via particles in the topological path, and can also entail the creation of joints, Steiners, and via nodes. In some embodiments, this operation also specifies coordinates for each topological particle that it creates. The back trace operation is further described in the above-incorporated application.

One of ordinary skill will realize that the Q* path-generation process might be implemented differently in other embodiments. For instance, some embodiments might utilize non-convex PLF's. Also, in some embodiments, the H cost function might not specify a lower bound on the shortest path between a drop's particle and a target set. In addition, some embodiments might compute the {circumflex over (F)} function slightly differently. For instance, some embodiments might express the {circumflex over (F)} function as: {circumflex over (F)}=G+2*H. Such a function would bias the search process to expand about the drops that are closer to the target set. Alternative embodiments might express the {circumflex over (F)} function as: {circumflex over (F)}=G+H+ , where represents the estimated computational effort needed to complete the path from the current drop. The embodiments that use alternative {circumflex over (F)} function do not satisfy the admissibility requirement (i.e., they do not produce consistently the lowest-cost path between source and target sets). On the other hand, the embodiments that use the {circumflex over (F)} function of equation (1) do satisfy this requirement. IV. Example of the Q* Search Process

FIG. 18 presents an example of the Q* path search. In this example, the Q* search process is used to construct the lowest-cost path between a single source node 1805 and a set of target nodes 1810 in a triangulated graph 1800. To simplify this example, the only source and target particles are nodes, and the only intermediate particles are edges. Also, this example accounts only for the distance costs, and ignores spacing constraints on edges due to obstacles.

FIG. 18 illustrates several sets of expansions identified during a path exploration phase. The expansions are represented by drops 1a, 1b, 2, 3a, 3b, 4a, 4b, 5 7, 8a, 8b, 9, 10, and 11. In this example, the Q* path search starts by identifying and storing drops 1a and 1b about the source node 1805. This process then successively identifies the sequence of drops 2, 3a and 3b, and 4a and 4b. It identifies this sequence by successively (1) identifying each of the drops 1a, 2, and 3a as the drops in the priority queue with the lowest {circumflex over (F)} function minimum, and (2) identifying viable expansions about each of the edges of these drops. Once the process creates and stores expansion drops 4a and 4b as viable expansions from drop 3a, the process identifies drop 1b as the drop with the lowest {circumflex over (F)} function minimum in the priority queue. Accordingly, it then successively identifies the sequence of drops 5, 6, 7, 8a, 8b, 9, 10, and 11 that reaches the target set 1810. The process identifies this sequence by successively (1) identifying each of the drops 5, 6, 7, 8a, 9 as the drops in the priority queue with the lowest {circumflex over (F)} function minimum, and (2) identifying viable expansions about the edge of each of these drops.

In this example, two expansions are identified to each of the following four edges 1825, 1830, 1835, and 1840. The search process identifies the first expansions (i.e., identifies drops 3a, 3b, 4a, and 4b) to these edges when it expands about drops 1a, 2, 3a, 3b, and 4a, while it identifies the second expansions (i.e., identifies drops 6, 7, 8a, and 8b) to these edges when it expands about drops 5, 6, and 7. The second set of drops (i.e., drops 6, 7, and 8b) that are identified for the edges
1825, 1830, and 1840 are only specified over portions 1845, 1850, and 1855 of these edges. This is because the filtering operations that were performed to assess the viability of these second expansions to edges 1825, 1830, and 1840 resulted in the filtering of their G PLF's outside of the portions 1845, 1850, and 1855. However, the second drop 8a on edge 1835 is defined over the entire edge, as the filtering operation that the process performs before identifying this drop does not filter any portion of this expansion's G PLF. This is because the entirety of the edge 1835 can be reached more cheaply through the sequence of drops 1b, 5, 6, and 7 than through the sequence of drops 1a, 2, and 3a.

In the example illustrated in FIG. 18, the lowest-cost path is the one represented by drops 11, 9, 8a, 7, 6, 5, 1b, and 12, where drop 12 is the drop created for the source node 1805. After identifying this sequence of drops, the Q* search process embeds a path for this sequence. An approximation of this embedded path is illustrated in FIG. 19. As shown in FIG. 19, joints are defined at the intersection of the embedded path and the edges that this path intersects.

V. Computing G PLF

When the process 1500 identifies (at 1534) a potential expansion from the Current_Drop's particle to a destination particle, this process specifies (at 1534) a G PLF for such a potential expansion. In some embodiments, the process 1500 computes this G PLF by (1) propagating the Current_Drop's G PLF to the destination particle, and (2) for certain expansions, adding one or more penalty costs to the PLF resulting from the propagation.

A. Propagation

Propagating the Current_Drop's G PLF to an expansion's destination particle generates a PLF that expresses the distance and penalty costs of reaching the Current_Drop's particle plus the distance cost of reaching the expansion's particle from the Current_Drop's particle. In other words, the propagation accounts for the extra distance cost of going from the Current_Drop's particle to the expansion's particle.

Some embodiments limit each propagation operation to only the portion of the expansion's destination particle to which a path can expand from the Current_Drop. The discussion below uses the phrase "destination state" to refer to the portion of an expansion's destination particle to which a path can expand from the Current_Drop. This discussion also uses the phrases "the Current_Drop's domain" or "the start domain" to refer to the domain of the Current_Drop's G PLF.

Nine different propagation operations are described below for nine pair-wise combinations of expansions between points, line, and surfaces. In these propagation operations, points represent nodes, lines represent edge- and wall-segments to which a path can expand, and surfaces represent portions of holes to which a path can expand.

As mentioned above, a hole is specified between each pair of overlapping spaces when the intersection of the two polygons of the overlapping spaces is larger than a threshold size. Such a hole represents a potential via that can be anywhere in the polygonal intersection of the two polygons of the two overlapping spaces. In some embodiments, a path for a net can expand to each portion of a hole. These embodiments might specify the same width and spacing constraints for all nets being routed at a given time, or might construct each hole for the worst case of constraints (e.g., construct the polygons of the hole's overlapping spaces for the worst case of constraints). Alternatively, some embodiments construct each hole based on the best case of constraints (e.g., construct the polygons of the hole's overlapping spaces for the best case of constraints). For an expansion of a path of a net to a hole, these embodiments then identify a sub-set of the hole's polygon (i.e., the polygonal surface represented by the hole) to which the net's path can expand given the spacing constraints for the net. One manner for identifying the sub-set of hole polygons is described in the above-incorporated application.

1. Expansion from Point to Point

To perform a propagation operation for an expansion that goes from an expansion start point to an expansion destination point (e.g., goes from one node to another node), the process 1500 identifies the distance between the two points and adds this distance to the G PLF of the start point (i.e., to the Current_Drop's G PLF). In some embodiments, the process measures the distance between two points in an IC layout using only a specified set of wiring directions that are specified by the layout's wiring model. For instance, when two points are on an octilinear layer that can have horizontal, vertical, and .+-.45.degree. diagonal interconnect lines, the distance between the two points is the shortest distance that can be traversed by using horizontal, vertical, and .+-.45.degree. diagonal interconnect lines. As disclosed in United States patent application entitled "Hierarchical Routing Method and Apparatus that Utilize Diagonal Routes," and having Ser. No. 10/013,813, the shortest distance between two points for such an octilinear wiring model: Distance=L+S*(sqrt(2)-1), (2) where L and S respectively represent the long and short sides of a rectangular bounding box that is aligned with the layout's x-y axes and that encompasses the two points. This manner of computing the shortest distance does not disfavor or penalize any preferred wiring direction over another preferred wiring direction.

Numerous other operations below require the computation of the distance between two points. The embodiments described below compute each such distance according to the above-described equation (2).

2. Expansion from Point to Line or Point to Surface

FIG. 20 illustrates a process 2000 that propagates a PLF that is defined over a point to a line or a surface. This process is described below by reference to FIG. 21, which illustrates an example of propagating a PLF from a point P to a line L, and FIG. 22, which illustrates an example of propagating a PLF from a point P to a surface S.

As show in FIG. 20, the process 2000 initially projects (at 2005) vectors in all available interconnect directions from the Current_Drop's point. These vectors are referred to below as propagation vectors. The embodiments described below utilize a wiring model that specifies horizontal, vertical, and .+-.45.degree. diagonal interconnect lines on each layer. Accordingly, these embodiments project vectors in the 0.degree., 45.degree., 90.degree., 135.degree., 180.degree., 225.degree.,
270.degree., and 315.degree. directions. FIGS. 21 and 22 illustrate eight propagation vectors emanating from their points P in 0.degree., 45.degree., 90.degree., 135.degree., 180.degree., 225.degree., 270.degree., and 315.degree. directions. Some embodiments do not project vectors in all interconnect directions. Instead, they project only the propagation vectors that will intersect the destination state. These propagation vectors are the vectors that fall within a triangle defined by the start-state point and the leftmost and rightmost vertices of the destination state.

At 2010, the process then identifies the intersection of the projected propagation vectors and the destination line or surface. A propagation vector intersects with a line at a point that is the location of a knot of the destination's line PLF. FIG. 21 illustrates the intersection of the propagation vectors 2105, 2110, and 2115 at three points 2120, 2125, and 2130 along line L. A propagation vector intersects a surface either (1) at only a vertex of the surface, or (2) at two points on the surface boundary and an edge that runs through the surface. FIG. 22 illustrates the intersection of two propagation vectors 2215 and 2220 with the surface S along edges 2270 and 2275, which respectively terminate on boundary point pair 2225 and 2230 and point pair 2235 and 2240.

Next, for the expansion to the destination state, the process 2000 then specifies (at 2015) a G PLF with knots at the intersections identified at 2010. Specifically, for a destination line, the process 2000 specifies (at 2015) a knot at each point of the destination line that a propagation vector intersects. FIG. 21 illustrates a G PLF 2145 with three knots 2150, 2155, and 2160 for the three intersection points 2120, 2125, and 2130. For a destination surface, the process 2000 specifies (at
2015) a knot at each surface vertex intersected by a propagation vector and a knot at each surface boundary point intersected by a propagation vector. FIG. 22 illustrates a G PLF 2260 with four knots 2280, 2282, 2284, and 2286 that are defined for four boundary intersection points 2225, 2230, 2235, and 2240.

At 2015, the process 2000 sets the PLF-value of each knot that it specifies at 2015. The PLF-value of a knot specified at 2015 equals (1) the Current_Drop's PLF-value at the start point, plus (2) the distance between the knot's x,y coordinates and the start point P, where this distance is measured along the direction of the propagation vector that was used to identify the knot. For example, in FIG. 41, the PLF-value of knot 4155 equals the PLF-value at point P plus the distance D between point P and intersection point 4125 along the direction of propagation vector 4110. In FIG. 22, the PLF-value of knot 2286 equals the PLF-value at point P plus the distance D between point P and intersection point 2240 along the direction of propagation vector 2220.

At 2020, the process specifies knots for the expansion's G PLF at the location of any unexamined vertex of the destination state. The vertices of a destination line are its endpoints. A line endpoint is an unexamined vertex if none of the projected propagation vectors intersect the destination line at the endpoint. The PLF-value of an unexamined endpoint of a destination line equals (1) the Current_Drop's PLF-value at the start point, plus (2) the distance (according to the equation (2)) between the start point and the endpoint. For instance, in FIG. 41, the process specifies two knots 4165 and 4170 at the endpoints 4175 and 4180 of the line L, and specifies the PLF-value of each of these knots as the PLF-value at point P plus the distance (according to equation (2)) between point P and each knot location 4175 or 4180.

The vertices of a destination surface are the vertices of the edges that define the surface's external boundary. Such a vertex is an unexamined vertex if none of the propagation vectors intersect the destination surface at the vertex. In FIG.
22, the destination surface S has five vertices 2265, all of which are "unexamined" as they are not at the intersection of the propagation vectors and the surface. Accordingly, five knots 2290 are specified at the unexamined vertices 2265. The PLF-value for each such knot equals (1) the distance (according to equation (2)) between the start point and the surface's vertex that corresponds to the knot, plus (2) the Current_Drop's PLF-value at the start point. For instance, the PLF-value of knot
2290a equals the PLF-value at the start point P plus the distance (according to equation (2)) between point P and vertex 2265a.

For a destination surface, the process 2000 uses (at 2025) the knots specified at 2015 and 2020 to specify the edges and facets of the surface PLF that is defined over the destination surface. For each facet, the process defines a normal and a z-intercept. Standard plane-defining techniques can be used to derive the normal and z-intercept values of a facet from three points on the facet. For each facet, the process 2000 identified at least three knots at 2015 and 2020.

3. Line to Line or Surface to Line

FIG. 23 illustrates a process 2300 for propagating a PLF from a line to another line or from a surface to a line. This process is described by reference to FIG. 24, which illustrates the propagation of a line PLF from a line 2405 to another line
2410, and FIG. 25, which illustrates the propagation of a surface PLF from a surface 2502 to a line 2504.

As shown in FIG. 23, the process 2300 initially identifies (at 2305) the propagation vectors that emanate from the locations on the Current_Drop's domain that are locations of knots in the Current_Drop's G PLF. The identification of these propagation vectors is further described below by reference to FIGS. 26 31. In FIG. 24, knots are located at points 2415 and 2420 on line 2405. In FIG. 25, knots are located at vertices 2506 2518 of surface 2502.

Next, at 2310, the process 2300 projects the propagation vectors identified at 2305. FIG. 24 illustrates the projection of five propagation vectors from knot-location 2415 and five propagation vectors from knot-location 2420. In FIG. 25, three propagation vectors are projected from each of the vertices 2506, 2512, and 2514, two propagation vectors are projected from each of the vertices 2508 and 2518, and one propagation vector is projected from each of the vertices 2510 and 2516. In some embodiments, the process 2300 does not project (at 2310) vectors in all interconnect directions. Instead, it projects only the propagation vectors that will intersect the destination state. In these embodiments, this process projects propagation vectors that fall within a triangle defined by the knot-location and the leftmost and rightmost vertices of the destination line or surface.

The process 2300 identifies (at 2315) the intersection of the destination line and the propagation vectors that were projected at 2310. FIG. 24 illustrates the intersection of the propagation vectors 2430 and 2435 and the line 2410 at points
2450 and 2455. FIG. 25 illustrates the intersection of the propagation vectors 2522, 2524, and 2526 and the line 2504 at points 2530, 2532, and 2534.

Each intersection identified at 2315 is a knot in the expansion's G PLF. Accordingly, for the expansion to the destination line, the process specifies (at 2320) a line G PLF with a knot at each intersection identified at 2315. At 2320, the process computes the PLF-value of each knot specified at 2320. The PLF-value of each destination-state knot equals (1) the PLF-value of the Current_Drop's knot that was used to identify the destination-state knot, plus (2) the distance between the x,y coordinates of the Current_Drop and destination-state knots, where this distance is measured along the projected propagation vector that identified the destination-state knot.

For instance, in FIG. 24, the PLF-value of knot 2472, which is defined at the intersection 2450 of the propagation vector 2430 and the line 2410, equals (1) the PLF-value of the Current_Drop's G PLF at 2420 on the line 2405, plus (2) the distance D1 between points 2420 and 2450 along the direction of the propagation vector 2430. Similarly, in FIG. 25, the PLF-value of knot 2524, which is defined at the intersection 2532 of the propagation vector 2524 and the line 2504, equals (1) the PLF-value of the Current_Drop's G PLF at 2512 on the surface 2502, plus (2) the distance D2 between points 2512 and 2532 along the direction of the propagation vector 2524.

At 2325, the process specifies knots for the expansion's G PLF at the location of unexamined vertices of the destination line, and then terminates. As mentioned above, an unexamined vertex of a destination line is an endpoint of the line that does not intersect any of the projected propagation vectors. An unexamined destination-line vertex can be in either (1) a "wedge" that is defined by two propagation vectors that emanate from the same location on the Current_Drop's domain, (2) a "channel" that is defined by two parallel propagation vectors that emanate from two different locations on the Current_Drop's domain. The PLF-value of a knot specified for an unexamined vertex that is within a wedge defined by two propagation vectors emanating from the same start-state location equals (1) the PLF-value of Current_Drop's G PLF at the start-state location, plus (2) the distance (according to the equation (2)) between the start-state location and the unexamined vertex. On the other hand, the PLF-value of a knot specified for an unexamined vertex that is within a channel defined equals (1) the length of a line segment that is parallel to the two channel-defining vectors and that starts at the unexamined vertex and terminates at the start domain, plus (2) the PLF-value of the Current_Drop's G PLF at the point that the line segment terminates on the start domain. The line segment terminates on the start domain on a second line segment that is between the two knot locations from which the two channel-defining vectors emanate. When the start domain is a surface, the second line segment (1) is an edge on the boundary of the surface if the two knot locations are boundary vertices of the surface, and (2) is a line segment within the surface if the two channel-defining knot locations are within the surface.

For instance, in FIG. 24, endpoint 2445 of the line 2405 falls within a channel defined by propagation vectors 2425 and 2430. The distance between endpoint 2445 and line 2405 is the length D3 of a line segment 2440 that is parallel to vectors
2425 and 2430. Accordingly, the PLF-value of the knot 2476 specified at endpoint 2445 equals the length D3 plus the PLF-value of the Current_Drop's G PLF at point 2480, which is the location that line segment 2440 intersects line 2405. The endpoint
2460, on the other hand, is within a wedge defined by two propagation vectors 2435 and 2482 that emanate from the start-state location 2420 on the line 2405. Accordingly, the PLF-value for the knot 2478 that is specified at 2460 equals (1) the PLF-value of the Current_Drop's G PLF at the start-state location, plus (2) the distance between points 2460 and 2420 according to the equation (2).

In FIG. 25, endpoint 2554 falls within a channel defined by propagation vectors 2520 and 2522. The distance between endpoint 2554 and surface 2502 is the length D4 of a line segment 2560 that is parallel to vectors 2520 and 2522. Accordingly, the PLF-value of the knot 2550 specified at point 2554 equals the length D4 plus the PLF-value of the Current_Drop's G PLF at point 2562, which is the location that the line segment 2560 intersects the surface boundary. The endpoint 2556, on the other hand, is within a wedge defined by two propagation vectors 2526 and 2564 that emanate from the start-state location 2512. Accordingly, the PLF-value for the knot 2552 that is specified at 2556 equals (1) the PLF-value of the Current_Drop's G PLF at the start-state location 2512, plus (2) the distance between points 2512 and 2556 according to the above-described equation (2).

FIGS. 26 31 illustrate how some embodiments identify the propagation vectors that emanate from the knot locations of a line PLF or surface PLF. These embodiments identify the propagation vectors based on the following observations. At most eight propagation-vector wedges can be defined about a Current_Drop's domain when the octilinear wiring model that provides horizontal, vertical, and .+-.45.degree. diagonal interconnect lines on each layer is used. Knots can be the only sources for wedges.

As mentioned above, each wedge is defined by two propagation vectors that emanate from the same knot location. Two wedges are abutting wedges when they share a propagation vector, while two wedges are adjacent wedges when they have parallel propagation vectors. For instance, FIG. 26 illustrates eight wedges 2650 2664 that are defined about five knot locations 2625 2645 from a surface PLF's domain 2600. In this figure, there are three abutting wedge pairs, and five adjacent wedge pairs. For instance, wedges 2658 and 2656 are abutting wedges as they share vector 2666, while wedges 2654 and 2656 are adjacent wedges as their vectors 2668 and 2670 are parallel.

The parallel propagation vectors of two adjacent wedges define a freeway. For instance, a freeway 2672 exits between adjacent wedge pairs 2662 and 2664 in FIG. 26. This freeway either (1) defines a channel when no other propagation vectors emanates from a knot location that falls within the freeway, or (2) contains two or more channels when other propagation vectors that are parallel to the freeway emanate from knot location(s) that fall(s) within the freeway. At most there are eight adjacent wedge pairs about a Current_Drop's domain. Consequently, there are at most eight freeways between the adjacent wedge pairs.

Some embodiments define the direction of the propagation vectors that emanate from an a Current_Drop's domain by performing the following three operations. First, they identify the knot location for each wedge. Second, these embodiments identify one or more freeways between adjacent wedge pairs. Third, for each identified freeway, these embodiments determine whether to treat the freeway as one channel, or to define additional channels within the freeway by defining one or more propagation vectors that are parallel to the freeway-defining vectors and that emanate from knot location(s) that fall within the freeway. The first operation (i.e., the identification of the knot location for each wedge) is described below by reference to FIGS. 27 and 28. The second and third operations (i.e., the identification of freeways and additional channels within the freeways) are then described by reference to FIGS. 29 31.

FIG. 28 illustrates a process 2800 that identifies the knot location for each propagation-vector wedge that emanates from the Current_Drop's domain, which can be a line or a surface. This process will be described by reference to an example illustrated in FIG. 27. This example illustrates how one of the wedges of the PLF-surface domain 2600 of FIG. 26 is identified.

The process 2800 initially selects (at 2805) a wedge. There are eight wedges when the octilinear wiring model that specifies horizontal, vertical, and .+-.45.degree. diagonal interconnect lines on each layer is used. The process then selects (at 2810) a knot location as the first candidate location for the source of the selected wedge, and records this knot location as the current best (Current_Best) location for the selected wedge. FIG. 27 illustrates a selected wedge 2660 and a first candidate knot location 2610. Next, at 2815, the process selects a second candidate knot location for the source of the selected wedge and records it as Next_Candidate location. In FIG. 27, the second candidate location is location 2625.

At 2820, the process then determines whether the Current_Best knot location is a better candidate location than the Next_Candidate location. This determination ensures that all locations in the wedge are best reached from the source of that wedge, when both distance and PLF-value is considered. To make this determination, the process performs the following four operations. First, the process uses the selected wedge's "vector," which in some embodiments is defined to be a unit vector that bisects the wedge (i.e., it is midway between the two vectors that define the wedge). FIG. 27 illustrates the vector 2705 of the selected wedge 2660.

Second, the process computes the dot product of the selected wedge's vector and a vector that starts from Current_Best knot location and terminates on Next_Candidate knot location. This computation quantifies whether the Next_Candidate knot location is closer to an arbitrary point in the wedge than the Current_Best knot location. FIG. 27 illustrates a vector 2710 from the Current_Best location 2610 to the Next_Candidate location 2625.

Third, after computing the dot product, the process computes a Cost_Delta, which is the difference in the PLF-values of Next_Candidate location and the Current_Best location according to the Current_Drop's G PLF (Cost_Delta=G PLF(Next_Candidate)-G PLF(Current_Best)). For the example in FIG. 27, the Cost_Delta is the difference in the PLF-values at locations 2625 and 2610.

Fourth, the process determines whether the computed dot product is greater than the Cost_Delta. If not, the Current_Best location is better than the Next_Candidate location, and the process transitions from 2820 to 2830, which is further described below. If so, the Next_Candidate location is a better location for the wedge than Current_Best location, and the process transitions from 2820 to 2825. At 2825, the process sets the Current_Best location equal to the Next_Candidate location, and then transitions to 2830. At 2830, the process determines whether it has examined all knot locations for the wedge selected at 2805. If not, the process selects (at 2835) another knot location, sets this knot location as the Next_Candidate, and transitions to 2820 to compare this newly selected Next_Candidate with the Current_Best.

When the process determines at 2830 that it has examined all the locations of knots in the Current_Drop's G PLF, the process defines (at 2840) Current_Best as the knot location for the selected wedge. The process then determines (at 2845) whether it has examined all the wedges. If not, it returns to 2805 to select another wedge and to repeat its operations for this wedge. Otherwise, it ends.

After identifying the locations of the wedges, the Q* engine has to specify the channels between the wedges. When two wedges abut (i.e., when they share a propagation vector), no channel can exist between the wedges. However, when two wedges are adjacent wedges (i.e., when they have parallel propagation vectors) one or more channels can be defined in the freeway defined by the parallel vectors of the adjacent wedge pairs.

If the Current_Drop's domain is a line, the Q* engine examines each adjacent wedge pair that is defined along the line. If no knot location exists on the line segment between the adjacent wedge pair, then the Q* engine defines the freeway between the adjacent wedge pair as a channel. If one or more knot locations exist on the line segment between an adjacent wedge pair, the Q* engine examines each knot location to determine whether they are sources of propagation vectors. The engine initially sorts in descending order the PLF-values of the knot locations between the adjacent wedge pair. If there is only one knot location between the adjacent wedge pair, the engine simply adds this PLF-value to its sorted list. The engine then selects the largest PLF-value on the sorted list. The Q* engine then identifies the channel that contains the knot location corresponding to the selected PLF-value. This channel is the freeway formed by the adjacent wedge pair when the knot location is the first location between the wedge pair that is examined. When the knot location is not the first location between the wedge pair, the channel might be formed by one or two propagation vectors that the engine specified for knot locations (between the wedge pair) that it previously examined.

The engine next determines whether the selected PLF-value for the knot location is less than the PLF-value that can be obtained by linearly interpolating between the values at the knot locations of the vectors that define the channel that contains the selected PLF-value's knot location (i.e., determines if the selected value is below a line that connects the PLF-values at the knot locations from which the identified-channel's vectors emanate). If so, the engine specifies a channel-defining vector at the knot location associated with the selected PLF-value. This specified vector is parallel to the parallel vectors of the adjacent wedge pair.

FIG. 29 illustrates an example of a knot location 2930 that is between two adjacent wedge pairs (where one pair is formed by wedges 2910 and 2915 and one pair is formed by wedges 2920 and 2925). This knot location is examined for each of these adjacent wedge pairs. When the engine examines location 2930 for adjacent wedges 2910 and 2915, it determines whether the PLF-value of this location is smaller than the PLF-value that can be obtained for this location by linearly interpolating between the PLF-values at knot locations 2945 and 2950 that serves as the emanating location of the wedges 2910 and 2915. In FIG. 29, it is assumed that the PLF-value of location 2930 is less than the PLF-value that can be obtained through the linear interpolation. Accordingly, two propagation vectors 2935 and 2940 are defined for the knot location 2930. The propagation vector 2935 is parallel to the parallel vectors of adjacent wedges 2910 and 2915, while the propagation vector 2940 is parallel to the parallel vectors of adjacent wedges 2920 and 2925.

FIG. 30 illustrates a process 3000 for defining channels between adjacent wedge pairs when the Current_Drop's domain is a surface. This process will be described by reference to FIG. 31A, which illustrates the domain 3100 of a surface PLF. The process 3000 initially identifies (at 3005) all adjacent wedge pairs. It then selects (at 3010) one of the adjacent wedge pairs. In FIG. 31A, the selected pair of adjacent wedges are wedges 3105 and 3110.

Next, at 3015, the process projects each location of a knot (in the Current_Drop's G PLF), which falls within the freeway that the selected wedge pair defines, towards a line that connects the knot locations from which the wedge pair emanates. The projection is in a direction that is parallel to the adjacent-wedge-pair vectors that define the freeway. In FIG. 31A, knot locations 3120, 3125, 3130, 3135, 3140, and 3142 fall within the freeway 3115 between the adjacent wedges 3105 and 3110. Also, the two wedges emanate from knot locations 3145 and 3150, and an edge 3170 exists between these two locations. Knot location 3120 lies on the edge 3170, and hence does not need to be projected towards this line segment. On the other hand, knot locations 3125, 3130, 3135, 3140, and 3142 need to be projected towards this line segment in the direction of the vectors 3155 and 3160 that define the freeway 3115. FIG. 31A illustrates the projection of knot location 3125 towards this edge.

At 3015, the process then computes a cost at the intersection of each projection with the line. The cost at each intersection point equals the sum of the PLF-value of the G PLF at the