Method and apparatus for deciding a wiring route and for detecting a critical cut

• US 6,219,823 B1
• Filed: 11/12/1998
• Issued: 04/17/2001
• Est. Priority Date: 11/26/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hama, Toshiyuki, Etoh, Hiroaki
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US09/190,735
• Time in Patent Office: 887 Days
• Field of Search: 395/500.11, 395/500.13, 716/12
• US Class Current: 716/131
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: H05K 1/111 Pads for surface mounting, e.g. lay-out

Abstract

A plane is segmented into a plurality of regions whose vertexes are points which include the terminals, and a route search graph is generated. The route search graph expresses a connection relationship between the plurality of regions. A line connecting two objects in a shortest distance is recorded as a critical cut together with a width of wires that can go through the critical cut, the two objects including the terminals. A corresponding relationship relative to the critical cut and, when necessary, position information relative to the critical cut are recorded in edges of one of the plurality of regions related to the critical cut and in a necessary terminal. In deciding the wiring route in the route search graph and when it is detected, by using the position information recorded in a terminal or an edge on the wiring route being decided, that the wiring route has come into a certain region of the plurality of regions, the incoming direction in the critical cut related to the certain region is recorded by referring to the position information used in the detection. Also, when it is detected, from the position information recorded in a terminal or an edge which will be on the wiring route being decided, that the wiring route goes out of the region, it is judged whether the wiring route crosses the related critical cut, from the position information used when detecting the outgoing wiring route by referring to the incoming direction recorded in the related critical cut. Furthermore, when it is judged that the wiring route crosses the critical cut, it is judged whether the wiring route can be wired by referring to the width of wires that can go through the critical cut.

Claims

1. A method for detecting a critical cut that is not necessary to check, and determining a wiring capacity by using said critical cut, said critical cut being the minimum distance between two objects including a terminal disposed on a plane segmented into a plurality of triangular regions, said method comprising the steps of:

calculating a maximum flow by referring to a limitation on the size and disposition of said plane and terminal, the maximum flow being the maximum width of wires that can pass through each edge of said plurality of triangular regions;

calculating the wiring capacity for one critical cut;

in a union region consisting of the regions that said one critical cut crosses, calculating the sum of the maximum flows of edges being positioned on one side of said critical cut and constituting a boundary of said union region, updating, when said maximum flow of one edge of a triangular region is less than the sum of maximum flows of the other two edges of said triangular region, said maximum flow of said one edge to said sum of the maximum flows of the other two edges;

comparing said wiring capacity of said one critical cut with said sum of maximum flows; and

when the wiring capacity of said one critical cut is the larger one, as judged by the comparison, outputting said one critical cut as a critical cut that is not necessary to check.

2. The method for detecting a critical cut of claim 1, wherein the step of calculating the sum of the maximum flows includes, when the edge of said triangular region is a boundary of an obstacle, and said boundary includes both the boundary of said plane and the boundary of a region that cannot be wired, a step of:

setting said maximum flow of said edge to zero.

3. The method for detecting a critical cut of claim 2, wherein the step of calculating the sum of the maximum flows includes, when a critical cut from a vertex of said triangular region to the boundary of said obstacle is included in the interior of said triangular region, a step of:

causing a maximum flow of an edge, other than an edge which is the boundary of said obstacle, to be the same as the wiring capacity of said critical cut.