Method of determining routes for a plurality of wiring connections and a circuit board produced by such a method

• US 5,657,242 A
• Filed: 01/25/1993
• Issued: 08/12/1997
• Est. Priority Date: 01/23/1992
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Tanaka, Hiromi, Sekiyama, Yutaka, Fujihara, Yasuyuki, Kusuhara, Jiro, Hayashi, Terumine
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/010,070
• Time in Patent Office: 1,660 Days
• Field of Search: 364/489, 364/490, 364/491
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: H01L 23/5386 Geometry or layout of the interconnection structure
• CPC Class Codes: H01L 2924/00 Indexing scheme for arrangements or methods for connecting or disconnecting semiconductor or solid-state bodies as covered by H01L24/00
• CPC Class Codes: H01L 2924/0002 Not covered by any one of groups H01L24/00, H01L24/00 and H01L2224/00
• CPC Class Codes: H05K 1/0289 having a matrix lay-out, i.e. having selectively interconnectable sets of X-conductors and Y-conductors in different planes
• CPC Class Codes: H05K 2201/09972 Partitioned, e.g. portions of a PCB dedicated to different functions; Boundary lines therefore; Portions of a PCB being processed separately or differently
• CPC Class Codes: H05K 3/0005 for designing circuits by computer

Abstract

In order to determine the routes of wiring connections on a multi-layer circuit board, to form a suitable wiring pattern without local congestions of the wiring connections, the wiring region of the circuit board is considered as one or more areas. For each area, a preferred wiring direction is determined for each layer of the circuit board. Those preferred directions for the layers may be determined by proposing initial preferred wiring directions for each layer, determining whether there is congestion of the wiring connections in any area, and changing the wiring direction for one or more layers of such an area to reduce the congestion. Alternatively, the wiring directions can be determined for each layer without there being an initial wiring direction which is common to all areas. Furthermore, an excess number value may be obtained, which is the sum by which the desired number of wiring connections of an area exceed a predetermined value, for a series of candidate wiring directions of the layers of the area, and then the candidate is selected which has the minimum excess value.

Claims

1. A method of determining routes for a plurality of wiring connections for at least one predetermined area of a circuit board having a plurality of layers by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, said method comprising the steps of:

establishing a plurality of wiring directions for said plurality of wiring connections for said at least one predetermined area by selecting candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of said at least one predetermined area;

assigning a respective first one of said plurality of wiring directions to each of said plurality of layers for said predetermined area;

determining, for said at least one predetermined area, a predicted number of said plurality of wiring connections corresponding to each of said plurality of wiring directions;

determining, for said at least one predetermined area, whether said predicted number of wiring connections exceeds a predetermined degree of congestion in any of said plurality of wiring directions; and

assigning a respective second one of said plurality of wiring directions to at least one of said plurality of layers for said at least one predetermined area when said predicted number of wiring connections exceeds said predetermined degree of congestion for said predetermined area;

thereby to determine said routes for said plurality of wiring layers for said predetermined area on the basis of said respective second one of said plurality of wiring directions assigned to said at least one of said plurality of layers and said respective first one of said plurality of wiring directions assigned to said plurality of wiring layers.

2. A method according to claim 1, wherein said step of assigning a respective second one of said plurality of wiring directions is such as to eliminate said predetermined degree of congestion in said any of said plurality of wiring directions.

3. A method according to claim 1, wherein said plurality of wiring directions comprise first and second orthogonal wiring directions.

4. A method according to claim 1, wherein said plurality of wiring directions comprise first and second orthogonal wiring directions and at least one further wiring direction.

5. A method according to claim 1, wherein said at least one predetermined area is in the form of rectangle and at least one of said plurality of wiring directions is parallel to a side of said rectangle.

6. A method according to claim 1, wherein said step of determining, for said at least one predetermined area, a predicted number of wiring interconnections comprises:

determining a plurality of virtual routes for each of said wiring connections;

assigning a probability to each of said virtual routes; and

calculating said predicted number on the basis of said probability of each of said virtual routes.

7. A method according to claim 1, wherein the step of assigning a respective first one of said plurality of wiring directions is done according to an xy rule wherein alternative layers of the circuit board have predetermined wiring directions that are perpendicular to one another.

8. A method according to claim 1, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.

9. A method of determining routes for a plurality of wiring connections for a plurality of predetermined areas of a circuit board having a plurality of layers by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, comprising the steps of:

establishing a plurality of wiring directions for said plurality of wiring connections for said plurality of predetermined areas by selecting for each of said plurality of predetermined areas, candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of each of said plurality of predetermined areas;

assigning a respective first one of said plurality of wiring directions to each of said plurality of layers for said plurality of predetermined areas;

determining, for said plurality of predetermined areas, a predicted number of said plurality of wiring connections corresponding to each of said plurality of wiring directions;

determining, for said plurality of predetermined areas, whether said predicted number of wiring connections exceeds a predetermined degree of congestion in any of said plurality of wiring directions; and

assigning a respective second one of said plurality of wiring directions to at least one of said plurality of layers for said at least one of said plurality of predetermined areas when said predicted number of wiring connections exceeds said predetermined degree of congestion for said at least one of said predetermined areas;

thereby to determine said routes for said plurality of wiring layers for said plurality of predetermined areas on the basis of said respective second one of said plurality of wiring directions assigned to said at least one of said plurality of layers and said respective one first of said plurality of wiring directions assigned to said plurality of wiring layers.

10. A method according to claim 9, wherein said step of assigning a respective second one of said plurality of wiring directions is carried out independently for each of said plurality of predetermined areas.

11. A method according to claim 9, wherein said step of assigning a respective second one of said plurality of wiring layers is carried out such as to minimize the total over all said plurality of predetermined areas by which said predicted number of wiring connections exceed said corresponding predetermined degree of congestion for each of said plurality of predetermined areas.

12. A method according to claim 9, wherein said step of determining, for said at least one predetermined area, a predicted number of wiring interconnections comprises:

determining a plurality of virtual routes for each of said wiring connections;

assigning a probability to each of said virtual routes; and

calculating said predicted number on the basis of said probability of each of said virtual routes.

13. A method according to claim 9, wherein the step of assigning a respective first one of said plurality of wiring directions is done according to an xy rule wherein alternate layers of the circuit board have predetermined wiring directions that are perpendicular to one another.

14. A method according to claim 9, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.

15. A method of determining routes for a plurality of wiring connections for at least one predetermined area of a circuit board having a plurality of layers by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, comprising:

establishing a plurality of wiring directions for said plurality of wiring connections for said at least one predetermined area by selecting candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of said at least one predetermined area;

determining a plurality of degrees of congestion of a predicted number of said wiring connections for said at least one predetermined area for said plurality of wiring directions, each of said plurality of degrees of congestion corresponding to a selected assignment of a respective area of said plurality of wiring directions to each of said plurality of layers for said at least one predetermined area; and

selecting a desired one of said plurality of wiring directions, for said at least one area, for each of said wiring layers on the basis of said plurality of degrees of congestion;

thereby to determine said routes for said plurality of wiring connections on the basis of said selecting of said desired one of said plurality of wiring directions for each of said plurality of wiring layers.

16. A method according to claim 15, wherein said selecting of said desired one of said wiring directions for each of said plurality of wiring layers corresponds to a one of said plurality of degrees of congestion which has a minimum value among said plurality of degrees of congestion.

17. A method according to claim 15, wherein the step of establishing a plurality of wiring directions is done according to an xy rule wherein alternate layers of the circuit board have predetermined wiring directions that are perpendicular to one another.

18. A method according to claim 15, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.

19. A method of determining routes for a plurality of wiring connections for a plurality of predetermined areas of a circuit board having a plurality of layers, by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, comprising the steps of:

establishing a plurality of wiring directions for said plurality of wiring connections for said plurality of predetermined areas by selecting for each of said plurality of predetermined areas, candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of each of said plurality of predetermined areas;

determining a plurality of degrees of congestion of a predicted number of said wiring connections for said plurality of predetermined areas for said plurality of wiring directions, each of said plurality of degrees of congestion corresponding to a selected assignment of a respective one of said plurality of wiring directions to each of said plurality of layers for each of said plurality of predetermined areas; and

selecting a desired one of said plurality of wiring directions, for said each plurality of predetermined areas, for each of said wiring layers on the basis of said plurality of degrees of congestion;

thereby to determine said routes for said plurality of wiring connections on the basis of said selecting of said desired one of said plurality of wiring directions for each of said plurality of wiring layers.

20. A method according to claim 19, wherein said selecting of said desired one of said wiring directions for each of said wiring layers corresponds to a selection for which the sum over all said plurality of predetermined areas of said plurality of degrees of congestion is minimum.

21. A method according to claim 19, comprising:

establishing a plurality of wiring directions for said plurality of wiring connections for said at least one predetermined area;

determining a plurality of degrees of congestion of a predicted number of said wiring connections for said at least one predetermined area for said plurality of wiring directions, each of said plurality of degrees of congestion corresponding to a selected assignment of a respective area of said plurality of wiring directions to each of said plurality of layers for said at least one predetermined area; and

selecting a desired one of said plurality of wiring directions, for said at least one area, for each of said wiring layers on the basis of said plurality of degrees of congestion;

thereby to determine said routes for said plurality of wiring connections on the basis of said selecting of said desired one of said plurality of wiring directions for each of said plurality of wiring layers.

22. A method according to claim 19, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.

23. A method of determining routes for a plurality of wiring connections for at least one predetermined area on a circuit board having a plurality of layers by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, wherein, for said at least one predetermined area of said circuit board, candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of said at least one predetermined area are successively selected, and a wiring direction is determined for each layer on the basis of a degree of congestion of a predicted number of said wiring connections for said at least one predetermined area for said selected candidates of preset combinations of wiring directions, over all said plurality of layers.

24. A method according to claim 23, wherein initial wiring directions for each layer, before the degree of congestion is determined, are assigned according to an xy rule wherein alternate layers of the circuit board have predetermined wiring directions that are perpendicular to one another.

25. A method according to claim 23, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.

26. A method of determining routes for a plurality of wiring connections on a predetermined area of a circuit board, said circuit board having a plurality of layers by first determining a wiring direction for routing said wiring connections for each area of said circuit board prior to determining a routing pattern for said wiring connections for each of said layers, comprising:

a) establishing a plurality of wiring directions for said plurality of wiring connections for said at least one predetermined area by selecting candidates from preset combinations of wiring directions for areas of said plurality of layers corresponding to the same position of said at least one predetermined area;

b) assigning a respective one of said plurality of wiring directions to each of said plurality of layers;

c) determining an excess number value, said excess number value being the sum of the amounts by which a predicted number of wiring connections exceeds a predetermined value for each of said plurality of wiring directions on the basis of said assigning of said respective one of said plurality of wiring directions to each of said plurality of layers;

d) assigning at least one further one of said plurality of wiring directions to at least some of said wiring layers and repeating step c) on the basis of said assigning of said at least one further one of said plurality of wiring directions, thereby to determine a plurality of excess number values; and

e) determining the minimum excess number value, thereby to determine an optimum assigning of said plurality of wiring directions to each of said plurality of layers.

27. A method according to claim 26, wherein the step of assigning a respective one of said plurality of wiring directions is done according to an xy rule wherein alternate layers of the circuit board have predetermined wiring directions that are perpendicular to one another.

28. A method according to claim 26, wherein said method is carried out without iterative processing for determining said routing pattern for said wiring connections for each of said layers.