Source: http://www.google.com/patents/US5200908?dq=6,976,008
Timestamp: 2013-12-06 03:34:06
Document Index: 790544237

Matched Legal Cases: ['art 31', 'art 31', 'art 32', 'art 41', 'art 43', 'art 53', 'art 53', 'art 53', 'art 53', 'art 53', 'art 53', 'art 54', 'art 54', 'art 53', 'art 54', 'arts 11']

Patent US5200908 - Placement optimizing method/apparatus and apparatus for designing ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsA 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,...http://www.google.com/patents/US5200908?utm_source=gb-gplus-sharePatent US5200908 - Placement optimizing method/apparatus and apparatus for designing semiconductor devicesPublication numberUS5200908 APublication typeGrantApplication numberUS 07/533,540Publication dateApr 6, 1993Filing dateJun 5, 1990Priority dateJun 8, 1989Fee statusLapsedAlso published asDE69031197D1, EP0401687A2, EP0401687A3, EP0401687B1Publication number07533540, 533540, US 5200908 A, US 5200908A, US-A-5200908, US5200908 A, US5200908AInventorsHiroshi Date, Terumine HayashiOriginal AssigneeHitachi, Ltd.Patent Citations (12), Referenced by (53), Classifications (17), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetPlacement optimizing method/apparatus and apparatus for designing semiconductor devicesUS 5200908 AAbstract 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.
What is claimed is: 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.sup.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. 2. A method according to claim 1, wherein processors, the number of which is less than or equal to (n.sup.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.sup.2 processors are used.
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.sup.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.sub.x indicates the transposed vector of the vector x, t.sub.b indicates the transposed vector of the vector b, d.sub.kl indicates the distance between the k-th position and the l-th position, d.sub.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.sub.kp =0), c.sub.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.sub.ik and x.sub.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)=-(&#931;T.sub.ikjl u.sub.jl (t)-b.sub.ik) 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.sub.jl (t) of the t-th calculation result is given, a constraint variable u.sub.ik (t+1) is given by t+1-th calculation, and calculating the constraint variable u.sub.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.
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.sub.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.sub.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.sub.ik is set to 0.5.
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.sup.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. 13. An apparatus according to claim 12, wherein processors, the number of which is less than or equal to (n.sup.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.sup.2 processors are included in the processor 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.sub.x indicates the transposed vector of the vector x, t.sub.b indicates the transposed vector of the vector b, d.sub.kl indicates the distance between the k-th position and the l-th position, d.sub.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.sub.kp =0), c.sub.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.sub.ik and x.sub.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.sup.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. 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.
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: dx.sub.ik (t)=-(&#931;T.sub.ikjl u.sub.jl (t)-b.sub.ik) 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))} 20. An apparatus according to claim 15, further comprising initial-value setting means for setting the initial value of the variable u.sub.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.sub.jl to 0.5.
22. An apparatus according to claim 15, wherein processors, the number of which is less than or equal to (n.sup.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.sup.2 processors are included in the processor 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.sup.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. 25. A semiconductor device design apparatus according to claim 24, wherein the processors are interconnected to form a neural network.
In order to the attain the above object, according to the present invention, a processor network is used in which each of n.sup.2 processors is applied with its own output and the outputs of all other processors to solve a problem, a processor having coordinate values (i, k) calculates a constraint variable for a case where the i-th circuit element (where i=1 to n) is placed at the k-th position (where k=1 to n), until the constraint variable satisfies a constraint condition, so that a circuit evaluation can have an optimal value, and the position of a circuit element allotted to a processor which delivers an output satisfying a constraint condition, is determined from the coordinate values of the processor.
FIG. 4 is a diagram for explaining the processor network 12. As shown in FIG. 4, the network 12 is made up of a processor network part 31 and an output 32. The processor network part 31 includes a large number of processors 31a to 31g, and the processors are connected with one another so that each processor is applied with its own output and the outputs of all other processors. It is to be noted that only a portion of connections among the processors is shown in FIG. 4 for convenience' sake. In the output part 32, output terminals are provided on a one-to-one basis for each processor. For example, in a case where the positions of n circuit elements are calculated, that is, n positions corresponding to n circuit elements are calculated, n.sup.2 processors are used for calculation. In this case, it is assumed that n.sup.2 processors are placed in the form of an n column is required to perform an arithmetic operation for a case where the first circuit element is allotted to the first position, on the basis of an arithmetic expression mentioned later. Similarly, the processor 31b in the first row, the second column is required to perform an arithmetic operation for a case where the first circuit element is allotted to the second position, the processor 31d in the second row, the first column is required to perform an arithmetic operation for a case where the second circuit element is allotted to the first position, and the processor 31g in the n-th row, the n-th column is required to perform an arithmetic operation for a case where the n-th circuit element is allotted to the n-th position. In short, when the numbers of the circuit elements are indicated by i (where i=1 to n) and the numbers of the positions are indicated by k (where k=1 to n), an arithmetic operation for the combination of a circuit element and a position indicated by (i, k) is performed by a processor having coordinate values (i, k).
Although n.sup.2 processors are used in the above explanation, processors, the number of which is less than or equal to (n.sup.2 -1), may be used for performing the above arithmetic operations. In this case, the result of an arithmetic operation is stored in a memory, to be used in the following arithmetic operation. Thus, arithmetic operations can be performed in substantially the same manner as a case where the arithmetic operations are performed by n.sup.2 processors.
E=(1/2).sup.t where x and b indicate n-dimensional vectors, T an n .sup.+ X and .sup.+ b transposed vectors. The conditions for minimizing the energy function E are seeked to determine the positions of circuit elements. The above conditions are seeked under constraint that each component x.sub.i of the vector x has a value "0" or "1". It is to be noted that the matrix T is the weight matrix of the processor network, and the vector b is a threshold vector. The term "weight" used in the above description corresponds to the distance to a circuit element, for which an arithmetic operation is performed. The "weight" increases as the above distance is longer. Further, the term "threshold" indicates the probability that a specified circuit element is placed at a specified position, and the threshold increases as the probability that the specified circuit element is placed at the specified position, is higher.
Each processor updates the value of each component x.sub.i of the variable x in accordance with the following equations, to find a minimum value of the energy function E:
x.sub.i =(1/2)
First, the evaluation function setting part 41a sets the evaluation function of, for example, an optimization problem that the total wiring length among circuit elements is made as short as possible, as follows: ##EQU1## where d.sub.kl indicates the distance between the k-th position and the l-th position, d.sub.kp indicates the distance between the k-th position and the fixed position of the p-th circuit element, c.sub.ijm is given by an equation ##EQU2## M.sub.m is a net indicative of a connecting relation among circuit elements, i and j indicate circuit elements, p indicates a circuit element whose position is fixed, and u.sub.ik and u.sub.jl indicate variables.
The above evaluation function and energy function are used for a case where the position of a specified one of circuit elements which are to be placed, is previously determined on the basis of experience or under constraint conditions. In a case where there is not any circuit element whose position is fixed, the second term of the evaluation function and the second term of the E.sub.1 -part of the energy function are eliminated.
Next, the coefficient ratio determining part 43 determines a ratio A/D of the coefficient A of the E.sub.2 -part of the energy function E to the coefficient D of the E.sub.1 -part.
Now, explanation will be made of how the ratio A/D is determined. Let us study a change ΔE.sub.1 in E.sub.1 and a change ΔE.sub.2 in E.sub.2 in a case where a state that the E.sub.2 -part is made minimum (that is, a state that the constraint conditions are satisfied) is varied by changing the value of the variable x.sub.ik from "0" to "1". By using the number N of circuit elements included in the largest one of circuit element nets, the upper limit of ΔE.sub.1 can be written as follows: ##EQU5##
When the ratio A/D is determined so that a formula ΔE.sub.1 ≦ΔE.sub.2 is satisfied, the constraint conditions will be satisfied. Further, the placement of circuit elements is improved as the ratio A/D is smaller. Accordingly, an equation ΔE.sub.1 =ΔE.sub.2 is set, and thus the ratio A/D is given by the following equation: ##EQU6##
That is, in a case where the value of the variable u.sub.jl due to the t-th arithmetic operation, that is, u.sub.jl (t) is known, the processor having coordinate values (i, k) calculates the value of the variable u.sub.ik due to the (t+1)th arithmetic operation, that is, u.sub.ik (t+1), by using the following equations:
dx.sub.ik (t)=-(&#931;T.sub.ikjl u.sub.jl (t)-b.sub.ik)
where dt indicates an integration interval, and is experimentally determined, for example, dt is set to 0.01 sec. In the above arithmetic operation the initial value of the variable u.sub.ik is set to 0.5 (that is, u.sub.ik (0)=0.5). In a case where the value of the variable u.sub.ik at the (t+1)th arithmetic operation does not converge on "0" or "1", the processor takes in its own calculation result at the (t+1)th operation and the calculation results of other processors at the (t+1)th operation, to find dx.sub.ik (t+1), and performs the (t+2)th arithmetic operation. By repeating the arithmetic operation as mentioned above, only a single processor in each row (or each column) of the two-dimensional matrix formed of processors, can deliver an output equal to "1", and the remaining processors in each row (or each column) deliver outputs equal to "0". Thus, when the processor having coordinate values (i, k) delivers "1", the i-th circuit element is placed at the k-th position.
Each time an arithmetic operation is performed, n.sup.2 signals are sent from the processor network 12 to the CPU 52. Before each of the signals converges on a level "0" or "1", each signal has an indefinite level within a range from "0" to "1", for example, a level "0.3" or "0.9". When each signal converges, it has a definite level "0" or "1". The CPU 52 checks whether or not the arithmetic operation performed by the processor network 12 has converged, that is, whether or not the network 12 delivers n signals having the level "1". When the arithmetic operation performed by the network 12 has converged, signal processing is carried out as mentioned below.
FIG. 7 shows the construction of the CPU 52. In a case where n circuit elements are placed at n positions, n.sup.2 signals are delivered from the network 12.
In the present embodiment, the CPU 52 includes n.sup.2 judgement processors. It is to be noted that only three judgement processors 61, 62 and 63 are shown for the sake of brevity. The output signals from the network are applied to corresponding judgement processors. Each judgement processor calculates information for judging whether the input signal thereto converges or not, independently of other judgement processors, and delivers the result of calculation to the judgement part 53 and the adder 64. The adder 64 adds up the input signals thereto as mentioned later, and delivers the result of addition to the judgement part 53. It is to be noted that the CPU 52 includes n.sup.2 judgement processors to carry out parallel processing, thereby shortening a processing time. Alternatively, only a single high-speed processor may be included in the CPU 52, to carry out serial processing.
FIG. 8 shows the processing carried out by each judgement processor of FIG. 7. Referring to FIG. 8, variables C.sub.m (j) and PLACE(j) (where j=1 to n.sup.2) are initialized, that is, these variables are set to "0" (step 71). Then, it is checked whether or not the output signal from the processor which has coordinate values (i, k) and is connected to the m-th judgement processor, has a level "1" (step 72). When the output signal has the level "1", variables C.sub.m (i) and C.sub.m (k) are set to "1" (step 73), and the variable PLACE(i) is set to "k". The above values of these variables are sent to the judgement part 53. When it is judged in the step 72 that the output signal does not converge on the level "1", the values of the variables C.sub.m (λ) and C.sub.m (k) are kept at "0" (step 74). The values obtained in the step 73 or 74 are sent to the adder 64.
FIG. 9 is a diagram for explaining the operation of the adder 64. In the adder 64, the values of the variables C.sub.m (j) supplied from all the judgement processors are summed up, to form a variable COUNT(j) which is given by the following equation: ##EQU8##
FIG. 10 is a diagram for explaining the operation of the judgement part 53. The value of the variable COUNT(j) supplied from the adder 64 will first be explained. Let us consider a case where that one of processors for forming the network 12 which delivers an output having a value "1", has coordinate values (i, k). In this case, the values of diagonal components (i, i) and (k, k) of the n operation is performed for all of processors which deliver the output having the value "1". Thus, when the outputs of all of the processors for forming the network 12 converge, all the diagonal components of the matrix are set to "2". In other words, a circuit element corresponding to the diagonal component which is set to "2", can be placed.
The value of the variable COUNT(i) is the value of the diagonal component (i, i). Accordingly, the judgement part 53 carries out the following processing. That is, it is checked whether the value j lies in a range from 1 to n.sup.2 (step 91). When the value j lies in this range, it is checked whether or not the value of the variable COUNT(j) is equal to "2" (step 92). It is judged that the j-th circuit element corresponding to the variable COUNT(j) equal to "2" can be placed (step 93). While, it is judged that the j-th circuit element corresponding to the variable COUNT(j) different from "2" cannot be placed. The judgement part 53 delivers the result of judgement to the placement processing part 54.
FIG. 11 is a flow chart for explaining the operation of the placement processing part 54. When the result of judgement indicating whether the i-th circuit element can be placed or not, is sent from the judgement part 53 to the placement processing part 54, a variable C indicating the number of circuit elements which cannot be placed, and a variable FAIL(C) indicating the number of the circuit element which could not be placed, are both initialized, that is, the values of these variables are set to "0". Next, the following processing is carried out for n.sup.2 judgemental results. That is, it is checked whether or not the i-th circuit element can be placed. When the i-th circuit element can be placed, the i-th circuit element is placed at the position indicated by the value of the variable PLACE(i) supplied from a judgement processor. When it is judged that the i-th circuit element cannot be placed, the value of the variable C is incremented by one, and the value of the variable FAIL(C) is set to "i". The above processing is carried out for all the circuit elements. When the value of the variable C indicating the number of circuit elements which cannot be placed, is equal to "0", the placement of all the circuit elements is completed. When there are circuit elements which cannot be placed, the conventional iterative improvement method or simulated annealing method is applied for the circuit elements, to determine the positions of the circuit elements.
The weight matrix T.sub.ikjl is defined so that components indicated by (i=j) and (k=l), that is, all the diagonal components have a value "0". It is mathematically known that the placement of circuit elements which is determined by using the above weight matrix, corresponds to the local minimum.
When the position of the i-th circuit element which cannot be arranged, is determined by the conventional exchange method or the like, the output of the processor corresponding to the above position is set to "1", and the outputs of other processors allotted to the i-th circuit element are set to "0". Further, the values of those diagonal components of the weight matrix T which correspond to the coordinate values of processors having the output "1", are increased to, for example, 0.1 or 0.3. Then, the network 12 recalculates the variable u.sub.ik by using the weight matrix which has the increased diagonal components, till the variable u.sub.ik converges on a value "0" or "1". When the placement thus obtained agrees with the original placement (that is, the placement determined by using the exchange method or the like), the original placement indicates the optimal placement. When the original placement corresponds to a local minimum, the placement obtained by using the modified weight matrix, is different from the original placement. Thus, the optimal placement can be obtained by repeating the processing in the parts 11c, 12, 13, 112 of FIG. 12.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3629843 *May 11, 1970Dec 21, 1971Bell Telephone Labor IncMachine process for assigning interconnected components to locations in a planar matrixUS3681782 *Dec 2, 1970Aug 1, 1972Honeywell Inf SystemsMachine process for positioning interconnected components to minimize interconnecting line lengthUS3702003 *Oct 9, 1970Oct 31, 1972Marathon Oil CoAlgorithm to minimize iterative computation in a process for the analysis or design of a physical systemUS4577276 *Sep 12, 1983Mar 18, 1986At&T Bell LaboratoriesPlacement of components on circuit substratesUS4580228 *Jun 6, 1983Apr 1, 1986The United States Of America As Represented By The Secretary Of The ArmyAutomated design program for LSI and VLSI circuitsUS4593363 *Aug 12, 1983Jun 3, 1986International Business Machines CorporationSimultaneous placement and wiring for VLSI chipsUS4719591 *Nov 7, 1985Jan 12, 1988American Telephone And Telegraph Company, At&T Bell Labs.Optimization network for the decomposition of signalsUS4754408 *Nov 21, 1985Jun 28, 1988International Business Machines CorporationProgressive insertion placement of elements on an integrated circuitUSH354 *Apr 4, 1986Oct 6, 1987The United States Of America As Represented By The Secretary Of The ArmyLinear algorithm for non-linear interpolation for computer aided designsJPS6293760A * Title not availableJPS62243071A * Title not availableJPS63121978A * Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5361214 *Jul 9, 1991Nov 1, 1994Kabushiki Kaisha ToshibaMethod for automatically determining wiring routesUS5402359 *Sep 20, 1991Mar 28, 1995Kabushiki Kaisha ToshibaMethod and apparatus for determining wiring routes by utilizing artificial neural networksUS5416889 *Sep 19, 1994May 16, 1995Mitsubishi Denki Kabushiki KaishaMethod of optimizing combination by neural networkUS5452400 *Mar 11, 1994Sep 19, 1995Mitsubishi Denki Kabushiki KaishaMethod of optimizing a combination using a neural networkUS5465204 *Nov 5, 1992Nov 7, 1995Kabushiki Kaisha ToshibaHeuristic control system employing expert system, neural network and training pattern generating and controlling systemUS5495419 *Apr 19, 1994Feb 27, 1996Lsi Logic CorporationIntegrated circuit physical design automation system utilizing optimization process decomposition and parallel processingUS5533168 *Mar 6, 1995Jul 2, 1996Hitachi, Ltd.Data processing apparatus for obtaining optimum combination solution and method of obtaining optimum combination solutionUS5535134 *Jun 3, 1994Jul 9, 1996International Business Machines CorporationObject placement aidUS5555406 *Aug 30, 1994Sep 10, 1996Toyota Jidosha Kabushiki KaishaMethod and apparatus for assisting the design of parts of a productUS5557533 *Apr 19, 1994Sep 17, 1996Lsi Logic CorporationCell placement alteration apparatus for integrated circuit chip physical design automation systemUS5590063 *Jul 5, 1994Dec 31, 1996Motorola, Inc.Optimization method using parallel processorsUS5636125 *Nov 13, 1995Jun 3, 1997Lsi Logic CorporationComputer implemented method for producing optimized cell placement for integrated circiut chipUS5638292 *Jan 4, 1993Jun 10, 1997Kabushiki Kaisha ToshibaMethod for automatically optimizing cell placementUS5644500 *Jul 1, 1996Jul 1, 1997Fujitsu LimitedRouting program generating method and apparatus therefor, placement program generating method and apparatus therefor, and automatic routing method and apparatus thereforUS5691913 *Mar 27, 1995Nov 25, 1997Matsushita Electric Ind. Co.Layout designing apparatus for circuit boardsUS5740067 *Oct 19, 1995Apr 14, 1998International Business Machines CorporationMethod for clock skew cost calculationUS5740071 *Jun 7, 1995Apr 14, 1998International Business Machines CorporationMethod and apparatus for selective shape adjustment of hierarchical designsUS5745735 *Oct 26, 1995Apr 28, 1998International Business Machines CorporationLocalized simulated annealingUS5781439 *Nov 13, 1995Jul 14, 1998Lsi Logic CorporationMethod for producing integrated circuit chip having optimized cell placementUS5793644 *Sep 17, 1996Aug 11, 1998Lsi Logic CorporationCell placement alteration apparatus for integrated circuit chip physical design automation systemUS5808899 *Jun 28, 1996Sep 15, 1998Lsi Logic CorporationAdvanced modular cell placement system with cell placement crystallizationUS5812740 *Jun 28, 1996Sep 22, 1998Lsi Logic CorporationAdvanced modular cell placement system with neighborhood system driven optimizationUS5815403 *Apr 19, 1994Sep 29, 1998Lsi Logic CorporationFail-safe distributive processing method for producing a highest fitness cell placement for an integrated circuit chipUS5831863 *Jun 28, 1996Nov 3, 1998Lsi Logic CorporationAdvanced modular cell placement system with wire length driven affinity systemUS5835381 *Jun 28, 1996Nov 10, 1998Lsi Logic CorporationAdvanced modular cell placement system with minimizing maximal cut driven affinity systemUS5844811 *Jun 28, 1996Dec 1, 1998Lsi Logic CorporationAdvanced modular cell placement system with universal affinity driven discrete placement optimizationUS5867398 *Jun 28, 1996Feb 2, 1999Lsi Logic CorporationAdvanced modular cell placement system with density driven capacity penalty systemUS5870311 *Jun 28, 1996Feb 9, 1999Lsi Logic CorporationAdvanced modular cell placement system with fast procedure for finding a levelizing cut pointUS5870312 *Jun 28, 1996Feb 9, 1999Lsi Logic CorporationAdvanced modular cell placement system with dispersion-driven levelizing systemUS5872718 *Jun 28, 1996Feb 16, 1999Lsi Logic CorporationAdvanced modular cell placement systemUS5875117 *Apr 23, 1996Feb 23, 1999Lsi Logic CorporationSimultaneous placement and routing (SPAR) method for integrated circuit physical design automation systemUS5892688 *Jun 28, 1996Apr 6, 1999Lsi Logic CorporationAdvanced modular cell placement system with iterative one dimensional preplacement optimizationUS5903461 *May 23, 1997May 11, 1999Lsi Logic CorporationMethod of cell placement for an integrated circuit chip comprising chaotic placement and moving windowsUS5914887 *Apr 19, 1994Jun 22, 1999Lsi Logic CorporationCongestion based cost factor computing apparatus for integrated circuit physical design automation systemUS5914888 *Jun 28, 1996Jun 22, 1999Lsi Logic CorporationAdvanced modular cell placement system with coarse overflow removerUS5953518 *Mar 14, 1997Sep 14, 1999Lsi Logic CorporationYield improvement techniques through layout optimizationUS5963455 *Jun 28, 1996Oct 5, 1999Lsi Logic CorporationAdvanced modular cell placement system with functional sieve optimization techniqueUS5963975 *Sep 17, 1997Oct 5, 1999Lsi Logic CorporationSingle chip integrated circuit distributed shared memory (DSM) and communications nodesUS5971588 *Jun 28, 1996Oct 26, 1999Lsi Logic CorporationAdvanced modular cell placement system with optimization of cell neighborhood systemUS5980093 *Dec 4, 1996Nov 9, 1999Lsi Logic CorporationIntegrated circuit layout routing using multiprocessingUS6026223 *Jun 28, 1996Feb 15, 2000Scepanovic; RankoAdvanced modular cell placement system with overlap remover with minimal noiseUS6030110 *Jun 28, 1996Feb 29, 2000Lsi Logic CorporationAdvanced modular cell placement system with median control and increase in resolutionUS6067409 *Feb 11, 1997May 23, 2000Lsi Logic CorporationAdvanced modular cell placement systemUS6085032 *Jun 28, 1996Jul 4, 2000Lsi Logic CorporationAdvanced modular cell placement system with sinusoidal optimizationUS6155725 *Apr 19, 1994Dec 5, 2000Lsi Logic CorporationCell placement representation and transposition for integrated circuit physical design automation systemUS6219627 *Jul 12, 1994Apr 17, 2001Texas Instruments IncorporatedArchitecture of a chip having multiple processors and multiple memoriesUS6324436Sep 14, 1998Nov 27, 2001Fujitsu LimitedMethod for optimizing cost of manufacturing memory arraysUS6493658Apr 19, 1994Dec 10, 2002Lsi Logic CorporationOptimization processing for integrated circuit physical design automation system using optimally switched fitness improvement algorithmsUS7210112 *Aug 18, 2003Apr 24, 2007California Institute Of TechnologyElement placement method and apparatusUS7285487Jul 23, 2004Oct 23, 2007California Institute Of TechnologyMethod and apparatus for network with multilayer metalizationUS7342414Jan 31, 2003Mar 11, 2008California Institute Of TechnologyFast router and hardware-assisted fast routing methodUS7702155 *Apr 1, 2005Apr 20, 2010Glickman Jeff BEnergy minimization for classification, pattern recognition, sensor fusion, data compression, network reconstruction and signal processingUS7912290Apr 9, 2010Mar 22, 2011Glickman Jeff BEnergy minimization for classification, pattern recognition, sensor fusion, data compression, network reconstruction and signal processing* Cited by examinerClassifications U.S. Classification716/122, 706/19, 706/921, 716/135, 716/123International ClassificationG06Q10/04, G06F19/00, G06F17/50, G06N3/10, G06N3/00, H01L21/82, G06F15/18Cooperative ClassificationY10S706/921, G06N3/10, G06F17/5072European ClassificationG06F17/50L1, G06N3/10Legal EventsDateCodeEventDescriptionJun 12, 2001FPExpired due to failure to pay maintenance feeEffective date: 20010406Apr 8, 2001LAPSLapse for failure to pay maintenance feesOct 31, 2000REMIMaintenance fee reminder mailedSep 30, 1996FPAYFee paymentYear of fee payment: 4Jun 5, 1990ASAssignmentOwner name: HITACHI, LTD., A CORP OF JAPAN, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:DATE, HIROSHI;HAYASHI, TERUMINE;REEL/FRAME:005326/0860Effective date: 19900523Jun 5, 1990AS02Assignment of assignor's interestOwner name: DATE, HIROSHIEffective date: 19900523Owner name: HAYASHI, TERUMINEOwner name: HITACHI, LTD., 6, KANDA SURUGADAI 4-CHOME, CHIYODARotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google