US5200908A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Placement optimizing method/apparatus and apparatus for designing semiconductor devices
Assignee: Hitachi Ltd
•
Filing: 1990-06-05
•
Granted: 1993-04-06
•
Expires: 2010-06-05
Abstract
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.
Inventors
- 👤 Hiroshi Date
- 👤 Terumine Hayashi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 09:37
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/02; G06N3/10; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; Y; Y10; Y10S; Y10S706/00; Y10S706/902; Y10S706/919; Y10S706/921
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
209 words
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 2 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.
Claim 2
Independent Claim
209 words
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 2 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.
Claim 3
Dependent Claim
77 words
A method according to claim 1, wherein processors, the number of which is less than or equal to (n 2 -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 2 processors are used.
Claim 4
Dependent Claim
16 words
A method according to claim 1, wherein the processors are connected to form a neural network.
Claim 5
Independent Claim
400 words
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 2 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: dx.sub.ik (t)=-(ΣT.sub.ikjl u.sub.jl (t)-b.sub.ik)×dt x.sub.ik (t+1)=x.sub.ik (t)+dx.sub.ik (t) 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.
Claim 6
Independent Claim
400 words
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 2 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: dx.sub.ik (t)=-(ΣT.sub.ikjl u.sub.jl (t)-b.sub.ik)×dt x.sub.ik (t+1)=x.sub.ik (t)+dx.sub.ik (t) 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.
Claim 7
Dependent Claim
46 words
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.
Claim 8
Dependent Claim
57 words
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.
Claim 9
Dependent Claim
45 words
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.
Claim 10
Dependent Claim
74 words
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.
Claim 11
Dependent Claim
28 words
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.
Claim 12
Dependent Claim
20 words
A method according to claim 9, wherein the initial value of the constraint variable u ik is set to 0.5.
Claim 13
Dependent Claim
16 words
A method according to claim 4, wherein the processors are connected to form a neural network.
Claim 14
Dependent Claim
213 words
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 2 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.
Claim 15
Dependent Claim
213 words
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 2 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.
Claim 16
Dependent Claim
93 words
An apparatus according to claim 12, wherein processors, the number of which is less than or equal to (n 2 -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 2 processors are included in the processor network.
Claim 17
Dependent Claim
18 words
An optimal allocation apparatus according to claim 12, wherein the processors are interconnected to form a neural network.
Claim 18
Dependent Claim
405 words
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 2 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.
Claim 19
Dependent Claim
405 words
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 2 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.
Claim 20
Dependent Claim
46 words
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.
Claim 21
Dependent Claim
57 words
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.
Claim 22
Dependent Claim
44 words
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.
Claim 23
Dependent Claim
68 words
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: dx.sub.ik (t)=-(ΣT.sub.ikjl u.sub.jl (t)-b.sub.ik)×dt x.sub.ik (t+1)=x.sub.ik (t)+dx.sub.ik (t) u.sub.ik (t+1)=1/{1+exp(-x.sub.ik (t+1))}
Claim 24
Dependent Claim
31 words
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.
Claim 25
Dependent Claim
22 words
An apparatus according to claim 20, wherein the initial-value setting means sets the initial value of the variable u jl to 0.5.
Claim 26
Dependent Claim
93 words
An apparatus according to claim 15, wherein processors, the number of which is less than or equal to (n 2 -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 2 processors are included in the processor network.
Claim 27
Dependent Claim
18 words
An optimal allocation apparatus according to claim 15, wherein the processors are interconnected to form a neural network.
Claim 28
Dependent Claim
214 words
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 2 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.
Claim 29
Dependent Claim
214 words
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 2 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.
Claim 30
Dependent Claim
19 words
A semiconductor device design apparatus according to claim 24, wherein the processors are interconnected to form a neural network.
References Cited (Backward Citations)
US3629843A
Cited
US3702003A
Cited
US3681782A
Cited
US4580228A
Cited
US4593363A
Cited
US4577276A
Cited
JPS6293760A
Cited
US4719591A
Cited
US4754408A
Cited
USH354H
Cited
JPS62243071A
Cited
JPS63121978A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-04-05 | 1996-10-05 | 1997-04-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-04-05 | 2000-10-05 | 2001-04-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-04-05 | 2004-10-05 | 2005-04-06 | $7700.00 | Window Closed / Lapsed |