Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-12-19
2004-03-16
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06708320
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for automatically optimizing element placement by using a computer in the layout design of a semiconductor device.
2. Description of the Prior Art
The problem of optimization of element placement in a semiconductor results in a problem of searching for a placement to minimize a given cost function. The cost function herein denotes a function in which a value is uniquely determined with respect to one placement and also is referred to as an optimization object function. The cost function is defined appropriately in accordance with individual specific problems. The cost function differs depending on problems, for example, a problem of a placement of standard cells in a block, a problem of a placement of a transistor in the standard cell, or the like.
As a means for heuristically solving the optimization problem of element placement in a semiconductor with a defined cost function to be minimized using a computer, a method of assuming a combinatorial problem to be a physical system and of performing the generation of a thermal equilibrium condition by Monte-Carlo simulation under the control with a virtual temperature parameter is well known (S. Kirkpatrick et al. “Optimization by Simulated Annealing”, SCIENCE, Vol. 220, No. 4598, pp. 671-680, 1983). That is, under a constant virtual temperature, by performing the Monte-Carlo simulation in which a random placement change and a judgement whether the placement change is accepted under a rule set by analogy to statistical physics are repeated, a thermal equilibrium condition corresponding to the virtual temperature is generated and the thermal equilibrium condition is generated at each virtual temperature while slowly cooling from a high temperature to a cryogenic temperature (absolute temperature of about 0° C.), and finally an approximate minimum solution to the cost function is obtained. Such a method generally is referred to as a simulated annealing method (hereinafter, referred to as SA method), and broadly used for practically treating actual optimization problems of element placement.
The performance of the SA method is evaluated by a total repetition number of searches, which is a total sum of the repetition number of searches required at the time of Monte-Carlo simulation at all virtual temperatures, and an error between the cost function value of the final solution and the real minimum value of the cost function value. The speed of the optimization processing becomes high as the total repetition number becomes small, and the quality of solution becomes high as the error between the cost function value of the final solution and the real minimum value of the cost function value becomes small.
The technique for generating thermal equilibrium condition by the Monte-Carlo simulation under a constant virtual temperature is one of the important elementary techniques of the SA method. The precision of the thermal equilibrium achieved by the generation of the thermal equilibrium condition largely affects the quality of the final solution of the SA method. Furthermore, if the number of temperature points for observing the thermal equilibrium during the slow cooling process in the SA method is decreased, the effect of the precision of the thermal equilibrium at one temperature on the quality of the final solution is increased. Therefore, whether it is possible to achieve the precise thermal equilibrium by the generation of the thermal equilibrium condition involves not only the quality of the final solution but also the improvement of total processing efficiency in SA method, and is very important in performing the SA method. Therefore, in generating the thermal equilibrium condition, it is desired to generate a precise thermal equilibrium condition with a small repetition number of searches.
The conventional method for optimizing element placement in order to generate the thermal equilibrium conditions includes, for example, a method called a Metropolis method among the Monte-Carlo simulation methods. In generating the thermal equilibrium condition by the Metropolis method, the following Monte-Carlo simulation is carried out. When the cost function value is defined as E
j
for a placement S
j
that is jth generated at one virtual temperature T, and the cost function value is defined as E
j
+&Dgr;E for a placement S
j
′ that is locally changed from the placement S
j
, the placement S
j
′ is accepted as the (j+1)th placement at a probability of 1 if &Dgr;E≦0, while if &Dgr;E>0, at a probability expressed by exp (−&bgr;×&Dgr;E), wherein k denotes a virtual temperature normalization constant, and &bgr; denotes an amount that is in proportion to the reciprocal of the virtual temperature and is defined as &bgr;=1/(k×T).
Furthermore, another conventional method for optimizing element placement includes a method in which, in order to generate a thermal equilibrium condition, for example, by converging the average value of the cost function value for a placement generated at one virtual temperature T, the achievement of equilibrium is judged (Kurokawa et al. “Method for optimizing a placement by simulated phase transition method,” the 12th workshop (Karuizawa) “Circuit and System” pp. 451-456, 1999). In this method, in judging the convergence of the average value as the statistic, repetition placement search operations in order to generate placements sequentially are composed of repetition operations in a two-level hierarchy consisting of higher and lower levels; and each time a series of repetition searches in each of the lower levels are finished, the convergence of the average value in the lower level is judged.
In a case of the SA method using Monte-Carlo simulation by the Metropolis method for generating a thermal equilibrium condition as in the above-mentioned conventional method for optimizing element placement, since the Metropolis method is one of the approximate techniques for achieving the thermal equilibrium and gives precedence to the relief of a burden on the computer, it has a problem in sacrificing the precision of the thermal equilibrium.
Furthermore, as in the above-mentioned another modification method for element placement, the SA method in which the judgement of the thermal equilibrium is carried out by the convergence of the average value of the cost function values does not conform to the essential meaning of the physical thermal equilibrium. Also this method gives precedence to the relief of the burden on a computer, and thus sacrifices the precision of the thermal equilibrium. Furthermore, the judgement of the thermal equilibrium is carried out in which the convergence of the average value in the lower level while using the repetition operations of the two-level hierarchy is judged, so that it is necessary to increase the number of repetition in the lower level for actually observing the convergence of the average values, thus lowering the efficiency in generating the thermal equilibrium condition.
SUMMARY OF THE INVENTION
With the foregoing in mind, it is an object of the present invention to provide a method for optimizing element placement, which improves a method for judging whether a placement change is accepted at the time of generating thermal equilibrium and a method for achieving thermal equilibrium and generates the thermal equilibrium condition with high efficiency and high precision, thereby shortening the processing time by the SA method and improving the optimality of solution.
In order to achieve the above-mentioned object, a method for optimizing element placement according to the present invention is a method for optimizing element placement in layout design of a semiconductor device, and includes: generating a thermal equilibrium condition by performing a Monte-Carlo simulation at each virtual temperature while varying the virtual temperature that is a parameter for controlling a range in which a solution of element placement on a placement expression s
Lin Sun James
Matsushita Electric - Industrial Co., Ltd.
Smith Matthew
LandOfFree
Optimization method for element placement does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization method for element placement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization method for element placement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269548