Routing method and apparatus Number:7,155,697 from the United States Patent and Trademark Office (PTO) owispatent A method for routing of some embodiments defines global routes for nets in an arbitrary region of a circuit layout in which each net has a set of pins. The method uses a first set of lines of measure the length of the global routes, a second set of lines to measure congestion of the global routes, and a third set of lines to partition the arbitrary region into a first set of sub-regions. For each net, the method identifies a global route that connects a group of first-set sub-regions that contain the net's set of pins.<H apparatus, Routing, Routing, method, , 7155697.html, Patent, pto, 7155697

Title: Routing method and apparatus

Abstract: A method for routing of some embodiments defines global routes for nets in an arbitrary region of a circuit layout in which each net has a set of pins. The method uses a first set of lines of measure the length of the global routes, a second set of lines to measure congestion of the global routes, and a third set of lines to partition the arbitrary region into a first set of sub-regions. For each net, the method identifies a global route that connects a group of first-set sub-regions that contain the net's set of pins.

Patent Number: 7,155,697 Issued on 12/26/2006 to Teig, et al.

Inventors: Teig; Steven (Menlo Park, CA), Buset; Oscar (Morges, CH), Jacques; Etienne (Sunnyvale, CA), Caldwell; Andrew (Santa Clara, CA), Frankle; Jonathan (Los Gatos, CA)
Assignee: Cadence Design Systems, Inc. (San Jose, CA)

Appl. No.: 10/046,926

Filed: January 13, 2002

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
10041957	Jan., 2002
10013816	Oct., 2001	6957410
60337504	Dec., 2001
60314580	Aug., 2001

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

Current International Class: G06F 17/50 (20060101)

Field of Search: 716/12-15

References Cited [Referenced By]

U.S. Patent Documents


4593363	June 1986	Burstein et al.
4615011	September 1986	Linsker
4673966	June 1987	Shimoyama
4782193	November 1988	Linsker
4855929	August 1989	Nakajima
5097422	March 1992	Corbin, II et al.
5251147	October 1993	Finnerty
5267176	November 1993	Antreich et al.
5281151	January 1994	Arima et al.
5360948	November 1994	Thornberg
5375069	December 1994	Satoh et al.
5532934	July 1996	Rostoker
5566078	October 1996	Ding et al.
5578840	November 1996	Scepanovic
5587923	December 1996	Wang
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
5640327	June 1997	Ting
5650653	July 1997	Rostoker et al.
5657242	August 1997	Sekiyama et al.
5663891	September 1997	Bamji et al.
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.
5784289	July 1998	Wang
5798936	August 1998	Cheng
5811863	September 1998	Rostoker et al.
5822214	October 1998	Rostoker et al.
5838583	November 1998	Varadarajan et al.
5859449	January 1999	Kobayashi et al.
5875117	February 1999	Jones et al.
5889677	March 1999	Yasuda et al.
5898597	April 1999	Scepanovic et al.
5903461	May 1999	Rostoker et al.
5914887	June 1999	Scepanovic et al.
5973376	October 1999	Rostoker et al.
5980093	November 1999	Jones et al.
6035108	March 2000	Kikuchi
6058254	May 2000	Scepanovic et al.
6067409	May 2000	Scepanovic et al.
6068662	May 2000	Scepanovic et al.
6070108	May 2000	Andreev et al.
6088519	July 2000	Koford
6123736	September 2000	Pavisic et al.
6128767	October 2000	Chapman
6134702	October 2000	Scepanovic et al.
6150193	November 2000	Glenn
6155725	December 2000	Scepanovic et al.
6175950	January 2001	Scepanovic
6182271	January 2001	Yahagi
6216252	April 2001	Dangelo et al.
6219832	April 2001	Buzbee
6226560	May 2001	Hama et al.
6230306	May 2001	Raspopovic et al.
6247167	June 2001	Raspopovic et al.
6249902	June 2001	Igusa et al.
6253363	June 2001	Gasanov et al.
6260179	July 2001	Ohsawa et al.
6260183	July 2001	Raspopovic et al.
6262487	July 2001	Igarashi et al.
6289495	September 2001	Raspopovic
6292929	September 2001	Scepanovic et al.
6295634	September 2001	Matsumoto
6301686	October 2001	Kikuchi et al.
6307256	October 2001	Chiang et al.
6316838	November 2001	Ozawa et al.
6324674	November 2001	Andreev et al.
6324675	November 2001	Dutta et al.
6327693	December 2001	Cheng et al.
6327694	December 2001	Kanazawa
6330703	December 2001	Saito et al.
6330707	December 2001	Shinomiya 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.
6415422	July 2002	Mehrotra et al.
6436804	August 2002	Igarashi et al.
6442743	August 2002	Sarrafzadeh et al.
6446245	September 2002	Xing et al.
6448591	September 2002	Juengling
6463575	October 2002	Takahashi
6473891	October 2002	Shively
6480991	November 2002	Cho et al.
6490713	December 2002	Matsumoto
6516455	February 2003	Teig et al.
6519751	February 2003	Sriram 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.
2001/0003843	June 2001	Scepanovic et al.
2001/0009031	July 2001	Nitta et al.
2002/0069397	June 2002	Teig et al.
2002/0073390	June 2002	Teig et al.
2002/0100007	July 2002	Teig et al.
2002/0124231	September 2002	Teig et al.
2002/0133798	September 2002	Teig et al.
2002/0147958	October 2002	Teig et al.
2002/0157075	October 2002	Teig et al.
2002/0166105	November 2002	Teig et al.
2002/0170027	November 2002	Teig et al.
2002/0174412	November 2002	Teig et al.
2002/0182844	December 2002	Igarashi et al.
2002/0199165	December 2002	Teig et al.
2003/0005399	January 2003	Igarashi et al.
2003/0018947	January 2003	Teig et al.
2003/0023943	January 2003	Teig et al.
2003/0025205	February 2003	Shively
2003/0043827	March 2003	Teig et al.
2003/0056187	March 2003	Teig et al.
2003/0063568	April 2003	Teig et al.
2003/0063614	April 2003	Teig et al.
2003/0064559	April 2003	Teig et al.
2003/0066042	April 2003	Teig et al.
2003/0066044	April 2003	Teig et al.
2003/0066045	April 2003	Teig et al.
2003/0079193	April 2003	Teig et al.
2003/0088841	May 2003	Teig et al.
2003/0088844	May 2003	Teig et al.
2003/0088845	May 2003	Teig et al.
2003/0101428	May 2003	Teig et al.
2003/0115566	June 2003	Teig
2003/0121015	June 2003	Teig et al.
2003/0121017	June 2003	Andreev et al.

Foreign Patent Documents


64-15947	Jan., 1989	JP
H03-173471	Jul., 1991	JP
04000677	Jan., 1992	JP
H05-102305	Apr., 1993	JP
H05-243379	Sep., 1993	JP
H07-86407	Mar., 1995	JP
H09-162279	Jun., 1997	JP
411296560	Oct., 1999	JP
2000-82743	Mar., 2000	JP

Other References

Das et al., "Channel Routing in Manhattan-Diagonal Model," IEEE, Jan. 1996, pp. 43-48. cited by examiner .
Ahuja, R. et al., Faster Algorithms for the Shortest Path Problem, Journal of the Association for Computing Machinery, vol. 37, No. 2, Apr. 1990, pp. 213-223. cited by other .
Brady, L. et al., Channel Routing on a 60.degree. Grid, extended abstract, pp. 956-931, no date. cited by other .
Brambilla, A. et al., Statistical Method for the Analysis of Interconnects Delay in Submicrometer Layouts, IEEE, Aug. 2001, pp. 957-966. cited by other .
Carothers, K., A Method of Measuring Nets Routability for MCM's General Area Routing Problems, 1999, pp. 186-192. cited by other .
Chen, H. et al., Physical Planning of On-Chip Interconnect Architectures, 2002, IEEE, International Conference, pp. 30-35. cited by other .
Cheng, K., Steiner Problem in Octilinear Routing Model, a Thesis Submitted for the Degree of Master of Science, National University Singapore, 1995, pp. 1-122. cited by other .
Chip Model with Wiring Cost Map, Aug. 1983, IBM Technical Disclosure Bulletin, vol. 26, iss. 3A, pp. 929-933. cited by other .
Cong, J. et al., Efficient Heuristics for the Minimum Shortest Path Steiner Arborescence Problem with Applications to VLSI Physical Design, Cadence Design Systems and UCLA Computer Science Department, pp. 88-95, no date. cited by other .
Cong, J. et al., Performance-Driven Multi-Layer General Routing for PCB/MCM Designs, UCLA Computer Science Department, 1998, pp. 356-361. cit- ed by other .
Enbody, R. et al., Near-Optimal n-Layer Channel Routing, 23.sup.rd Design Automation Conference, 1986, pp. 708-714. cited by other .
Fang, S. et al., Constrained Via Minimization with Practical Considerations for Multi-Layer VLSI/PCB Routing Problems, 28.sup.th ACM/IEEE Design Automation Conference, 1991, pp. 60-65. cited by other .
Hom, I. et al., Estimation of the Number of Routing Layers and Total Wirelength in a PCB Through Wiring Distribution Analysis, 1996, pp. 1-6. cited by other .
Hong, X. et al., Performance-Driven Steiner Tree Algorithms for Global Routing, 30.sup.th ACM/IEEE Design Automation Conference, 1993, pp. 177-181. cited by other .
Hu, J. et al., A Timing-Constrained Algorithm for Simultaneous Global Routing of Multiple Nets, IEEE/ACM International Conference on Computer Aided Design. ICCAD--2000. IEEE/ACM Digest of Technical Papers (CAT. No.00CH37140), Proceedings of International Conference on Computer Aided Design (ICCAD), San Jose, CA, USA, Nov. 5-9, 2000, pp. 99-103. cited by other .
Kastner, R. et al, Predictable Routing, IEEE/ACM International Conference on Computer Aided Design. ICCAD--2000. IEEE/ACM Digest of Technical Papers (CAT. No. 00CH37140), Proceedings of International Conference on Computer Aided Design (ICCAD), San Jose, CA, USA, Nov. 5-9, 2000. pp. 110-113. cited by other .
Khoo, K. et al., An Efficient Multilayer MCM Router Based on Four-Via Routing, 30.sup.th ACM/IEEE Design Automation Conference, 1993, pp. 590-595. cited by other .
Lillis, J. et al., Table-Lookup Methods for Improved Performance-Driven Routing, 1998, pp. 368-373. cited by other .
Lipski, W. et al., A Unified Approach to Layout Wirability, Mathimatical Systems Theory, 1987, pp. 189-203. cited by other .
Lodi, E. et al., A Preliminary Study of a Diagonal Channel-Routing Model, Algorithmica, 1989, pp. 585-597. cited by other .
Lodi, E. et al., Lecture Notes in Computer Science, A 4d Channel Router for a Two Layer Diagonal Model, pp. 464-476, Jul. 1988. cited by other .
Naclerio, N. et al., Via Minimization for Gridless Layouts, 24.sup.th ACM/IEEE Design Automation Conference, 1987, pp. 159-165. cited by other .
Nam, G. et al, Satisfiability-Based Layout Revisited: Detailed Routing of Complex FPGAs Via Search-Based Boolean SAT, 1999, pp. 167-175.. cited by other .
Oh, J. et al., Constructing Lower and Upper Bounded Delay Routing Trees Using Linear Programming, 33.sup.rd Design Automation Conference, 1996. cited by other .
Partitioning Logic on to Graph Structure, IBM Technical Disclosure Bulletin, Feb. 1990, vol. 32, iss. 9A, pp. 469-475. cited by other .
Phillips, N., Channel Routing by Constraint Logic, Department of Computer Science Southern Illinois University, ACM, 1992. cited by other .
Takashima, Y. et al, Routability of FPGAs with Extremal Switch-Block Structures, IEICE Trans. Fundamentals, vol. E81-A, No. 5, May 1998, pp. 850-856. cited by other .
Thakur, S. et al., Algorithms for a Switch Module Routing Problem, 1994, pp. 265-270. cited by other .
Theune, D. et al., HERO: Hierarchical EMC-constrained routing, Nov. 1992, IEEE pp. 468-472. cited by other .
Tseng, H., Timing and Crosstalk Driven Area Routing, pp. 378-381, no date. cited by other .
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. cited by other .
Wang, M. et al., Modeling and Minimization of Routing Congestion, Jan. 2000, IEEE proceedings of ASP-DAC, Asia and South Pacific, pp. 185-190. cited by other .
Wood, G. et al., FPGA Routing and Routability Estimation Via Boolean Satisfiability, Department of Electrical and Computer Engineering Carnegie Mellon University, Pittsburgh, PA, pp. 119-125, no date. cited by other .
Zhang, C.X. et al., Floorplan Design Using a Hierarchical Neutral Learning Algorithm, IEEE, Jun. 1991. pp. 2060-2063. cited by other .
Zhou, H. et al., An Optimal Algorithm for River Routing with Crosstalk Constraints, 1996. cited by other .
Zhou, H. et al.,Global Routing with Crosstalk Constraints, Department of Computer Sciences, University of Texas, 1998, pp. 374-377. cited by other .
Zhou, H. et al., Optimal River Routing with Crosstalk Constraints, ACM Transactions on Design Automation of Electronic Systems, vol. 3, No. 3, Jul. 1998, pp. 496-514. cited by other .
U.S. Appl. No. 09/737,220, filed Dec. 13, 2000, Steven Teig et al., Application regarding related placement technology. cited by other .
U.S. Appl. No. 09/737,245, filed Dec. 13, 2000, Steven Teig et al., Application regarding related placement technology. cited by other .
U.S. Appl. No. 09/739,460, filed Dec. 15, 2000, Steven Teig et al., Application regarding related placement technology. cited by other .
U.S. Appl. No. 09/739,589, filed Dec. 15, 2000, Steven Teig et al., Application regarding related placement technology. cited by other .
U.S. Appl. No. 09/742,171, filed Dec. 19, 2000, Steven Teig et al., Application regarding related placement technology. cited by other .
A.H. Farrahi, et al., Quality of EDA CAD Tools: Definitions, Metrics and Directions, Quality Electronic Design, 2000, Proceedings of the first International Symposium on Mar. 2000, pp. 395-405. cited by other .
A. Vannelli, et al., An adaptation of the interior point method for solving the global routing problem, Feb. 1991, IEEE pp. 193-203. cited by other .
B. Berger, et al., Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, Journal of the Association for Computing Machinery, pp. 500-542, Mar. 1995. cited by other .
C. Chiang, et al., Wirability of Knock-Knee Layouts with 45.degree. Wires, IEEE Transactions on Circuits and Systems, vol. 38, Issue 6, pp. 613-624, Jun. 1991. cited by other .
G. Overtone, EDA Underwriter 2 Finding Space in a Multi Layer Board, Electronic Engineering, Morgan-Grampian LTD, vol. 67, No. 819, pp. 29-30. cited by other .
G.D. Hachtel et al., Linear Complexity Algorithms for Hierarchical Routing, Jan. 1989, IEEE pp. 64-80. cited by other .
J.D. Cho, et al., Four-Bend Top Down Global Routing, IEEE, pp. 793-802, 1998. cited by other .
J. Su et al., Post Route Optimization for Improved Yield Using Rubber-Band Wiring Model, 1997 International Conference on Computer-Aided Design, pp. 700-706, Nov. 1997. cited by other .
J. Vicente, RSR: A New Rectilinear Steiner Minimum Tree Approximation for FPGA Placement and Global Routing, Proceedings of the 24.sup.th Euro Micro Conference, pp. 192-195, Aug. 1998. cited by other .
K. Powers et al., The 60.degree. Grid: Routing Channels in Width d/square root 3, VLSI, 1991, Proceedings., First Great Lakes Symposium in Kalamazoo, MI, USA, pp. 214-291, Mar. 1991. cited by other .
M. Alexander et al., Performance-Oriented Placement and Routing for field-programmable gate arrays, Proceedings of the European Design Automation Conference, pp. 80-85, 1995. cited by other .
M. Alexander et al., Placement and Routing for Performance-Oriented FPGA Layout, VLSI Design, vol. 7, No. 1, 1998. cited by other .
M. Igarashi et al., A Diagonal-Interconnect Architecture and Its Application to RISC Core Design, 2002 IEEE Solid-State Circuits Conference, pp. 210-460, Feb. 2002. cited by other .
P. Dood, et al., A Two-Dimensional Topological Compactor with Octagonal Geometry, 28.sup.th ACM/IEEE Design Automation Conference, pp. 727-731, Jul. 1991. cited by other .
P. Parakh, et al., Congestion Drive Quadratic Placement, Proceedings of Design Automation Conference, 1998, pp. 275-278. cited by other .
R. Putatunda et al., VITAL: Fully Automatic Placement Strategies for Very Large Semicustom Designs, Proceedings of the International Conference on Computer Design: VLSI in Computers and Processors, pp. 434-439 Oct. 1988. cited by other .
S. Dutt, et al., Probability-Based Approaches to VLSI Circuit Partitioning, IEEE Trans. On Computer Aided Design of IC's and Systems, vol. 19, No. 5, May 2000, pp. 534-549. cited by other .
Y. Sekiyama et al., Timing-Oriented Routers for PCB Layout Design of High-Performance Computers, International Conference on Computer Aided Design, pp. 332-335, Nov. 1991. cited by other .
C. Leiserson et al., Algorithm for Routing and Testing Routability of Planar VLSI Layouts, pp. 69-78, May 1985. cited by other .
S. Das et a., Channel Routing in Manhattan-Diagonal Model, 9.sup.th International Conference on VLSI Design, Jan. 1996. pp. 43-48. cited by other .
W. Wei-Ming Dai et a., Routability of a Rubber-Band Sketch. 28.sup.th ACM/IEEE Design Automation Conference, 1991. pp. 45-65. cited by other .
H. Chen, Routing L-Shaped Channels in Nonslicing-Structure Placement. 24.sup.th ACM/IEEE Design Automation Conference, pp. 152-165, 1987. cited by other .
I. Tollis, Techniques for Wiring in Non-Square Grids, pp. 66-69. May 1989. cited by other .
E. Lodi et al., A 2d Channel Router for the Diagonal Model, pp. 111-125, Apr. 1991. cited by other .
E. Lodi et al., Routing in Times Square Mode, pp. 41-48, Jun. 1990. cited by other .
K. Cheng-Kok et al., Manhattan or Non Manhattan? A Study of Alternative VLSI Routing Architectures. pp. 47-52, 2000. cited by other .
E. Lodi et al., Routing Multiterminal Nets in a Diagonal Model, pp. 899-902, 1988. cited by other .
D. Staepelaere et al., Surf: A Rubber-Band Routing System for Multichip Modules. pp. 18-26, 1993. cited by other .
S. Das et al., Routing of L-Shaped Channels, Switch boxes and Staircases in Manhattan-Diagonal Model, pp. 65-70m Jan. 1998. cited by other .
W. Schiele et al., A Gridless Router for Industrial Design Rule, 27.sup.th ACM/IEEE Design Automation Conference, pp. 626-631, 1990. cited by other .
J. Nester, A New Look at Hardware Maze Routing, Proceedings of the 12.sup.th ACM Symposium on Great Lakes Symposium on VLSI, pp. 142-147, Apr. 2002. cited by other .
Chen et al., Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing, May 1994, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions vol. 13 Issues, pp. 603-609. cited by othe- r .
Cong, J. et al., Multilevel Approach to Full Chip Gridless Routing, Nov. 2001, IEEE, pp. 396-403. cited by other .
Yan et al., Three-Layer Bubble-Sorting--Based Non-Manhattan Channel Routing, ACM Transactions on Design Automation of Electronic Systems, vol. 5, No. 3, Jul. 2000, pp. 726-734. cited by other.

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

Parent Case Text

CLAIM OF BENEFIT TO PRIOR APPLICATIONS

This patent application claims the benefit of the earlier-filed U.S. Provisional Patent Application entitled "Routing Method and Apparatus", having Ser. No. 60/314,580, and filed Aug. 23, 2001 and U.S. Provisional Patent Application entitled "Routing Method and Apparatus", having Ser. No. 60/337,504, and filed Dec. 6, 2001. This patent application is also a continuation application of U.S. patent application Ser. No. 10/041,957, filed Jan. 7, 2002. This patent application is also a continuation-in-part application of U.S. patent application Ser. No. 10/013,816, filed Oct. 19, 2001 now U.S. Pat No. 6,957,410.

Claims

We claim:

1. A method of defining global routes for nets in an arbitrary region of a circuit layout, wherein each net has a set of pins, the method comprising: a) using a first set of lines to measure length of the global routes; b) using a second set of lines to measure congestion of the global routes; c) using a third set of lines to partition the arbitrary region into a first set of sub-regions; and d) for each net, identifying a global route that connects a group of first-set sub-regions that contain the net's set of pins.

2. The method of claim 1, wherein the second and third sets of lines are identical.

3. A method of defining global routes for nets in an arbitrary region of a circuit layout, wherein each net has a set of pins, the method comprising: a) using a first set of intersecting lines to measure length of the global routes, wherein the first set of lines defines a first set of sub-regions within the arbitrary region of a circuit layout; b) using a second set of intersecting lines to measure congestion of the global routes; c) for each net, identifying a route that connects a group of first-set sub-regions that contain the net's set of pins; wherein each global route has a set of route segments, and each route segment connects two sub-regions in the first set of sub-regions.

4. The method of claim 3, further comprising measuring the length of each global route by summing the length of each global route segment in the route's set of route segments.

5. The method of claim 4, wherein using the second set of lines comprises measuring the congestion of the global routes across the second set of lines.

6. The method of claim 5, wherein the second set of lines define a plurality of congestion edges, wherein measuring the congestion of the global routes comprises measuring the congestion of routes across the congestion edges.

7. The method of claim 6, further comprising: once a global route is completed, specifying each global route only with respect to the global route's segments that cross the congestion edges.

8. The method of claim 3, wherein identifying the global route for each net comprises: starting at a first-set sub-region that contains a pin of the net, successively specifying a route segment that expands the route into a new first-set sub-region until the route connects all the group of sub-regions that contain the net's pins.

9. The method of claim 8, further comprising: at each expansion of a global route segment, computing a length cost; for each expansion of a global route segment across a second-set line, computing a congestion cost based on the congestion of the second-set line.

10. The method of claim 8, wherein specifying a first global route segment comprises examining a plurality of potential global route-segment expansions; wherein for each potential global route-segment expansion, computing a length cost; wherein if the potential global route-segment expansion intersects a second-set line, computing a congestion cost based on the congestion of the second-set line.

11. A computer program embedded in a computer readable medium, the computer program for defining global routes for nets in an arbitrary region of a circuit layout, the computer program comprising sets of instructions for: using a first set of lines to measure length of the global routes; using a second set of lines to measure congestion of the global routes; using a third set of lines to partition the arbitrary region into a first set of sub-regions; and identifying for each net, a global route that connects a group of first-set sub-regions that contain the net's set of pins.

12. A computer program embedded in a computer readable medium, the computer program for defining global routes for nets in an arbitrary region of a circuit layout, the computer program comprising sets of instructions for: using a first set of intersecting lines to measure length of the global routes, wherein the first set of lines defines a first set of sub-regions within the arbitrary region of a circuit layout; using a second set of intersecting lines to measure congestion of the global routes; and identifying for each net, a global route that connects a group of first-set sub-regions that contain the net's set of pins; wherein each global route has a set of global route segments, and each global route segment connects two sub-regions in the first set of sub-regions.

Description

FIELD OF THE INVENTION

The invention is directed towards method and apparatus.

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") 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. 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 commo