Method and apparatus for producing multi-layer topological routes


United States Patent		6898773
Teig , ; et al.		May 24, 2005

	*Title*

Method and apparatus for producing multi-layer topological routes

	*Abstract*

Some embodiments of the invention provide a method for identifying topological routes in a multi-layer region of a design layout. The method selects a first net that has several routable elements. For the selected net, it then specifies a first multi-layer topological route that connects the first net's routable elements before selecting another net for routing. The first topological route traverses a plurality of layers. In addition, a topological route is a route that represents a set of diffeomorphic geometric routes.



Inventors:	Teig; Steven (Menlo Park, CA), Caldwell; Andrew (Santa Clara, CA)
Assignee:	Cadence Design Systems, Inc. (San Jose, CA)
Appl. No.:	215896
Filed:	August 9, 2002

Current U.S. Class:			716/13 716/14 716/1 716/12
Current International Class:			G06F 17/50 (20060101)
Field of Search:			716/1,12,13,14,17

	U.S. Patent Documents
20010003843	June 2001	Scepanovic et al.
20010038612	November 2001	Vaughn et al.
20020043988	April 2002	Or-Bach et al.
20020100009	July 2002	Xing et al.
20020104061	August 2002	Xing et al.
20020107711	August 2002	Xing et al.
20020174413	November 2002	Tanaka
20020182844	December 2002	Igarashi et al.
20030005399	January 2003	Igarashi et al.
20030009737	January 2003	Xing
20030014725	January 2003	Sato et al.
20030025205	February 2003	Shively
20030121017	June 2003	Andreev et al.
20030188281	October 2003	Xing
20040044979	March 2004	Aji et al.
20040088670	May 2004	Stevens et al.
4615011	September 1986	Linsker
4673966	June 1987	Shimoyama
4777606	October 1988	Fournier
4782193	November 1988	Linsker
4855929	August 1989	Nakajima
5224057	June 1993	Igarashi et al.
5360948	November 1994	Thornberg
5375069	December 1994	Satoh et al.
5532934	July 1996	Rostoker
5578840	November 1996	Scepanovic et al.
5618744	April 1997	Suzuki et al.
5633479	May 1997	Hirano
5634093	May 1997	Ashida et al.
5635736	June 1997	Funaki et al.
5636125	June 1997	Rostoker et al.
5637920	June 1997	Loo
5650653	July 1997	Rostoker et al.
5657242	August 1997	Sekiyama et al.
5659484	August 1997	Bennett et al.
5663891	September 1997	Bamji et al.
5717600	February 1998	Ishizuka
5723908	March 1998	Fuchida et al.
5742086	April 1998	Rostoker et al.
5757089	May 1998	Ishizuka
5757656	May 1998	Hershberger et al.
5777360	July 1998	Rostoker et al.
5811863	September 1998	Rostoker et al.
5822214	October 1998	Rostoker et al.
5838583	November 1998	Varadarajan et al.
5856927	January 1999	Greidinger et al.
5859449	January 1999	Kobayashi et al.
5877091	March 1999	Kawakami
5880969	March 1999	Hama et al.
5889329	March 1999	Rostoker et al.
5889677	March 1999	Yasuda et al.
5898597	April 1999	Scepanovic et al.
5914887	June 1999	Scepanovic et al.
5973376	October 1999	Rostoker et al.
5980093	November 1999	Jones et al.
6006024	December 1999	Guruswamy et al.
6035108	March 2000	Kikuchi
6038383	March 2000	Young et al.
6058254	May 2000	Scepanovic et al.
6067409	May 2000	Scepanovic et al.
6068662	May 2000	Scepanovic et al.
6088519	July 2000	Koford
6110222	August 2000	Minami et al.
6111756	August 2000	Moresco
6123736	September 2000	Pavisic et al.
6128767	October 2000	Chapman
6154873	November 2000	Takahashi
6154874	November 2000	Scepanovic et al.
6155725	December 2000	Scepanovic et al.
6166441	December 2000	Geryk
6175950	January 2001	Scepanovic et al.
6209123	March 2001	Maziasz et al.
6216252	April 2001	Dangelo et al.
6219823	April 2001	Hama et al.
6219832	April 2001	Buzbee
6226560	May 2001	Hama et al.
6230306	May 2001	Raspopovic et al.
6247167	June 2001	Raspopovic et al.
6247853	June 2001	Papadopoulou et al.
6253363	June 2001	Gasanov et al.
6260179	July 2001	Ohsawa et al.
6262487	July 2001	Igarashi et al.
6286128	September 2001	Pileggi et al.
6289495	September 2001	Raspopovic et al.
6292929	September 2001	Scepanovic et al.
6295634	September 2001	Matsumoto
6301686	October 2001	Kikuchi et al.
6324674	November 2001	Andreev et al.
6324675	November 2001	Dutta et al.
6327693	December 2001	Cheng et al.
6327694	December 2001	Kanazawa
6330707	December 2001	Shinomiya et al.
6349403	February 2002	Dutta et al.
6378121	April 2002	Hiraga
6385758	May 2002	Kikuchi et al.
6401234	June 2002	Alpert et al.
6405358	June 2002	Nuber
6407434	June 2002	Rostoker et al.
6412097	June 2002	Kikuchi et al.
6412102	June 2002	Andreev et al.
6415427	July 2002	Nitta et al.
6434730	August 2002	Ito et al.
6436804	August 2002	Igarashi et al.
6442745	August 2002	Aranachalam et al.
6463575	October 2002	Takahashi
6473891	October 2002	Shively
6490713	December 2002	Matsumoto
6505331	January 2003	Bracha et al.
6516447	February 2003	Wadland et al.
6519751	February 2003	Sriram
6526555	February 2003	Teig et al.
6543043	April 2003	Wang et al.
6546540	April 2003	Igarashi et al.
6557145	April 2003	Boyle et al.
6567967	May 2003	Greidinger et al.
6586281	July 2003	Gabara et al.
6601227	July 2003	Trimberger
6609237	August 2003	Hamawaki et al.
6645842	November 2003	Igarashi et al.
6656644	December 2003	Hasegawa et al.
6665852	December 2003	Xing et al.
6687893	February 2004	Teig et al.

	Foreign Patent Documents
02-262354	Oct., 1990	JP
03-173471	Jul., 1991	JP
04-000677	Jan., 1992	JP
05-102305	Apr., 1993	JP
05-243379	Sep., 1993	JP
07-086407	Mar., 1995	JP
09-162279	Jun., 1997	JP
11-296560	Oct., 1999	JP
2000-082743	Mar., 2000	JP
64-15947	Jan., 1989	JP

	Other References
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. . 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. . Dion J. et al., Contour: A Tile-based Gridless Router, Mar. 1995, Digital Western Research Laboratory, research Report 95-3, pp. 1-22. . Schulz U., Hierarchical Physical Design System, CompEuro '89, VLSI and Computer Peripherals. VSLI and Microeletronic Applications in Intelligent Peripherals and their Interconnection Networks. Proceedings, May 8-12, 1989, pp. 5/20-5/24. . 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. . U.S. Appl. No. 10/066,060, filed Jan. 31, 2002, Teig. . U.S. Appl. No. 10/066,160, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/066,095, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/066,047, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/061,641, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/066,094, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/076,121, filed Feb. 12, 2002, Teig. . U.S. Appl. No. 10/062,995, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/066,102, filed Jan. 31, 2002, Teig. . U.S. Appl. No. 10/066,187, filed Jan. 31, 2002, Teig et al. . U.S. Appl. No. 10/228,736, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/229,311, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/229,108, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/215,563, filed Aug. 9, 2002, Teig. . U.S. Appl. No. 10/219,675, filed Aug. 14, 2002, Teig. . U.S. Appl. No. 10/219,608, filed Aug. 14, 2002, Teig. . U.S. Appl. No. 10/233,202, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/229,196, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/288,870, filed Nov. 6, 2002, Teig. . U.S. Appl. No. 10/219,923, filed Aug. 14, 2002, Teig. . U.S. Appl. No. 10/286,254, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/219,706, filed Aug. 14, 2002, Teig. . U.S. Appl. No. 10/231,423, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/230,503, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/222,088, filed Aug. 14, 2002, Teig. . U.S. Appl. No. 10/228,679, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/229,202, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/229,170, filed Aug. 26, 2002, Teig. . U.S. Appl. No. 10/286,630, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/230,504, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/215,923, filed Aug. 9, 2002, Teig. . U.S. Appl. No. 10/226,483, filed Aug. 23, 2002, Teig. . U.S. Appl. No. 10/226,774, filed Aug. 23, 2002, Teig. . U.S. Appl. No. 10/232,795, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/231,369, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/233,312, filed Aug. 28, 2002, Teig. . U.S. Appl. No. 10/227,016, filed Aug. 23, 2002, Teig. . U.S. Appl. No. 10/226,482, filed Aug. 23, 2002, Teig. . U.S. Appl. No. 10/285,844, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/286,253, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/288,033, filed Nov. 5, 2002, Teig. . U.S. Appl. No. 10/335,179, filed Dec. 31, 2002, Teig. . U.S. Appl. No. 10/285,758, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/286,598, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/286,584, filed Oct. 31, 2002, Teig. . U.S. Appl. No. 10/335,074, filed Dec. 31, 2002, Teig et al. . U.S. Appl. No. 10/334,665, filed Dec. 31, 2002, Teig et al. . U.S. Appl. No. 10/335,243, filed Dec. 31, 2002 Teig et al. . U.S. Appl. No. 10/335,062, filed Dec. 31, 2002 Teig. . Chen, H.F. et al., A Faster Algorithm for Rubber-Band Equivalent Transformation for Planar VLSI Layouts, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 2, Feb. 1996, pp. 217-227. . Chip Model with Wiring Cost Map, Aug. 1983, IBM Technical Disclosure Bulletin, vol. 26, issu. 3A, pp. 929-933. . Dayan, T. et al., Layer Assignment for Rubber Band Routing, UCSC-CRI-93-04, Jan. 20, 1993. . Dayan, T., Rubber-Band Based Topological Router, A Dissertation, UC Santa Cruz, Jun. 1997. . Dood, P. et al. A Two-Dimensional Topological Compactor with Octagonal Geometry, 28.sup.th ACM/IEEE Design Automation Conference, pp. 727-731, Jul. 1991. . Fujimura, K. et al, Homotopic Shape Deformation. . Hama, T. et al., Curvilinear Deatiled Routing Algorithm and its Extension to Wire-Spreading and Wire-Fattening. . 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. . Kobayashi, K. et al., A New Interactive Analog Layout Methodology based on Rubber-Band Routing, UCSC-CRL-96-12, Jun. 13, 1996. . Lim, A. et al, A Fast Algorithm To Test Planar Topological Routability, Technical Report 94-012, pp. 1-16. . Lu, Y., Dynamic Constrained Delaunay Triangulation and Application to Multichip Module Layout, A Thesis for Master of Science, UC Santa Cruz, Dec. 1991. . Maley, F.M., Testing Homotopic Routability Under Polygonal Wiring Rules, Algorithmica 1996, 15: 1-16. . 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. . NN71091316, Use of Relatively Diagonal And Rectangular Wiring Planes n Multilayer Packages, Sep. 1971, IBM Technical Disclosure Bulletin, vol. No. 14, Issue No. 4, pp. 1316-1317. . Staepelaere, D. et al., Geometric Transformations for a Rubber-Band Sketch, A Thesis for a Master of Science in Computer Engineering, UCSC, Sep. 1992. . Staepelaere, D. et al., Surf: A Rubber-Band Routing System for Multichip Modules, pp. 18-26, 1993. . 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. . Wei-Ming Dai, W. et al., Routability of a Rubber-Band Sketch. 28.sup.th ACM-IEEE Design Automation Conference, 1991, pp. 45-65. . Xing, Z. et al., A Minimum Cost Path Search Algorithm Through Tile Obstacles, slide presentation. . Xing, Z. et al., Shortest Path Using Tiles and Piecewise Linear Cost Propagation, IEEE, 2002, pp. 145-158. . Xu, A More Efficient Distance Vector Routing Algorithm, UCSC-CRL-96-18, Mar. 1997. . 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. . Yu, M.-F. et al, Interchangeable Pin Routing with Application to Package Layout, UCSC-CRL-96-10, Apr. 25, 1996. . Yu, M.-F. et al., Pin Assignment and Routing on a Single-Layer Grid Array, UCSC-CRL-95-15, Feb. 24, 1995. . Yu, M.-F. et al., Planar Interchangeable 2-Terminal Routing, UCSC-CRL-95-49, Oct. 19, 1995. . Yu, M.-F. et al., Single-Layer Fanout Routing and Routability Analysis for Ball Grid Arrays, UCSC-CRL-95-18, Apr. 25, 1995. . 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. . Alexander, M. et al., Performance-Oriented Placement and Routing for field-programmable gate arrays, Proceedings of the European Design Automation Conference, pp. 80-85, 1995. . Alexander, M. et al., Placement and Routing for Performance-Oriented FPGA Layout, LVSI Dsign, vol. 7, No. 1, 1998. . Andou, H. et al., Automatic Routing Algorithm for VLSI, 22.sup.nd Design Automation Conference, 1985, pp. 785-788. . Bagga, J. et al., Internal, External, and Mixed Visibility Edges of Polygons. . 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. . Brady, L. et al., Channel Routing on a 60.degree. Grid, extended abstract, pp. 926-931. . Carothers, K., A. Method of Measuring Nets Routability for MCM's General Area Routing Problems, 1999, pp. 186-192. . Chen, D-S. et al., A Wire-Length Minimization Algorithm for Single-Layer Layouts. . 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 Volume: 13 Issues, pp. 603-609. . Chen, H., Routing L-Shaped Channels in Nonslicing-Structure Placement. 24.sup.th ACM-IEEE Design Automation Conference, pp. 152-165, 1987. . Chen, H. et al., Physical Planning of On-Chip Interconnect Architectures, 2002, IEEE, International Conference, pp. 30-35. . Chen, S.-S. et al., A New Approach to the Ball Grid Array Package Routing, IEICE Trans. Fundamentals, vol. E82-A, No. 11, Nov., 1999, pp. 2599-2608. . Cheng, K. et al., Manhattan or Non Manhattan? A Study of Alternative VLSI Routing Architectures, pp. 47-52, 2000. . Cheng, K., Steiner Problem in Octilinear Routing Model, A Thesis submitted for the Degree of Master of Science, National University Singapore, 1995, pp. 1-122. . 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. . 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. . Cong, J. et al., Multilevel Approach to Full Chip Gridless Routing, Nov. 2001, IEEE, pp. 396-403. . Cong, J. et al., Performance Driven Multi-Layer General Routing for PCB/MCM Designs, UCLA Computer Science Department, 1998, pp. 356-361. . Das, S. et al., Channel Routing in Manhattan-Diagonal Model, 9.sup.th International Conference on VLSI Design, Jan. 1996. pp. 43-48. . Das, S. et al., Routing of L-Shaped Channels, Switchboxes and Staircases in Manhattan-Diagonal Model, pp. 65-70, Jan. 1998. . Enbody, R. et al., Near-Optimal n-Layer Channel Routing, 23.sup.rd Design Automation Conference, 1986, pp. 708-714. . Finch, A.C. et al., A Method for Gridless Routing of Printed Circuit Boards, 22.sup.nd Design Automation Conference, 1985 ACM, pp. 509-515. . 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. . Gao, T. et al., Minimum Crosstalk Channel Routing, pp. 692-696, 1993 IEEE. . Gao, T. et al., Minimum Crosstalk Switchbox Routing, pp. 610-615, 1994 ACM. . 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. . Guibas, L. et al., Optimal Shortest Path Queries in a Simple Polygon, 1987 ACM, pp. 50-63. . Hachtel, G.D. et al., Linear Complexity Algorithms for Hierarchical Routing, 1/89, IEEE pp 64-80. . Hershberger, J., Efficient Breakout Routing in Printed Circuit Boards, Computational Geometry, 1997, ACM, pp 460-462. . Hershberger, J., Finding the Visibility Graph of a Simple Polygon in Time Proportional to its Size, Preliminary Version, 1987 ACM, pp. 11-20. . Hightower, D., A Solution to Line-Routing Problems on the Continuous Plane, Bell Laboratories, Inc., pp. 11-34. . 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. . 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. . Ladage, L. et al., Resistance Extraction Using a Routing Algorithm, 30.sup.th ACM/IEEE Design Automation Conference, 1993, pp. 38-42. . Leach, G., Improving Worst-case Optimal Delaunay Triangulation Algorithms, Department of Computer Science, Jun. 15, 1992, pp. 1-7. . Leiserson, C. et al., Algorithms for Routing and Testing Routability of Plannar VLSI Layouts, pp. 69-78, May 1985. . Lillis, J. et al., New Performance Driven Routing Techniques With Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing, 33.sup.rd Design Automation Conference, 1996. . Lipski, W. et al., A Unified Approach to Layout Wirability, Mathematical Systems Theory, 1987, pp. 189-203. . Lodi, E. et al., A 2d Channel Router for the Diagonal Model, pp. 111-125, Apr. 1991. . Lodi, E. et al., A Preliminary Study of a Diagonal Channel-Routing Model, Algorithmica, 1989, pp. 585-597. . Lodi, E. et al., Lecture Notes in Computer Science, A 4d Channel router for a two layer diagonal model, pp. 464-476, Jil. 1988. . Lodi, E. et al., Routing in Time Square Mode, pp. 41-48, Jun. 1990. . Lodi, E. et al., Routing Multiterminal Nets in a Diagonal Model, pp. 899-902, 1988. . Murooka, T. et al., Simplified Routing Procedure for a CAD-Verified FPGA, IEICE Trans. Fundamentals, vol. E82-A, No. 11 Nov. 1999, pp. 2240-2447. . Naclerio, N. et al., Via Minimization for Gridless Layouts, 24.sup.th ACM/IEEE Design Automation Conference, 1987, pp. 159-165. . Nam, G. et al, Satisfiability-Based Layout Revisited: Detailed Routing of Complex FPGAs Via Search-Based Boolean SAT, 1999, pp. 167-175. . 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. . Ng, C., A "Gridless" Variable-Width Channel Router for Macro Cell Design, 24.sup.th ACM/IEEE Design Automation Conference, 1987, pp. 633-636. . Olaverri, A.G. et al., On the Minimum Size of Visibility Graphs. . Overtone, G., EDA Underwriter 2 Finding Space in a Multi-Layer Board, Electronic Engineering, Morgan-Grampian LTD, Mar. 1995, vol. 67, No. 819, pp 29-30. . Pocchiola, M., Computing the Visibility Graph via Pseudo-Triangulations, 11.sup.th Computational Geometry, Vancouver, Canada, 1995 ACM, pp. 248-257. . 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. . Royle, J. et al., Geometric Compaction in One Dimension for Channel Routing, 24.sup.th ACM/IEEE Design Automation Conference, 1987, pp 140-145. . Schiele, W. et al., A Gridless Router for Industrial Design Rule, 27.sup.th ACM-IEEE Design Automation Conference, pp. 626-631, 1990. . 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. . Soukup, J. et al., Maze Router Without a Grid Map, IEEE, 1992, pp. 382-385. . 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. . Teig, S. The X Architecture: Not your Father's Diagonal Wiring, International Workshop on System Level Interconnect Prediction, pp. 33-37, Apr. 2002. . Thakur, S. et al., Algorithms for a Switch Module Routing Problem, 1994, pp. 265-270. . Theune, D. et al., HERO: Hierarchical EMC-constrained routing, Nov. 1992, IEEE pp 468-472. . Tollis, I. Techniques for Wiring in Non-Square Grids, pp. 66-69, May 1989. . Urrutia, J., On the Number of Internal and External Visibility Edges of Polygons, Department of CS, University of Ottawa, ON, Canada, Feb. 11, 1997. . Wang, D., Novel Routing Schemes for IC Layout, Part I: Two-Layer Channel Routing, 28.sup.th ACM/IEEE Automation Conference, 1991, pp. 49-53. . 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. . Zhou, H. et al., An Optimal Algorithm for River Routing with Crosstalk Constraints, 1996. . 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..~


Primary Examiner:	Do; Thuan
Attorney, Agent or Firm:	Stattler, Johansen, & Adeli, LLP


	*Parent Case Text*

CLAIM OF BENEFIT TO PROVISIONAL APPLICATION This patent application claims the benefit of U.S. Provisional Patent Application 60/351,459, filed Jan. 22, 2002, U.S. Provisional Patent Application 60/396,571, filed Jul. 15, 2002, U.S. Provisional Patent Application 60/388,518, filed Jun. 12, 2002, and U.S. Provisional Patent Application 60/385,975, filed Jun. 4, 2002. This application is also a continuation-in-part of U.S. patent application Ser. No. 10/076,121, filed Feb. 12, 2002, and a continuation-in-part of U.S. patent application Ser. No. 10/066,094, filed Jan. 31, 2002.


	*Claims*

We claim: 1. A method of identifying topological routes in a multi-layer region of a design layout, the method comprising: a) selecting a first net having routable elements; b) generating a tessellated graph, wherein the tessellated graph is a decomposition of the design layout into a plurality of polygons; and c) embedding in the tessellated graph a first multi-layer topological route that connects the first net's routable elements before selecting another net for routing, wherein the first topological route traverses a plurality of layers, wherein a topological route is a route that represents a set of geometric routes that are morphable into one another through a continuous sequence of perturbations, each geometric route being one geometric realization of the topological route. 2. The multi-layer topological routing method of claim 1 further comprising: a) selecting a second net, and b) embedding in the tessellated graph a second topological route that connects the Second nets routable elements before selecting another net for routing. 3. The method of claim 2, wherein the second topological route connects (the second net's routable elements on more than one layer. 4. The method of claim 2, wherein the tessellated graph includes a plurality of topological items for defining topological routes, said topological items including a first set of items that represent the first net's rotatable elements; and wherein embedding the first topological route comprises: specifying the first route as an associated set of items in the tessellated graph, wherein the associated set of items includes the first set of items. 5. The method of claim 4, wherein the associated set of items includes at least one item that represents a via. 6. The method of claim 5, wherein the tessellated graph includes a plurality of nodes and a plurality of edges, wherein each edge is between a pair of nodes. 7. The method of claim 6, wherein the layout has a coordinate system with at least two coordinate axes, and the tessellated graph comprises a triangulated graph that includes a plurality of edges wherein at least some of the edges are not aligned with either coordinate axis. 8. The method of claim 6, wherein the via allows the first route to traverse from one layer of the graph to another layer of the graph, the method further comprising: identifying at least two regions within at least two polygons on two different layers of the tessellated graph; identifying the intersection of the two regions; determining that the intersection or the two regions is sufficiently large for containing a via; and specifying the via in the identified intersection. 9. The method of claim 8, wherein the regions are polygonal regions. 10. The method of claim 8, wherein the regions are convex polygonal regions. 11. The method of claim 8, wherein the method identifies and intersects the two regions and specifics the via within the identified intersection before selecting the first net. 12. The method of claim 8, wherein the method identifies and intersects the two regions and specifies the via within the identified intersection while embedding the first route for the first net. 13. The method of claim 1, wherein the first topological route includes a set of topological paths, wherein embedding the first topological route comprises using a depth first, iterative deepening path search to identify each topological path. 14. The method of claim 1, wherein the first topological route includes a set of topological paths, wherein the tessellated graph includes a plurality of topological items for defining topological routes, said topological items including a first set of items that represent the first net's routable elements; and wherein embedding the first topological route comprises: identifying each topological path by using a best first search that expresses the cost of a path that reaches a topological item in the graph in terms of a function that is defined over the topological item. 15. The method of claim 1, wherein the design layout is an integrated circuit design layout. 16. A computer readable medium comprising a computer program having executable code, the computer program for identifying topological routes in a multi-layer region of a design layout, the computer program comprising sets of instructions for: a) selecting a first net having routable elements; b) generating a tessellated graph, wherein the tessellated graph is a decomposition of the design layout into a plurality of polygons; and c) embedding in the tessellated graph a first multi-layer topological route that connects the first net's routable elements before selecting another net for routing, wherein the first topological route traverses a plurality of layers, wherein a topological route is a route that represents a set of geometric routes that are morphable into one another through a continuous sequence of perturbations, each geometric route being one geometric realization the topological route. 17. The computer-readable medium of claim 16, wherein the computer program further comprises sets of instructions for: a) selecting a second net; and b) embedding in the tessellated graph a second topological route that connects the second net's routable elements before selecting another net for routing. 18. The computer-readable medium of claim 17, wherein the the tessellated graph includes a plurality of topological items for defining topological routes, said topological items including a first set of items that represent the first net's routable elements; and wherein the set of instructions for embedding the first topological route comprises a set of instructions for: specifying the first route as an associated set of items in the tessellated graph, wherein the associated set of items includes the first set of items. 19. The computer-readable medium of claim 18, wherein the associated set of items includes at least one item that represents a via. 20. The computer-readable medium of claim 19, wherein the tessellated graph includes a plurality of nodes and a plurality of edges, wherein each edge is between a pair of nodes. 21. The computer-readable medium of claim 20, wherein the layout has a coordinate system with at least two coordinate axes, the tessellated graph is a triangulated graph that includes a plurality of edges wherein at least some of the edges are not aligned with either coordinate axis. 22. The computer-readable medium of claim 20, wherein the via allows the first route to traverse from one layer of the graph to another layer of the graph, the computer program further comprising sets of instructions for: identifying at least two regions within at least two polygons on two different layers of the tessellated graph; identifying the intersection of the two regions; determining that the intersection of the two regions is sufficiently large for containing a via; and specifying the via in the identified intersection.


	*Description*

FIELD OF THE INVENTION The invention is directed towards method and apparatus for producing multi-layer topological routes. BACKGROUND OF THE INVENTION An integrated circuit ("IC") is a device that includes many electronic components (e.g., transistors, resistors, diodes, etc.). These components are often interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit components of IC's are jointly referred to below as "components." An IC also includes multiple layers of wiring ("wiring layers") that interconnect its electronic and circuit components. For instance, many IC's are currently fabricated with metal or polysilicon wiring layers (collectively referred to below as "metal layers," "interconnect layers" or "wiring layers") that interconnect its electronic and circuit components. One common fabrication model uses five metal layers. In theory, the wiring on the metal layers can be all-angle wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is commonly referred to as Euclidean wiring. In practice, however, each metal layer typically has a preferred wiring direction, and the preferred direction alternates between successive metal layers. IC designs often penalize non-preferred-direction wiring on a layer. Many IC's use the Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring. In this wiring model, the majority of the wires can only make 90.degree. turns. However, occasional diagonal jogs are sometimes allowed on the preferred horizontal and vertical layers. Design engineers design IC's by transforming circuit description of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation ("EDA") applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectangular lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. Also, in this document, the phrase "circuit module" refers to the geometric representation of an electronic or circuit IC component by an EDA application. EDA applications typically illustrate circuit modules with pins on their sides. These pins connect to the interconnect lines. A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a netlist. In other words, a netlist specifies a group of nets, which, in turn, specify the required interconnections between a set of pins. The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; and (5) verification, which checks the layout to ensure that it meets design and functional requirements. Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a "loose" route for the interconnect lines that are to connect the pins of the net. After global routes have been created, the detailed routing creates specific individual routing paths for each net. While some commercial routers today might allow an occasional diagonal jog, these routers do not typically explore diagonal routing paths consistently when they are specifying the routing geometries of the interconnect lines. This, in turn, increases the total wirelength (i.e., total length of interconnect lines) needed to connect the nets in the layout. In addition, routers today are mostly gridded. The manufacturing processes for designing IC's specify a manufacturing grid that specifies manufacturable resolution. The boundary of all circuit elements is defined by the straight-line connections between adjacent manufacturing points. Gridded routers typically define arbitrary grids of intersecting lines to specify the available locations for routing interconnects. These arbitrary grids are often much coarser than the manufacturing grids (e.g., they are typically line-to-via spacing). Consequently, they arbitrarily limit the locations of interconnect lines and impose arbitrary spacing between the items in the layout. These arbitrary limits increase the size and efficiency of a design. The routing grids also discourage using arbitrary widths or spacing for interconnect lines. Furthermore, existing routers primarily utilize preferred-direction wiring to route their designs. Many IC layouts are designed by penalizing the use of interconnect lines in each particular layer when the interconnect lines are not in the preferred wiring direction of the particular layer. Such preferred-direction wiring leads to IC layouts and IC's that have most of their interconnect lines and wiring on each of their metal layers traverse in the same direction. Such IC layouts and IC's do now efficiently use the available spacing on the interconnect layers, and this adversely affects the size and efficiency of the layouts and the IC's. SUMMARY OF THE INVENTION Some embodiments of the invention provide a method for identifying topological routes in a multi-layer region of a design layout. The method selects a first net that has several routable elements. For the selected net, it then specifies a first multi-layer topological route that connects the first net's routable elements before selecting another net for routing. The first topological route traverses a plurality of layers. In addition, a topological route is a route that represents a set of diffeomorphic geometric routes. 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. FIG. 1 illustrates a wiring model of some embodiments of the invention. FIG. 2 illustrates a process that is used by some embodiments to produce IC's that utilize NPD-wiring models. FIG. 3 presents a conceptual illustration of a routing process used by some embodiments of the invention. FIGS. 4 and 5 illustrate two layers of Gcells that have been combined to produce a sub-region. FIG. 6 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. 7 provides examples of topological routes that are formed by via nodes, Steiners, walls, joints, and nodes. FIG. 8 illustrates a process that provides the overall flow of the Q* topological engine in some embodiments. FIG. 9 illustrates a triangulation process that is used in some embodiment of the invention by the Q* topological routing engine. FIG. 10 illustrates the layout of FIG. 4 after nodes have been defined at each sub-region corner and at each port or obstacle geometry point. FIG. 11 illustrates a triangulation technique. FIGS. 12 and 13 illustrate why maximizing the minimal angle of decomposed triangles improves the likelihood that generated topological routes can be geometrized. FIGS. 14 and 15 illustrate one manner for performing an edge-flipping operation. FIG. 16 provides a pictorial example of a constraining operation. FIG. 17 illustrates a hole-identification process that can be used to try to specify holes within triangles. FIG. 18 illustrates an example of how the layout of FIG. 4 might look after triangulation. FIGS. 19 and 20 illustrate how some embodiments calculate edge capacities. FIG. 21 illustrates the overall flow of a solving engine of some embodiments of the invention. FIG. 22 illustrates a route generation process of some embodiments. FIGS. 23-30 provide an example of an A* path search that uses such an F cost. FIG. 31 illustrates an example of a line PLF that has four line segments. FIG. 32 illustrates an example of a surface PLF. FIG. 33 presents an example of filtering a first filtered PLF by a second filter PLF, where both PLF's are defined across a line. FIG. 34 illustrates the minimum PLF for the two PLF's of FIG. 33. FIG. 35 illustrates a Q* path search process of some embodiments of the invention. FIGS. 36-39 provide examples for describing the process of FIG. 35. FIG. 40 illustrates a process that propagates a PLF that is defined over a point to a line or a surface. FIGS. 41 and 42 illustrate examples of propagating a PLF from a point P to a line L and to a surface S. FIG. 43 illustrates a process for propagating a PLF from a line to another line or from a surface to a line, and FIGS. 44 and 45 provides examples for describing this process. FIGS. 46-51 illustrate how some embodiments identify the propagation vectors that emanate from the knot locations of a line PLF or surface PLF. FIG. 52 illustrates a process for propagating a G PLF from a line to a surface. FIG. 53 illustrates an example for propagating a G PLF from a line to a surface. FIG. 54 illustrates a process for propagating a PLF from a line to a point or from a surface to a point. FIGS. 55 and 56 describe the process of FIG. 54. FIG. 57 presents an example that illustrates an expansion from a start surface to a destination surface. FIGS. 58A and 58B illustrate how to compute the flow across an edge after a potential expansion. FIGS. 59 and 61 illustrate processes that generate PLF's that express costs of expansions to an edge or a hole, while FIGS. 60 and 62 present examples that describe these processes. FIGS. 63-65 illustrate how to add two surface PLF's. FIG. 66 illustrates a process that performs filtering and minimum operations for an expansion to a line. FIGS. 67 and 68 illustrate how to filter two surface PLF's. FIGS. 69 and 70 illustrate how some embodiments compute an H function. FIG. 71 illustrates a process that specifies a topological path. FIGS. 72-76 illustrate data structure that defines a face, an edge, a node, an edge item, and a face item in some embodiments of the invention. FIGS. 77 and 78 illustrate an example of topological routes. FIG. 79 illustrates a process that provides the overall flow of an IDA* topological engine in some embodiments of the invention. FIG. 80 pictorially illustrates an example of a solving engine's IDA-searching operation for a set of three nets. FIG. 81 illustrates a more detailed process used by the solving engine in some embodiments of the invention. FIG. 82 illustrates a process that the solving engine uses to generate topological routes. FIGS. 83A and 83B illustrate a process for inserting Steiner-tree face items in face. FIG. 84 illustrates a process for generating paths between one or more sources and one or more targets for a selected pin-pair. FIGS. 85-89 illustrate possible expansions from edge items, nodes, and face items. FIG. 90 illustrates three types of legality checking. FIGS. 91 and 92 illustrate two via-checking processes. FIGS. 93-105 present several examples that illustrate the process of FIG. 91. FIG. 106 illustrates a process for computing the cheapest-route cost for a net. FIG. 107 illustrates a computer system 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. 1. Non-Preferred Direction Architecture Some embodiments of the invention utilize non-preferred-direction ("NPD") wiring models for designing IC layouts. An NPD wiring model has at least one NPD interconnect layer that has more than one preferred routing direction. Specifically, in such a wiring model, each NPD interconnect layer has at least two wiring directions that are equally preferable with respect to one another, and that are as preferable as or more preferable than the other wiring directions on that layer. An NPD router that uses an NPD wiring model generates IC layouts with one or more NPD interconnect layers, with each having two or more preferred wiring directions. In some embodiments, such a router does not impose arbitrary penalty costs for routing (i.e., does not penalize wiring) in the two or more preferred directions of an NPD interconnect layer of its layout. Rather, such a router costs wiring (i.e., interconnect lines) in the preferred directions proportionately to the metric costs that they introduce in the design. The metric cost is a non-arbitrary cost that is based on putative chip performance, manufacturing considerations, or other real-world design consideration, and not an artifical characteristic of the router. The metric costs can be based on a number of properties of the wiring, such as resistance, delay, manufacturing yield, etc. A router can account for these metric costs by using costing functions that are based on the interconnect-line attributes, such as length, area, etc. For instance, horizontal and +45.degree. wiring directions might be the preferred wiring directions of an interconnect layer. On such a layer, an NPD router would not impose an arbitrary penalty cost on routing in either the horizontal +45.degree. directions, in order to deter routes in one of these directions. Instead, some embodiments might cost horizontal and +45.degree. lines based solely on the length of the lines in these directions, while other embodiments might cost horizontal and +45.degree. lines based solely on the area of the lines in these directions. Costing the lines based on their areas more accurately estimates the metric resistance and delay costs of the lines when the widths of the lines have to be different in different preferred directions. For instance, manufacturing design rules might require the preferred direction +45.degree. wires to be wider than preferred direction horizontal wires on a layer. Such 45.degree. lines would be more expensive than horizontal lines if area were used to cost the routes. This additional expense, however, is not an artificial penalty cost, but rather is an actual cost that relates directly to the metric cost that the +45.degree. lines introduce into the design. It should be noted that such 45.degree. lines would be less expensive than horizontal lines if delay were used as the primary metric for costing the routes. FIG. 1 illustrates a wiring model 100 of some embodiments of the invention. This wiring model has five interconnect layers 105-125. In this five-layer model, none of the layers has a single preferred wiring direction. Instead, each layer allows 4 different preferred directions of wiring. Specifically, as illustrated by the top view 130 of the fifth interconnect layer 125, each layer of the wiring model 100 can have horizontal, vertical, and .+-.45.degree. diagonal interconnect lines. Each layer is an octilinear layer, as it allows interconnect lines to traverse in eight separate vector directions from any given point. In some embodiments, an interconnect line is "diagonal" if it forms an angle other than zero or ninety degrees with respect to the layout's Cartcsian coordinate axes, which typically align with the layout's boundary and/or the boundary of the layout's expected IC. On the other hand, an interconnect line is "horizontal" or "vertical" if it forms an angle of 0.degree. or 90.degree. with respect to one of the coordinate axes of the layout. In the wiring model of FIG. 1, (1) the horizontal interconnect lines are parallel (i.e., are at 0.degree.) to the x-axis, which is defined to be parallel to the base of the layout, (2) the vertical interconnect lines are parallel to the y-axis, which is defined to be parallel to the height and perpendicular (i.e., is at 90.degree.) to the base of the layout, (3) the +45.degree. diagonal interconnect lines are at +45.degree. with respect to the x-axis, and (4) the -45.degree. diagonal interconnect lines are at -45.degree. with respect to the x-axis. Other embodiments of the invention use different NPD wiring models. For instance, some embodiments of the invention's NPD wiring model include only diagonal interconnect lines, other embodiments use only horizontal and vertical interconnect lines, and yet other embodiments use diagonal interconnect lines with either horizontal or vertical interconnect lines but not both. Also, some embodiments use non-45.degree. diagonal wiring. For example, some embodiments use horizontal, vertical and .+-.120.degree. diagonal interconnect lines. In addition, some embodiments have more than five layers, while other embodiments have fewer. Some embodiments also assign a single preferred direction for some of the layers, while allowing other layers not to have a single preferred wiring direction. For instance, some embodiments have preferred-direction Manhattan wiring for the first three layers (e.g., horizontal preferred-direction wiring for the first layer, vertical preferred-direction wiring for the second layer, and horizontal preferred-direction wiring for the third layer), and NPD wiring for the fourth and fifth layers. By generating IC layouts with one or more NPD interconnect layers, some embodiments fabricate IC's that have NPD wiring for one or more of their metal layers (ie., fabricate IC's with one or more NPD metal layers, with each having two or more preferred wiring directions). For instance, the wiring model 100 of FIG. 1 can be used to generate an IC layout with five NPD-interconnect layers. Such a layout can then be used to generate a five metal layer IC, where each of the metal layers has four equally preferable wiring directions. FIG. 2 illustrates a process 200 that is used by some embodiments to produce IC's that utilize NPD-wiring models. This process initially describes (at 205) the specification of an IC. The IC specification is a high-level representation that considers various factors, such as performance, functionality, physical dimension, etc. The process then specifies (at 210) the circuit design of the IC. This operation typically entails one or more sub-operations, such as specifying the IC's architectural design, functional design, logic design, etc. Numerous EDA tools exist for assisting in the creation of the system's circuit design. After specifying the circuit design, the process specifics (at 215) a physical design layout for the IC. According to the invention, the process specifies the physical design layout based on an NPD-wiring model. The generation of physical design layouts that use the NPD-wiring model will be described below. At 215, the physical-design operation might result in the partitioning of the IC into multiple IC's (i.e., might result in the generation of one or more layouts that represent several IC's). Also, at 215, the process verifies the generated physical design layouts. Verification typically entails various operations, such as design-rule check, extraction, etc. These operations are to ensure that the generated layouts specify designs that meet the fabrication rules and perform the desired functionalities. Once physical design and verification are completed, the process converts (at 220) the physical design layout into one or more sets of masks for one or more IC's. Each set of masks typically includes one mask for each wiring layer. Currently, each mask is typically a photo-lithographic mask that identifies spaces on a semiconductor wafer where certain materials need to be deposited, diffused and/or removed. Accordingly, at 225, the process uses the masks to fabricate one or more IC's. Specifically, the fabrication operation uses the masks to create devices on IC's and to define wiring that connect the devices. When the physical design layout uses an NPD-wiring model, the masks define NPD wiring on one or more layers of the IC's. After fabrication, the process 200 tests (at 230) the fabricated IC's. The process then (at 235) packages any IC that passes its tests, and then ends. Some embodiments fabricate IC's that have at least one wiring layer that does not have a wiring direction with more that 50% of the wiring on that layer. Other embodiments fabricate IC's that have at least one wiring layer that does not have a wiring direction with more than 70% of the wiring on that layer. For instance; one such IC might predominantly include horizontal and vertical direction wiring on the wiring layer that does not have any wiring direction with more than 70% of the wiring. II. Gridless Architecture A gridless routing process is described below. This routing process is gridless as it does not require the interconnect lines to be positioned with respect to any grid that is coarser than the manufacturing grid, if any. In other words, the only grid that the interconnect lines might have to be aligned with is the manufacturing grid. The generated gridless layouts can be used, in turn, to fabricate IC's that have their metal lines aligned with the finer manufacturing grids instead of coarser non-manufacturing grids. The gridless routing process described below generates gridless NPD octilinear layouts. However, one of ordinary skill will realize that this routing process can be used to generate other gridless layouts. In addition, even though a gridless NPD routing process is described below, some embodiments can use the invention's NPD routing in a gridded router that generates gridded NPD layouts. III. NPD and Gridless Routing A. Conceptual Flow. Some embodiments generate gridless NPD layouts by using a detailed routing technique that does not specify a preferred wiring direction for any of its interconnect layers. The detail-routing embodiments described below use the NPD wiring model 100 of FIG. 1. However, one of ordinary skill will realize that other embodiments of the invention use different NPD wiring models. In the embodiments described below, the detailed routing is performed after a global routing stage, which (1) partitions the routing region into global routing cells ("Gcells") and (2) defines, for each net, global routing paths that connect the Gcells containing the net's pins. One hierarchical global routing approach recursively divides the routing region into smaller sub-regions, and defines routing paths at each hierarchical level until reaching the lowest recursive level's sub-regions, which are the Gcells. Another global routing approach flatly divides the routing region into numerous Gcells and then defines the routing paths between the Gcells. Under either approach, the global router can use either an NPD wiring model or a preferred-direction wiring model. FIG. 3 presents a conceptual illustration of a detail-routing process 300 used by some embodiments of the invention. This routing process defines detail routes for nets within a region of the IC layout. This region can be the entire IC layout, or a portion of this layout. As shown in this figure, this process initially selects (at 305) a sub-region of the IC layout region to detail route. The sub-region can be a portion of the IC layout, or the entire IC layout. Several manners for selecting such a region will be described below in Section III.B. Next, for each particular net in the selected sub-region, the process identifies (at 310) a topological route that connects the particular net's routable elements in the sub-region. In the embodiments described below, a net has two or more pins, a pin can have one or more ports, and each port can have one or more geometries. In these embodiments, a net's routable elements are the port geometries, and a net is typically routed along one port of each of its pins. One of ordinary skill will realize, however, that other embodiments may define the routable elements of the nets differently. A topological route is a route that is defined in terms of its relation to other layout items, such as pins, obstacles, boundaries, and/or other topological routes of other nets. As such, a topological route provides a general plan for how to route a net, without necessarily providing a specific geometric path to do so. One topological route represents a set of diffeomorphic geometric routes (i.e., a set of geometric routes that can be morphed into one another through a continuous sequence of perturbations without changing the route's path relative to any other pin, path or obstacle). A geometric route is one explicit realization of a topological route. A geometric route is defined in terms of exact coordinates that define the route as it travels through the interconnect layers. Several manners for identifying topological routes for each net within the selected sub-region will be described below. After 310, the process determines (at 315) whether the identified topological routes identified at 310 are geometrically routable (i.e., whether there exists a design-rule-correct geometric route for each identified topological route). If so, the process transitions to 320, which will be described below. Otherwise, if the process determines (at 315) that the identified topological routes for some of the nets are not routable, it initially directs the topological router to generate additional topological routes that are more likely to have design rule-correct geometric routes. If the topological router repeatedly fails to generate geometrically routable topological routes, the detail-routing process flags one or more nets as unroutable, re-defines topological routes for some or all the nets, and then transitions to 320. Performing the mutability checking is described in U.S. Patent Application "Method and Apparatus for Routing Nets in an Integrated Circuit Layout", with the Ser. No. 10/215,563 and filed on Aug. 9, 2002. This application is incorporated in the present application by reference. At 320, the process generates these geometric routes and stores these routes in a detail-routing storage structure (such as a database). Generating geometric routes from topological routes is described in the above-mentioned patent application. At 320, the process also converts the generated geometric detail routes into global routing paths, which it stores in a global routing storage structure (such as a database). This is done just in case the router has to detail route some Gcells again. At 325, the process then determines whether it has generated detail routes for all the sub-regions of the IC region. If not, the process returns to 305 to select another sub-region and to repeat 310-320 to compute geometric routes in the newly selected sub-region. Otherwise, the process ends. After 325, some embodiments might repeat process 300 for certain congested sub-regions in order to alleviate the congestion in these regions, improve wiring quality, or fix violations left by previous attempts. B. Region Selection. As mentioned above, the detail-routing process 300 selects (at 305) a sub-region of the IC layout region to detail route. In some embodiments of the invention, this selection involves selecting several contiguous Gcells, and generating a sub-region by combining the selected Gcells. Several manners for selecting contiguous Gcells are disclosed in United Stales Patent Application entitled "Method and Apparatus for Generating Multi-Layer Routes" and having Ser. No. 10/076,121. One of ordinary skill will realize that other embodiments might select and combine Gcells in order to identify a sub-region, but rather might simply specify a portion or the entire IC layout as the sub-region. In generating a sub-region by combining several contiguous Gcells, the process 300 adds any virtual pins ("vpins") of the Gcells in the periphery of the sub-region as geometries of the sub-region. Virtual pins are artificial pins that are set to account for the global route propagation into Gcells from other Gcells or higher-level slots. In the embodiments described below, the virtual pins are represented as single point geometries. For example, FIGS. 4 and 5 illustrate two layers of 16 Gcells that have been combined to produce a sub-region 400. For sake of simplicity, this example assumes that the generated sub-region only has pins, virtual pins, and obstacles on the two layers shown in FIGS. 4 and 5. As shown in FIG. 4, the sub-region 400 includes two obstacles 410 and 415. This sub-region also includes port geometries of three nets A, B, and C. Again, for sake of simplifying the example, the port geometries 420-445 and 505 of nets A, B, and C are all from the same ports of their respective nets in the example illustrated in FIG. 4. As shown in FIGS. 4 and 5, the obstacle and port geometries can have a variety of shapes (e.g., convex or non-convex polygonal shapes, etc.). Also, these geometries have horizontal, vertical, and diagonal sides. As shown in FIG. 4, three of the twelve Gcells on the periphery include virtual pins 450, 455, 460, and 510 for nets A and C. During the sub-region generation, these four virtual pins 450, 455, 460, and 510 are added to the sub-region data structure as port geometries of nets A and C. The detailed routing process 300 defines a sub-region based on various attributes. These attributes include a list of all obstacle and port geometries in the region, and a list (i.e., a netlist) that specifies the nets in the sub-region. In the embodiments described below, each net specifics one or more pins, each pin refers to one or more ports, and each port refers to one or more geometries. Other embodiments might specify a net differently. A sub-region is also defined by information about net properties on different layers. For different layers, this information can include minimum wire size, minimum spacing, minimum via size, minimum cost per unit length, etc. In some embodiments, this information also includes (1) different net widths on different layers, (2) different spacing between nets on different layers, and (3) different spacings between nets and unrelated geometries on different layers. C. Topological Route Generation. In some embodiments, a topological routing engine receives the sub-region defined at 205 (i.e., receives the problem instance). For each net in the received sub-region, the topological routing engine generates (at 310) a topological representation of a route that connects the net's routable elements. Different embodiments use different topological routing engines. Below, two topological routers are described that can be used as the topological routing engine. One topological routing engine is referred to as the Q topological routing engine, while the other is referred to as the IDA* topological routing engine. Both engines are multi-layer topological routers. Accordingly, for each net in the sub-region, each engine generates a topological route (i.e., a topological representation of a route) that connects the net's routable elements on one or more layers. In other words, each router selects a net and, for the selected net, defines a topological route that connects the selected net's routable elements on one or more interconnect layers, before selecting another net for routing. To facilitate its multi-layer approach, each topological router uses vias that are defined topologically. These vias are referred to below as topological vias. In addition, both topological routing engines can route sets of nets as an ensemble. Specifically, the Q* engine selects a set of nets in the sub-region. For the selected set, this engine might generate several different routing solution sets, where each solution includes a topological route for some or all of the nets in the set. From the identified set of solutions, this engine then selects the best solution set for the selected set of nets. Similarly, the IDA* routing engine selects a set of nets in the sub-region and deterministically traverses through the solution space to identify the best possible combination of topological routes for the selected set of nets. Both topological engines can consider the estimated routing cost of unrouted nets in the selected set while they are generating a solution set. These engines consider such estimated costs so that they can terminate examining a solution set when an estimated cost exceeds an acceptable threshold. The IDA* routing engine uses an DA* path search engine that identifies paths between sets of sources and targets in a depth-first, iterative-deepening manner. The Q* routing engine, on the other hand, uses a Q* path search process that finds the shortest topological route for each net. The Q* path search process also has a powerful shove operation that allows the topological routes of later-routed nets to shove the topological routes of earlier-routed nets. In the embodiments described below, this operation allows the earlier-routed nets to bend around the topological routes of later-routed nets. Accordingly, this operation reduces the routing constraints placed on later-routed nets by the routes of earlier-routed nets. In the embodiments described below, both topological routers are NPD routers that use NPD wiring models (such as the wiring model of FIG. 1). In some embodiments, both topological engines allow nets to have different widths on different layers. They also can impose different spacing constraints between pairs of nets. The spacing constraint for a pair of nets can also be different on different layers. Both topological engines can also base their topological routes on different wiring models, such as a wiring model that employs only Manhattan lines, one that uses Manhattan and .+-.45.degree. lines, one that uses Manhattan and .+-.120.degree. lines, etc. 1. Q* Topological Routing Engine a. Overview The Q* topological engine decomposes each layer of the sub-region that it receives into numerous polygons and embeds topological routes into the decomposed region. Different embodiments decompose the sub-region into different types of polygons, such as triangles, rectangles, etc. The embodiments described below use a triangulation decomposition operation that decomposes each layer of the sub-region into numerous triangular faces, each with three nodes and an edge between each pair of nodes. The decomposed sub-region is at times referred to below as the tessellated region. The initial triangulation also specifies one space within each face. FIG. 6 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. For each layer of the sub-region, the initial triangulation operation adds a topological graph to the sub-region definition. Each layer's topological graph includes several nodes, edges, and faces. In the embodiments described below, nodes are defined at the obstacle-geometry vertices, port-geometry vertices, the four corners of the sub-region on each layer, and some or all of the vpins. The embodiments described below define edges between certain pairs of nodes in order to triangulate the sub-region. An edge can be part of up to two triangular faces. For each edge, the Q* topological engine stores the edge's capacity and length. It further stores the wire flow (route flow) across each edge. Different embodiments define edges differently. In the embodiments described below, the Q* topological engine defines each edge as an ordered list of topological particles in the tessellated region. In these embodiments, the topological particles that can be on an edge (i.e., that can define an edge) are nodes, joints, and exits, which are described below. Nodes are vertices of the tessellated region, as described above. Two nodes start and end each edge's ordered list of topological particles. A node can be part of multiple edges. A joint is a topological particle that is defined at the intersection of an edge and a net's route. An exit is a topological particle that is specified on an edge between each two non-exit particles on the edge. As illustrated in FIG. 6, an exit is the only topological particle between an edge's nodes, after the initial triangulation before any route has been embedded in the region. Whenever a joint is defined on an edge, it divides a previously undivided exit of the edge into two exits. Joints and exits are further described below. Each triangular face has 3 edges, 3 nodes, and a set of "spaces" representing topological regions inside the face. After the initial triangulation, each face has one space within it, as shown in FIG. 6. When topological routes are embedded across a face, additional spaces are defined in the face. 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. After the initial triangulation, the Q* engine embeds topological routes in the decomposed topological region. The Q* engine 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. The wire segments are referred to as walls in the embodiments described below. In other words, a wall is a wire segment (i.e., an interconnect segment) that connects two vertices in a topological route. In the embodiments described below, the topological particles that can serve as vertices of a route are nodes, joints, "holes," "via nodes," and "Steiners." A hole is a topological particle that represents a potential via between two spaces on two different layers. In the embodiments described below, a hole is defined between each pair of spaces that are on adjacent layers and that have sufficiently large overlap to accommodate a via. In other embodiments, however, holes might be defined between space pairs that are on different but not adjacent layers. 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. 6 illustrates holes in several spaces. When a net's topological route is embedded, a hole is converted into two via nodes, one in each space connected by the hole. In the embodiments described below, the two via nodes have an association (e.g., have a reference to one another) but do not have a wall (i.e., a wire segment) between them. Other embodiments might specify walls between related via nodes. 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 preexisting path of a net and a newly embedded path of the net. FIG. 7 provides examples of topological routes that are formed by via nodes, Steiners, walls, joints, and nodes. Specifically, this figure illustrates two embedded topological paths 700 and 702 (where a path in this instance is portion of a route). Both of these paths traverse several triangular faces on layer 2. Path 700 also traverses two triangular faces on layer 3, as it is a multi-layer route. Path 700 is specified by the following ordered list of particles: node 704, wall 706, joint 708, wall 710, joint 712, wall 714, node 716, node 718, wall 720, joint 722, wall 724, and node 726. Path 702 is specified by the following ordered list of particles: node 728, wall 730, joint 732, wall 734, joint 736, wall 738, Steiner 740, wall 742, and node 744. FIG. 7 also illustrates a wall 746 of another portion of path 702's route. As shown in FIG. 7, the embedded routes divide the faces that they completely cross into several spaces. For instance, these paths divide the face formed by vertices 704, 748, and 750 into three spaces. Also, a joint specifies the intersection of each route with each edge. Each joint connects to two exits, as each joint divides a previously undivided exit into two exits. As mentioned above, path 702 includes a Steiner 740. This Steiner connects walls 738, 742, and 746. In addition, multi-layer route 700 includes two via nodes 716 and 718. These via nodes enable this path to traverse layers 2 and 3. These via nodes correspond to the hole 605 illustrated in FIG. 6. Specifically, the Q* engine converts this hole into the two via nodes 716 and 718 when it embeds the path 700., 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. 7, the Q* engine specifies the edge between nodes 748 and 750 as an ordered list of the following particles: node 750, exit 752, joint 708, exit 754, joint 736, exit 756, and node 748. In this edge's ordered list, joints 708 and 736 of paths 700 and 702 appear in the order that their routes cross this edge. As mentioned above, a topological route is a route that is defined in terms of its relation to other layout items. The Q* engine uses two different sets of associations to specify the topology of each topological route. The first set is the ordered list of topological particles on the route, and the second set is the ordered list of topological particles on the edges intersected by the route. 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 port-geometry nodes) have a fixed location. The topological engine 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 Q* topological engine specifies and stores locations for the route-defining particles in order to be able to compute wirelength accurately. b. Overall Flow of the Q* Topological Router FIG. 8 illustrates a process 800 that provides the overall flow of the Q* topological engine in some embodiments. As shown in this figure, the process initially triangulates (at 805) the sub-region defined at 205. This triangulation will be further described below by reference to FIG. 9. After the triangulation, the process defines (at 810) an initial grouping of the nets in the sub-region. Different embodiments define the initial grouping differently. Some embodiments use a clustering approach that groups the nets that maximally interfere with each other. Some of these embodiments cluster the nets by (1) defining, for each net, a three-dimensional bounding box that contains the net's pins, (2) pair wise intersecting the bounding box of each net with each of the other nets, (3) computing the volume of intersection between the intersections, and (4) grouping the nets that have the greatest overlapping volume (i.e., that are likely to have the most amount of overlap). In some embodiments, the bounding boxes are rectangular bounding boxes that are defined with respect to a coordinate system that is rotated by 45.degree. with respect to the coordinate system that is aligned with the sides of the layout. Some embodiments might use a multi-clustering approach that allows some or all nets to be in more than one clustered group. After grouping the nets, the process selects (at 815) one of the groups identified at 810 for routing. Different embodiments make this selection differently. Some embodiments select the groups based on an initial ranking that depends on descending entropy values (i.e., descending estimated number of shortest routes) for all the nets in each group. Some embodiments specify the entropy of a net by (1) defining a grid of horizontal and vertical lines that are spaced apart by the minimum line to via spacing, (2) identifying the number of horizontal grid lines m and vertical grid lines n between the pins of each net, (3) computing the number of different n-Element sets in an m-n element set (i.e., computing ##EQU1## and (4) setting the net's entropy value equal to the log base 2 of this computation. The process 800 iterates through 815 several times. During some of the subsequent iterations, some embodiments select a group at 815 based on the number of unrouted or illegally routed nets in the group. After selecting a group at 815, the process 800 calls (at 820) a solving engine to find a topological route for each net in the selected group. In the embodiments described below, the solving engine typically defines a legal or illegal route for each net in the group. In the circumstances that it cannot even find an illegal route for one or more nets, the solving engine notifies the process 800, which then takes this failure into account at 825 and 830 described below. The operation of the solving engine will be further described below by reference to FIG. 21. Once the solving engine returns its solution (which may be incomplete) at 820, the process updates (at 825) the net groupings, if necessary. When necessary, the process updates the net groups based on the solution returned by the solving engine. The process 800 identified (at 810) the initial groupings based only on an estimated measure of interference between the nets. However, each time the process 800 receives a solution for a group of nets from the solving engine at 820, this process can receive or derive a more accurate measure of the interference between the nets in the groups. Based on this measure, the process might update the net groupings at 825. For instance, if the solution returned by the solving engine specifies that a net A uses the same edge as a net B, then the process updates the net groupings so that nets A and B are more likely to be clustered. At 830, the process determines whether it should terminate. In some embodiments, the process terminates only if it has found a legal route for all the nets in the region, or if it has unsuccessfully tried a particular number of times to find a legal solution for all the nets. If the process determines at 830 that it should not terminate, it returns to 815 to select another group of nets, and then repeats 820-830 for this newly selected group of nets. The process ends when it decides to terminate at 830. c. Triangulation Different embodiments use different decomposition techniques to create a topological structure for embedding topological routes. The embodiments described below use triangulated graphs for each layer of the routed sub-region. Specifically, these embodiments use a constrained Delaunay triangulation ("CDT") technique. Several such techniques are disclosed in C. L. Lawson, "Transforming triangulations", Discrete Math, 3:365-372, 1972; C. L. Lawson, "Software for C Surface Interpolation," In J. R. Rice, editor, Math Software III, pp 161-194, Academic Press, New York, 1977; L. J. Guibas, D. E. Knuth, and M. Sharir, "Randomized Incremental Construction of Delaunay and Voronoi Diagrams", Algorithmica, 7:381-413, 1992. FIG. 9 illustrates a triangulation process 900 that is used in some embodiment of the invention by the Q* topological routing engine. This process decomposes each layer of the sub-region into several triangular faces. Accordingly, this process initially selects (at 905) one of the layers of the sub-region. Next, the process (1) defines (at 910) a graph node at the location of each corner of the sub-region on that layer, and (2) defines (at 915) a graph node at the location of each geometry point of a port or obstacle in the selected sub-region layer. Some embodiments also define one node for each vpin in the selected sub-region layer. Other embodiments define a graph node for only some of the vpins. For instance, some embodiments select as triangulation nodes vpins that are near interior geometry nodes that are close to the boundary. Of the remaining vpins, these embodiments designate as nodes every nth (e.g., 5.sup.th) vpin around the boundary. The vpins that are not specified as nodes, are specified as joints in some embodiments. Also, in some embodiments, the process 900 defines (at 915) nodes on the sides of certain geometries to ensure that there are sufficient edges to detect congestion in the IC region. FIG. 10 illustrates the layout of FIG. 4 after nodes have been defined at each sub-region corner and at each port or obstacle geometry point. Next, as shown in FIG. 9, the process creates (at 925) two triangles by dividing the region along a diagonal line connecting two of the corner node vertices. The process then successively inserts (at 930) individual port or obstacle nodes in the created triangles to divide the triangles into smaller sub-triangles. Specifically, when a new node is inserted, the triangle containing that node is identified, and that triangle is further triangulated by connecting the newly inserted node to the vertices of the identified triangle. FIG. 11 illustrates this triangulation technique. In this example, two triangles 1120 and 1140 are created by connecting two diagonal nodes 1105 and 1110 of the sub-region layer. Next, a node 1115 is inserted in the sub-region. The triangle 1120 that contains this newly inserted node is then further triangulated into three smaller triangles 1125, 1130, and 1135 by connecting the newly inserted node to the vertices of triangle 1120. Each time the Q* topological engine defines (e.g., at 930) an edge between two nodes, it defines an exit between the two nodes. Also, each time the Q* topological engine defines a triangle (e.g., at 930), it defines the space within the triangle. After defining a set of triangles at 930, the process performs (at 935) an edge-flipping operation to maximize the minimal angle of each triangle, i.e., to make the triangulation Delaunay. This operation is done in order to improve the likelihood that the topological routes produced by the Q* topological engine can be converted into specific geometric routes. To have an absolute guarantee that the generated topological routes can be geometrized, a visibility graph needs to be constructed to analyze every edge between any two graph nodes that have unobstructed views of each other in the relevant routing metric to ensure that each such edge is not overcongested. However, such an approach would be computationally expensive. Hence, instead of examining the edge between each such pair of graph nodes, some embodiments use an edge-flipping Delaunay triangulation as a good approximation of the visibility graph. FIGS. 12 and 13 illustrate why maximizing the minimal angle of each triangle improves the likelihood that the generated topological routes can be geometrized. In these figures, nodes 1205 and 1210 do not have an edge between them. Hence, the Q* topological engine cannot measure the congestion of the straight-line path between these two nodes. It can, however, measure the congestion on edges 1215, 1220, 1225, 1230, and 1235. In FIG. 12, the triangles are equilateral triangles, and therefore have the largest minimal angles. As illustrated in FIG. 12, it is relatively unlikely that a set of topological routes exist that could overfill the capacity of the straight-line path between nodes 1205 and 1210 without overcongesting the capacity of edge 1235. However, as illustrated in FIG. 13, when the adjoining triangles have small minimal angles, it is quite possible that a set of paths overcongest the straight-line path between nodes 1205 and 1210 without overcongesting the capacity of the adjoining edge 1235. Some embodiments perform an edge-flipping operation by identifying, for each triangle, a circle that encompasses all of the triangle's vertices. If that circle encompasses the vertex of another triangle as well, and if the two triangles do not jointly form a non-convex polygon, then the common edge between the two triangles is flipped. Flipping an edge between two triangles means deleting the existing common edge between the two triangles and defining a new common edge between the two vertices of the triangles that were not previously connected. The edge flipping operation typically results in a new pair of triangles that has larger minimal angles than the original pair of triangles. This operation defines necessary exits and spaces for the new triangles, and discards the original pair of triangles and their associate spaces. When a pair of abutting triangles form a non-convex structure, the common edge between them is not flipped. FIGS. 14 and 15 illustrate one manner for performing the edge-flipping operation. FIG. 14 illustrates two triangles 1405 and 1410. Circle 1415 is the identified circle that encompasses all of the vertices of triangle 1405. This circle also includes the vertex 1420 of triangle 1410. As the two triangles do not form a non-convex polygon, the common edge 1425 between these two triangles is flipped. FIG. 15 illustrates the newly defined pair of triangles 1430 and 1435 and the edge 1440 between them. The edge 1425 between the triangles 1405 and 1410 would not have been flipped if the circle 1415 did not contain the vertex 1420 of triangle 1410. After performing the edge-flipping operation at 935, the process performs (at 940) a constraining operation to ensure that a triangle edge exists (1) between each pair of successive points of an obstacle or port, and (2) at the sub-region boundary edges. FIG. 16 provides a pictorial example of this operation. This figure illustrates two successive pairs of obstacle or port points 1605 and 1610 that do not share an edge after the edge-flipping operation of 935. FIG. 16 illustrates the constraining operation flipping three different edges 1615, 1620, and 1625 until an edge 1630 exists between the two node points 1605 and 1610. Once this edge exists, it is identified as a constrained edge that should not be removed. Accordingly, this operation is referred to as a constraining operation, as it defines edges at sub-region boundaries and between successive pairs of geometry points, and then marks the edges as constrained. Next, the process performs (at 945) a follow-up edge-flipping operation without flipping the edges constrained at 940. This follow-up operation is to try to maximize the minimal angle of the triangles as much as possible while respecting the constrained edges. The process then determines (at 950) whether it has examined all the sub-region's layers. If not, the process transitions back to 905 to select another layer and to repeat 910 through 945 to triangulate the newly selected layer. Otherwise, the process identifies (at 955) holes in the spaces of the triangles that it defined. FIG. 17 illustrates a hole-identification process 1700 that the Q* topological routing engine can use to try to specify holes for the spaces of a triangle (referred to as the examined triangle). After triangulation, the topological engine performs (at 955) the process 1700 for each triangle that it has defined. This engine also uses this process at other stages in the routing process. In general, this engine uses all or some of this process each time it creates a new space (e.g., when it creates new triangles, of when modifies previously defined triangles). The process 1700 initially identifies (at 1705) all triangular faces that overlap the examined triangular face in the layer above, and if applicable, in the layer below. The overlapping faces can be identified based on the x- and y- coordinates of the nodes of the faces. In some embodiments, the topological engine stores for each face a list of all faces that overlap it in the layers above and, if applicable, below. The process then identifies (at 1710) the overlapping faces that are potential via destinations from the examined face. Specifically, for each triangle, the Q* topological engine in some embodiments stores a polygon that approximates the legal area where the center of vias can be in the face in the absence of any route crossing the face. The engine identifies the polygon for each face by identifying the closest point within the face that a via can be to each obstacle on the layer, accounting for the via size and/or shape, the required spacing to obstacles, etc. If the result is disjoint or non-convex, the engine approximates by using the convex hull of the legal locations. The process 1700 uses the face polygons to identify quickly the overlapping faces that might be potential via destinations. In particular, at 1710, the process 1700 (1) intersects the examined face's polygon with the polygon of each overlapping face that it identified at 1705, and (2) identifies each overlapping face as a potential via destination if the intersection polygon computed for it has sufficient space for a via. The process 1700 then determines (at 1715) whether it identified at 1710 any overlapping face as a potential via destination. If not, the process ends. Otherwise, the process selects (at 1720) a potential via-destination face that it identified at 1710. For each space within each face, the Q* topological routing engine stores a polygon that specifics the legal area where the center of vias can be in the space. The engine identifies the polygon for each space by identifying the closest point within the space that a via can be to each obstacle on the layer, accounting for the via size and/or shape, the required spacing to obstacles, the required spacing to other routes crossing the face, etc. If the result is disjoint or non-convex, the engine approximates by using the convex hull of the legal locations. A space's polygon might be identical to its face's polygon (which, in some embodiments, is the case after the initial triangulation) or might be different than its face's polygon (which, in some embodiments, is the case when topological routes cross the face). The process 1700 specifies a hole for each pair of overlapping spaces when the intersection of the polygons of these spaces is at least a certain size (e.g., it is larger than a particular threshold value). Specifically, after selecting (at 1720) a potential via-destination face, the process 1700 identifies (at 1725) an intersection polygon for each combination of space pairs in the examined and selected faces. When the intersection polygon for a space pair is at least a certain size, the process then identifies (at 1730) a hole for the space pair, if one such hole does not already exist. The process then determines (at 1735) whether it has examined all the potential via-destination faces that it identified at 1710. If not, the process transitions back to 1720 to select another such face. Otherwise, the process ends. The end result of the triangulation operations 900 is a set of triangulated sub-region layers, which can be used to embed and remove topological routes in the sub-region. FIG. 18 illustrates an example of how the layout of FIG. 4 might look after triangulation. In some embodiments, the triangulation operation defines the capacity of each edge in the triangulated region. The above-described triangulation operation defines each edge's capacity whenever it creates the edge at 925 through 945. FIG. 19A illustrates a process 1900 that the topological engine can call each time it wants to identify the capacity of an edge in the triangulated sub-region. This process is designed to support multiple wiring models. As shown in FIG. 19A, the process 1900 determines (at 1905) whether either node of the edge belongs to a vpin. If so, the process identifies (at 1910) the edge as the capacity vector. If not, the process identifies (at 1915) the capacity vector as the vector that traverses the shortest distance between the sides of the geometry abutting one of the edge nodes and the sides of the geometry abutting the other edge node. After 1910 or 1915, the process 1900 defines the edge capacity as the length of the largest projection of the capacity vector onto one of the legal routing directions. The projection P of the capacity vector C onto a legal routing direction D is given by where .alpha. is the angle between the capacity vector C and the legal routing direction D. Accordingly, the edge capacity is the magnitude of the projection vector. The largest projection of the capacity vector can be identified (at 1920) in a variety of ways. Some embodiments compute the magnitude of the capacity vector's projection onto all the legal routing directions and then select the largest. Others identify the routing direction that makes the smallest angle with the capacity vector, define this routing direction as the direction of projection, and then compute the projection of this capacity vector onto the identified routing direction. Other embodiments might compute the edge capacities slightly differently from process 1900. For instance, some embodiments might define each edge (including an edge that does not connect to vpins) to be its own capacity vector. Some of these embodiments then specify each edge's capacity as the edge's largest projection onto one of the legal routing directions. FIG. 19B illustrates the different ways discussed above for defining the capacity of an edge. FIG. 19B illustrates an edge 1925 between two nodes 1930 and 1935 on an octilinear layer like the one shown in FIG. 1. In this example, vector 1965 is the vector that traverses the shortest distance between sides 1945 and 1950 abutting node 1930 and sides 1955 and 1960 abutting node 1935. Some embodiments would select the edge 1925 as the capacity vector. For these embodiments, the projection 1975 is the largest projection of this capacity vector onto one of the legal routing directions, which in this case is the +90.degree. direction. On the other hand, some embodiments would select the vector 1965 as the capacity vector. For these embodiments, the projection 1970 is the largest projection of the capacity vector 1965 onto a legal routing direction, which in this case is the +45.degree. direction. Defining an edge's capacity based on its capacity vector's largest projection onto a legal routing direction provided by the wiring model enables the Q* topological engine to produce topological routes that are customized for different wiring models. The embodiments described above identify an edge's capacity as the largest projection of the edge's capacity vector onto one of the legal routing directions. Other embodiments, however, might use other techniques to compute an edge's capacity from its capacity vector. For instance, some embodiments that use the octilinear wiring model of FIG. 1, (1) for each layer, identify eight sectors about the eight routing directions, (2) identify the sector of the edge's layer that contains the edge's capacity vector, and (3) project the capacity vector onto the routing direction associated with the identified sector. FIG. 20A illustrates eight sectors that some embodiments identify for a particular layer about the eight routing directions of FIG. 1. These eight sectors are defined between eight constraining angles: 22.5.degree., 67.5.degree., 112.50.degree., 157.5.degree., 202.5.degree., 247.5.degree., 292.5.degree., and 337.5.degree.. Some embodiments assume that these angles are the angles of edges that constrain the embedding of geometric routes about unrelated geometries in the layout. Some of these embodiments assume that net routes have equal widths and spacings in the Manhattan and diagonal directions on the particular layer. Computing the edge capacities by using the eight constraining angles and eight sectors illustrated in FIG. 20A is equivalent to defining the edge capacities as the largest projection of the capacity vectors onto the legal routing directions. Other embodiments, however, define the eight constraining angles of a particular layer differently. Therefore, they compute some edge capacities that are different than the largest projection of the edge capacity vectors onto the legal routing directions. These embodiments allow the widths and spacings of nets to be different in the Manhattan and diagonal directions on the same layer. These embodiments define the constraining angles on a layer based on the worst combination of net spacings and widths in the Manhattan and diagonal directions on the layer. FIG. 20B illustrates eight such constraining angles for a particular layer. In this figure, the angle cc can be computed based on the equation (1) below. ##EQU2## To understand this equation, the following variables need to be defined: i is a number from 1 to n representing one of n nets; k is a number from 1 to p representing one of p spacing constraints between nets and between nets and obstacles; S.sub.k.sup.m is a k.sup.th spacing between a net and another net or an unrelated geometry in a Manhattan direction of the particular layer; W.sub.i.sup.m is a width of the i.sup.th net in a Manhattan direction of the particular layer; S.sub.k.sup.d is the k.sup.th spacing constraint between a net and another net or an unrelated geometry in a diagonal direction of the particular layer, W.sub.i.sup.d is the width of the i.sup.th net in the diagonal direction of the particular layer. The values S.sub.k.y and W.sub.i.y are computed as follows: where the "ceil" operation in the above equations signifies rounding up to the next manufacturing grid, as the spacings and widths are expressed in terms of manufacturing grid units and the routes are defined with respect to the manufacturing grid. Given the above definitions, the variables S.sub.min.y and S.sub.min.sup.m are the related k.sup.th spacing constraints S.sub.k.y and S.sub.k.sup.m that produce the smallest ratio ##EQU3## Similarly, the variables W.sub.min.y and W.sub.min.sup.m are the related i.sup.th width constraints W.sub.i.y and W.sub.i.sup.m that produce the smallest ratio ##EQU4## FIG. 20C provides an example that illustrates some of the variables mentioned above, and describes the derivation of the equation (1). This figure illustrates two nets 2005 and 2010 bending around an obstacle 2015 of a particular layer. In this figure, S.sub.80.sup.m is the 80.sup.th spacing constraint specifying the spacing between the net 2005 and the obstacle 2015 in the Manhattan directions of the particular layer, S.sub.80.sup.D the 80.sup.th spacing constraint specifying the spacing between the net 2005 and the obstacle 2015 in the diagonal directions of the particular layer, W.sub.5.sup.m is the width of the net 2005 in the Manhattan directions of the particular layer, W.sub.5.sup.D is the width of the net 2005 in the diagonal directions of the particular layer, S.sub.122.sup.m is the 122.sup.nd spacing constraint specifying the spacing between the nets 2005 and 2010 in the Manhattan directions of the particular layer, and S.sub.122.sup.D is 122.sup.nd spacing constraint specifying the spacing between the nets 2005 and 2010 in the Manhattan directions of the particular layer, W.sub.10.sup.D is the width of the net 2010 in the Manhattan directions of the particular layer, W.sub.10.sup.D is the width of the net 2010 in the diagonal directions of the particular layer, S.sub.156.sup.m is the 156.sup.th spacing constraint specifying the spacing between the net 2010 and an obstacle 2050 in the Manhattan directions of the particular layer, and S.sub.156.sup.D is 156.sup.th spacing constraint specifying the spacing between (the net 2010 and the obstacle 2050 in the diagonal directions of the particular layer. FIG. 20C illustrates S.sub.80.y, W.sub.5.y, S.sub.122.y, W.sub.10.y, S.sub.156.y. In this figure, the points that define the route bends (i.e., in this case, the transitions from the -45.degree. direction to the vertical direction) are specified on the manufacturing grid. As shown FIG. 20C, S.sub.80.y is the difference in the y-coordinates of the vertex 2020 and the bend-defining point 2025 of the net 2005, W.sub.5.y is the difference in the y-coordinates of the bend-defining points 2025 and 2030 of the net 2005, S.sub.122.y is the difference in the y-coordinates of the bend-defining point 2030 of the net 2005 and the bend-defining point 2035 of the net 2010, W.sub.10.y is the difference in the y-coordinates of the bend-defining points 2035 and 2040 of the net 2010, and S.sub.156.y is the difference in the y-coordinates of the bend-defining point 2040 of the net 2010 and the vertex 2045 of the obstacle 2050. The five equations below specify how S.sub.122.y, S.sub.80.y, W.sub.5.y, W.sub.10.y, and S.sub.156.y are computed in order to define the bend-defining points on the manufacturing grid. In the example illustrated in FIG. 20C, the angle .alpha..sub.0 of a line connecting the obstacle vertex 2020 and the first bend point 2025 is arctan ##EQU5## The angle .alpha..sub.1 of a line connecting the obstacle vertex 2020 and the bend point 2035 is arctan ##EQU6## The angle .alpha..sub.2 of a line connecting the obstacle vertices 2020 and 2045 is: ##EQU7## This angle .alpha..sub.2 will always be greater or equal to the angle .alpha..sub.p : ##EQU8## where p-1 is the number of nets crossing a constraining edge. Equation (1) is obtained from the above equation, by realizing that for all p the angle .alpha..sub.p will be greater or equal to t