Placement optimizing method/apparatus and apparatus for designing semiconductor devices

• US 5,200,908 A
• Filed: 06/05/1990
• Issued: 04/06/1993
• Est. Priority Date: 06/08/1989
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Date, Hiroshi, Hayashi, Terumine
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/533,540
• Time in Patent Office: 1,036 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/21, 395/22, 395/921
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06N 3/10 Interfaces, programming languages or software development kits, e.g. for simulating neural networks
• CPC Class Codes: Y10S 706/921 Layout, e.g. circuit, construction

Abstract

A method of finding the optimal placement of circuit elements is disclosed in which the optimal position of each circuit element is determined from the results of arithmetic operations performed by a processor network where a plurality of processors are interconnected so as to form a neural network, and each processor takes in its own output and the outputs of all other processors to solve a problem.

Claims

1. A method of determining optimal allocation of a multiplicity of circuit elements having a predetermined correlation with one another, comprising the steps of:

setting at least information for connecting the circuit elements and coordinates for arranging the circuit elements;

generating output values for allocating the circuit elements by executing operation in n² processors, each of which receives its own output and outputs of the other processors to substantially arrange the circuit elements on locations on the basis of a weight representing a degree of connection between the circuit elements and on the basis of a threshold representing an allocation possibility of the circuit elements on the locations, both the weight and the threshold being obtained from the information and the coordinates;

calculating a constraint variable in a processor of the coordinates value (i, k) such that an i-th circuit element (where i=1 to n) is arranged on a k-th location (where k-1 to n), so that a circuit evaluation function becomes an optimal value and converges up to a constraint condition; and

arranging a circuit element on the coordinates of one of the processor which generates an output value which converges the constraint variable to the constraint condition, by deciding whether the constraint variable is converged or not.

2. A method according to claim 1, wherein processors, the number of which is less than or equal to (n² -1), are used, each processor calculates constraint variables by serial processing, the result of calculation is stored in a memory, and the next calculation is carried out by using the result of calculation stored in the memory, to calculate constraint variable in a manner similar to the calculation in a case where n² processors are used.

3. A method according to claim 1, wherein the processors are connected to form a neural network.

4. A method of determining optimal allocation of a multiplicity of circuit elements having a predetermined correlation with one another, comprising the steps of:

setting at least information for connecting the circuit elements and coordinates for arranging the circuit elements;

generating output values for allocating the circuit elements by executing operation in n² processors, each of the processors receiving its own output and outputs of the other processors to substantially arrange the circuit elements on locations on the basis of a weight matrix T representing a degree of connection between the circuit elements and on the basis of a threshold vector b representing an allocation possibility of the circuit elements on the locations, both the weight matrix T and the threshold vector b being based on the information and the coordinates and obtained from an energy function E given by the following equations;

##EQU9## where x and b indicate n-dimensional vectors, t_x indicates the transposed vector of the vector x, t_b indicates the transposed vector of the vector b, d_kl indicates the distance between the k-th position and the l-th position, d_kp indicates the distance between the k-th position and the fixed position of the p-th circuit element (wherein, when there is no fixed circuit element, d_kp =0), c_ijm indicates a variable having a value "1" for a case where the i-th and j-th circuit elements form a net and having a value "0" for other cases, x_ik and x_jl indicate constraint variables, and A and D are coefficients, wherein the weight matrix T and threshold vector b thus determined are given by the following equations;

##EQU10## calculating a constraint variable in a processor of the coordinates value (i, k) such that an i-th circuit element (where i=1 to n) is arranged on a k-th location (where k=1 to n), from the following equations;

space="preserve" listing-type="equation">dx.sub.ik (t)=-(Σ

T.sub.ikjl u.sub.jl (t)-b.sub.ik)×

dt

space="preserve" listing-type="equation">x.sub.ik (t+1)=x.sub.ik (t)+dx.sub.ik (t)

space="preserve" listing-type="equation">u.sub.ik (t+1)=1/{1+exp(-x.sub.ik (t+1))}

where a constraint variable u_jl (t) of the t-th calculation result is given, a constraint variable u_ik (t+1) is given by t+1-th calculation, and calculating the constraint variable u_ik becoming convergent up to the following constraint condition;

##EQU11## arranging a circuit element on the coordinates of one of the processors which generates an output value which converges the constraint variable to the constraint condition, by deciding whether the constraint variable s converged or not.

5. A method according to claim 4, wherein the weight matrix T and the threshold vector b are determined by using a ratio A/D which is given by the following equation:

##EQU12## where N indicates the number of circuit modules or elements included in the maximal net.

6. A method according to claim 4, wherein the weight matrix T and the threshold vector b are determined by using a value of the ratio A/D which is smaller than the value of the ratio A/D given by the following equation:

##EQU13## where N indicates the number of circuit modules or elements included in the maximal net.

7. A method according to claim 6, wherein when the outputs of processors allotted to a circuit module or element cannot satisfy the constraint conditions, the position of the circuit module or element is determined by one of the exchange method and the simulated annealing method.

8. A method according to claim 7, wherein those diagonal components of the weight matrix which correspond to the position of the circuit module or element determined by one of the exchange method and the simulated annealing method, are incremented by a value within a range from 0 to 1, and the constraint variable u_ik is recalculated by using the modified weight matrix to find the optimal position of the circuit module or element.

9. A method according to claim 4, wherein the initial value of the constraint variable u_ik is set to a value within a range from 0 to 1.

10. A method according to claim 9, wherein the initial value of the constraint variable u_ik is set to 0.5.

11. A method according to claim 4, wherein the processors are connected to form a neural network.

12. An optimal allocation apparatus for allocating a multiplicity of circuit elements having a predetermined correlation with one another, comprising:

initialization means including at least a table storing information for connecting between the circuit elements and a table storing coordinates for arranging the circuit elements, for setting a weight representing a degree of connection between the circuit elements and a threshold representing an allocation possibility of the circuit elements on locations on the basis of the information and the coordinates;

processor network means including n² processors, each of the processors receiving its own output and outputs of the other processors to generate an output value on the basis of the weight and the threshold by executing calculation to substantially arrange the circuit elements on the locations such that a processor of the coordinates value (i, k) calculates a constraint variable in arranging an i-th circuit element (where i-1 to n) on a k-th location (where k=1 to n), so that a circuit evaluation function becomes an optimal value and converges up to a constraint condition; and

arrangement means for arranging a circuit element on the coordinates of the processor which generates an output value which converges the constraint variable to the constraint condition, by deciding whether the constraint variable is converged or not.

13. An apparatus according to claim 12, wherein processors, the number of which is less than or equal to (n² -1), are included in the processor network, a memory is additionally provided for storing the result of calculation, each processor calculates constraint variables by serial processing, the result of calculation is stored in the memory, and the next calculation is carried out by using data stored in the memory, to calculate constraint variables in a manner similar to the calculation in a case where n² processors are included in the processor network.

14. An optimal allocation apparatus according to claim 12, wherein the processors are interconnected to form a neural network.

15. An optimal allocation apparatus for allocating a multiplicity of circuit elements having a predetermined correlation with one another, comprising:

initialization means including at least a table storing information for connecting between the circuit elements and a table storing coordinates for arranging the circuit elements, for setting a weight matrix representing a degree of connection between the circuit elements and a threshold vector representing an allocation possibility of the circuit elements on locations on the basis of the information and the coordinates, both the weight matrix T and the threshold vector b being based on the information and the coordinates and obtained from an energy function E given by the following equation;

##EQU14## where x and b indicate n-dimensional vectors, t_x indicates the transposed vector of the vector x, t_b indicates the transposed vector of the vector b, d_kl indicates the distance between the k-th position and the l-th position, d_kp indicates the distance between the k-th position and the fixed position of the p-th circuit module or element (wherein, when there is no fixed circuit element, d_kp =0), c_ijm indicates a variable having a value "1" for a case where the i-th and j-th circuit elements form a net and having a value "0" for other cases, x_ik and x_jl indicate constraint variables, and A and D are coefficients, wherein the weight matrix T and threshold vector b thus determined are given by the following equations;

##EQU15## processor network means including n² processors, each of the processors receiving its own output and outputs of the other processors to generate an output value for allocating the circuit elements on the basis of the weight matrix T and on the basis of the threshold vector b by executing calculation to substantially arrange the circuit elements on the locations such that a processor of the coordinates value (i, k) calculates a constraint variable in arranging an i-th circuit element (where i=1 to n) on a k-th location (where k=1 to n), so that a circuit evaluation function becomes an optimal value and converges up to a constraint condition, the calculation of the constraint variable being obtained from the following equations;

##EQU16## arrangement means for arranging a circuit element on the coordinates of one of the processor which generates an output value which converges the constraint variable to the constraint condition, by whether the constraint variable is converged or not.

16. An apparatus according to claim 15, wherein the weight matrix T and the threshold vector b are determined by using a ratio A/D which is given by the following equation:

##EQU17## where N indicates the number of circuit modules or elements included in the maximal net.

17. An apparatus according to claim 15, wherein the weight matrix T and the threshold vector b are determined by using a value of the ratio A/D which is smaller than the value of the ratio A/D given by the following equation:

##EQU18## where N indicates the number of circuit modules or elements included in the maximal net.

18. An apparatus according to claim 17, further comprising means for determining the position of a circuit module or element, processors allotted to which fail to deliver outputs capable of satisfying a constraint condition, by one of the exchange method and the simulated annealing method.

19. An apparatus according to claim 18, further comprising means for setting those diagonal components of the weight matrix which correspond to the position of the circuit module or element determined by one of the exchange method and the simulated annealing method, to a value within a range from 0 to 1, and for recalculating the following equations:

space="preserve" listing-type="equation">dx.sub.ik (t)=-(Σ

T.sub.ikjl u.sub.jl (t)-b.sub.ik)×

dt

space="preserve" listing-type="equation">x.sub.ik (t+1)=x.sub.ik (t)+dx.sub.ik (t)

space="preserve" listing-type="equation">u.sub.ik (t+1)=1/{1+exp(-x.sub.ik (t+1))}

20. An apparatus according to claim 15, further comprising initial-value setting means for setting the initial value of the variable u_jl to a value within a range from 0 to 1.

21. An apparatus according to claim 20, wherein the initial-value setting means sets the initial value of the variable u_jl to 0.5.

22. An apparatus according to claim 15, wherein processors, the number of which is less than or equal to (n² -1), are included in the processor network, a memory is additionally provided for storing the result of calculation, such processor calculates constraint variables by serial processing, the result of calculation is stored in the memory, and the next calculation is carried out by using data stored in the memory, to calculate constraint variables in a manner similar to the calculation in a case where n² processors are included in the processor network.

23. An optimal allocation apparatus according to claim 15, wherein the processors are interconnected to form a neural network.

24. A semiconductor device design apparatus for use in design of semiconductor devices, comprising:

initialization means including at least a table storing information for connecting between the circuit elements and a table storing coordinates for arranging the circuit elements, for setting a weight representing a degree of connection between the circuit elements and a threshold representing an allocation possibility of the circuit elements on locations on the basis of the information and the coordinates;

processor network means including n² processors, each of the processors receiving its own output and outputs of the other processors to generate an output value for allocating the circuit elements on the basis of the weight and the threshold by executing calculation to substantially arrange the circuit elements on the locations such that a processor of the coordinates value (i, k) calculates a constraint variable in arranging an i-th circuit element (where i=1 to n) on a k-th location (where k=1 to n), so that a circuit evaluation function becomes an optimal value and converges up to a constraint condition; and

arrangement means for arranging a circuit element on the coordinates of one of the processor which generates an output value which converges the constraint variable to the constraint condition, by deciding whether the constraint variable is converged or not.

25. A semiconductor device design apparatus according to claim 24, wherein the processors are interconnected to form a neural network.