Method and apparatus for determining wiring routes by utilizing artificial neural networks

• US 5,402,359 A
• Filed: 09/20/1991
• Issued: 03/28/1995
• Est. Priority Date: 09/21/1990
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Oyanagi, Shigeru
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): WALDER, STEPHEN JOSEPH
• Application Number:
  US07/763,448
• Time in Patent Office: 1,285 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/807
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method for determining routes of wiring nets by utilizing artificial neural networks includes the steps of dividing the wired area into smaller areas, representing each boundary through which one wiring net passes is capable of passing as an artificial neuron, changing an output value of the artificial neuron according to whether or not the wiring net actually passes through the boundary, composing an artificial neural network in which the interaction between the artificial neurons is taken into consideration according to one or more prescribed conditions restricting each route of the wiring nets while changing the output values of the artificial neurons, converging the output values of all artificial neurons, and determining the routes of all wiring nets by judging whether or not each wiring net passes through a boundary according to the converged output values of the artificial neurons.

Claims

1. A method for determining a plurality of wiring routes in an area by utilizing an artificial neural network, comprising the steps of:

dividing said area into a plurality of smaller areas;

representing each boundary among said plurality of smaller areas through which one of said plurality of wiring routes is capable of passing as an artificial neuron;

changing an output value of an artificial neuron in accordance with whether or not a wiring route actually passes through a boundary which is represented as said artificial neuron;

composing an artificial neural network in which interaction between artificial neurons is taken into consideration according to prescribed conditions restricting each of said plurality of wiring routes while changing output values of said artificial neurons, said prescribed conditions including;

(1) for each of said wiring routes, at least one route must exist that passes through said boundary without being cut,

(2) each of said wiring routes must not diverge or join a plurality of said wiring routes at an arbitrary boundary, and

(3) a number of said wiring routes passing through a boundary must be less than a predetermined number;

converging said output values of all of said artificial neurons of which said artificial neural network is composed; and

determining each of said plurality of wiring routes by judging whether or not each of said plurality of wiring routes passes through a boundary represented as an artificial neuron according to said output values of said artificial neurons.

2. A method for determining a plurality of routes of wiring nets in a wired area by utilizing artificial neural networks, comprising the steps of:

dividing said wired area into a plurality of smaller areas;

representing each boundary among said plurality of smaller areas through which one of said wiring nets is capable of passing as an artificial neuron;

changing an output value of an artificial neuron in accordance with whether or not a wiring net actually passes through a boundary which is represented as said artificial neuron;

composing an artificial neural network in which interaction between artificial neurons is taken into consideration according to prescribed conditions restricting each of said plurality of routes of said wiring nets while changing output values of said artificial neurons, said prescribed conditions including;

(1) for each of said wiring nets, at least one route must exist that passes through each of said boundaries without being cut,

(2) a route of each of said wiring nets must not diverge or join a plurality of routes at an arbitrary boundary, and

(3) a number of routes of said wiring nets passing through a boundary must be less than a predetermined number;

converging said output values of all of said artificial neurons of which said artificial neural network is composed; and

determining each of said plurality of routes of said wiring nets by judging whether or not each of said wiring nets passes through a boundary represented as an artificial neuron according to said output values of said artificial neurons.

4. The method according to any of claims 2 or 3, wherein an output value of an artificial neuron assumes a binary value.

5. The method according to any of claims 2 or 3, wherein the composing step includes the steps of:

representing said prescribed restrictions by energy functions in which said output values of said artificial neurons are variables;

multiplying each of said energy functions by a suitable parameter to produce multiplied energy functions; and

summing said multiplied energy functions to produce a total energy function.

6. The method according to claims 5, wherein the converging step includes the steps of:

comparing said total energy function with the Hopfield energy function;

determining weight parameters of quadratic terms in said Hopfield energy function by utilizing identity relations between said total energy function and said Hopfield energy function;

determining external input parameters of linear terms in said Hopfield energy function by utilizing said identity relations between said total energy function and said Hopfield energy function; and

calculating an extreme minimum value of said total energy function by utilizing said weight and external input parameters.

3. A method for determining a plurality of routes of wiring nets in a wired area by utilizing artificial neural networks, comprising the steps of:

dividing said wired area into a prescribed number of smaller areas;

representing each of said wiring nets connecting across boundaries between said smaller areas as an artificial neuron;

changing an output value of an artificial neuron in accordance with whether or not each route of one of said wiring nets satisfies one or more prescribed restrictions, each route of one of said wiring nets corresponding to one output value of said artificial neuron;

composing an artificial neural network in which interaction between artificial neurons is taken into consideration to select a route satisfying one or more prescribed restrictions while changing output values of said artificial neurons;

converging said output values of all of said artificial neurons of which said artificial neural network is composed;

determining each of said plurality of routes of said wiring nets corresponding to said output values of said artificial neurons; and

repeating the dividing step after redividing each of said boundaries into a plurality of divided boundaries while taking into consideration said interaction between said artificial neurons according to one or more prescribed restrictions which restrict each of said routes by changing said output values of said artificial neurons, the representing step for representing each of said wiring nets and one or more new wiring nets as artificial neurons, the changing step, the composing step, the converging step, and the determining step for determining each of said plurality of routes of said wiring nets in more detail and routes of said one or more new wiring nets, this repeating step itself being repeated until all of said plurality of routes of said wiring nets in said wired area are determined.

7. The method according to claim 3, wherein said prescribed number of smaller areas is equal to 4.

8. The method according to claim 3, wherein one of said one or more prescribed restrictions of the changing step is that a number of routes of said wiring nets passing through each of said boundaries be equalized.

9. The method according to claim 3, wherein one of said one or more prescribed restrictions of the changing step is that each of said wiring nets pass through the shortest possible route.

10. The method according to claim 3, wherein one of said one or more prescribed restrictions of the changing step is that a number of turns of each of said routes be minimized.

11. The method according to claim 3, wherein one of said one or more prescribed restrictions of the step for repeating the dividing step is that a number of said routes passing through each of said plurality of divided boundaries be equalized.

12. The method according to claim 3, wherein one of said one or more prescribed restrictions of the step for repeating the dividing step is that a length of each of said routes passing through each of said plurality of divided boundaries be minimized.

13. An apparatus for determining a plurality of routes of wiring nets in a wired area by utilizing artificial neural networks, comprising:

dividing means for dividing said wired area into a plurality of smaller areas;

representing means for representing each boundary among said plurality of smaller areas through which one of said wiring nets is capable of passing as an artificial neuron;

changing means for changing an output value of an artificial neuron in accordance with whether or not a wiring net actually passes through a boundary which is represented as said artificial neuron;

composing means for composing an artificial neural network in which interaction between artificial neurons is taken into consideration according to prescribed conditions restricting each of said plurality of routes of said wiring nets while changing output values of said artificial neurons via said changing means, said prescribed conditions including;

(1) for each of said wiring nets, at least one route must exist that passes through each of said boundaries without being cut,

(2) a route of each of said wiring nets must not diverge or loin a plurality of routes at an arbitrary boundary, and

(3) a number of routes of said wiring nets passing through a boundary must be less than a predetermined number;

converging means for converging said output values of all of said artificial neurons of which said artificial neural network is composed; and

determining means for determining each of said plurality of routes of said wiring nets by judging whether or not each of said wiring nets passes through a boundary represented as an artificial neuron according to said output values of said artificial neurons converged by said converging means.

14. An apparatus for determining a plurality of routes of wiring nets in a wired area by utilizing artificial neural networks, comprising:

dividing means for dividing said wired area into a prescribed number of smaller areas;

representing means for representing each of said wiring nets connecting across boundaries between said smaller areas as an artificial neuron;

changing means for changing an output value of an artificial neuron represented by said representing means in accordance with whether or not each route of one of said wiring nets satisfies one or more prescribed restrictions, each route of one of said wiring nets corresponding to one output value of said artificial neuron;

composing means for composing an artificial neural network in which interaction between artificial neurons is taken into consideration to select a route satisfying one or more prescribed restrictions while changing output values of said artificial neurons via said changing means;

converging means for converging said output values of all of said artificial neurons of which said artificial neural network is composed;

determining means for determining each of said plurality of routes of said wiring nets corresponding to said output values of said artificial neurons converged by said converging means; and

repeating means for repeating the dividing step after redividing each of said boundaries into a plurality of divided boundaries while taking into consideration said interaction between said artificial neurons according to one or more prescribed restrictions which restrict each of said routes by changing said output values of said artificial neurons, the representing step for representing each of said wiring nets and one or more new wiring nets as artificial neurons, the changing step, the composing step, the converging step, and the determining step for determining each of said plurality of routes of said wiring nets in more detail and routes of said one or more new wiring nets, this repeating by the repeating means itself being repeated until all of said plurality of routes of said wiring nets in said wired area are determined.

15. A method for determining a plurality of routes of wiring nets in a wired area by utilizing artificial neural networks, comprising the steps of:

dividing said wired area into four smaller areas A, B, C and D, the smaller area A being enclosed by four boundaries Q1, Q4, R8, and R1 in clockwise order, the smaller area B being enclosed by four boundaries Q2, Q1, R2, and R3 in clockwise order, the smaller area C being enclosed by four boundaries Q3, Q2, R4, and R5 in clockwise order, and the smaller area D being enclosed by four boundaries Q4, Q3, R6, and R7 in clockwise order;

representing each of said wiring nets connecting across boundaries Q1, Q2, Q3, and Q4 between said four smaller areas A. B, C, and D as an artificial neuron;

changing an output value Vi of an artificial neuron in accordance with whether or not each route of one of said wiring nets satisfies prescribed restrictions, each route of one of said wiring nets corresponding to one output value Vi of said artificial neuron, said prescribed restrictions including;

(1) a number of routes of said wiring nets passing through each of said boundaries Q1, Q2, Q3, and Q4 is equalized,

(2) each of said wiring nets pass through the shortest possible route, and

(3) a number of turns of each of said routes is minimized;

composing an artificial neural network in which interaction between artificial neurons is taken into consideration to select a route satisfying said prescribed restrictions (1), (2), and (3) while changing output values Vi of said artificial neurons, by representing said prescribed restrictions (1), (2), and (3) by energy functions E5, E6, and E7, respectively, given by;

##EQU9## where N is an average number of wiring routes passing through each boundary, and n(Q1), n(Q2), n(Q3), n(Q4) are numbers of wiring routes passing through the boundaries Q1, Q2, Q3, and Q4, respectively, defined by;

##EQU10## iAB indicates the artificial neurons connecting the smaller areas A and B, iAC indicates the artificial neurons connecting the smaller areas A and C, iAD indicates the artificial neurons connecting the smaller areas A and D, iBC indicates the artificial neurons connecting the smaller areas B and C, iBD indicates the artificial neurons connecting the smaller areas B and D, iCD indicates the artificial neurons connecting the smaller areas C and D, iR1-R4 indicates the artificial neurons connecting the boundaries R1 and R4, iR2-R7 indicates the artificial neurons connecting the boundaries R2 and R7, iR3-R6 indicates the artificial neurons connecting the boundaries R3 and R6, iR5-R8 indicates the artificial neurons connecting the boundaries R5 and R8;

converging said output values of all of said artificial neurons of which said artificial neural network is composed;

determining each of said plurality of routes of said wiring nets corresponding to said output values of said artificial neurons; and

repeating the dividing step, the representing step for representing each of said wiring nets and one or more new wiring nets as artificial neurons, the changing step, the composing step, the converging step, and the determining step for determining each of said plurality of routes of said wiring nets in more detail and routes of said one or more new wiring nets, this repeating step itself being repeated until all of said plurality of routes of said wiring nets in said wired area are determined.