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

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.

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.

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.

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.

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.