Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-11-16
2001-07-17
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06263475
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method for optimizing the placement of components in designing a semiconductor device.
A simulated annealing (SA) method, one of combinatorial optimization methods, was proposed by S. Kirkpatrick et al. in “Optimization by Simulated Annealing”, SCIENCE, Vol. 220, No. 4598, pp. 671-680, May 1983. The SA method is used for carrying out a combinatorial optimization by adopting a Monte-Carlo (MC) method, which is a computer simulation method in thermodynamics. In accordance with the SA method, a temperature and an energy value defined in thermodynamics are respectively replaced with an effective temperature as a parameter and the value of an estimate (i.e., a cost value) used for estimating a placement produced in a combinatorial problem. Specifically, first, a cost value is obtained by exchanging the positions of two components selected from a placement produced at an effective temperature T. And then it is determined in accordance with the MC method using the cost value whether or not the exchange is allowable. If it has been determined that the exchange is not allowable, then the two components are returned to their original positions and another pair of components are newly selected from the placement. Alternatively, if it has been determined that the exchange is allowable, then another pair of components are newly selected from the modified placement reflecting the exchange, and the positions of the two components selected are exchanged with each other, thereby obtaining a cost value. This determination is carried out N times, which is a predetermined number of times the placement should be improved, thereby optimizing the component placement at the effective temperature T. In accordance with the SA method, the component placement is optimized at an effective temperature (high temperature) Ts, which is slowly lowered by a predetermined temperature every time. At every effective temperature lowered, the optimized placement is further optimized. By repeatedly performing this procedure, the temperature is slowly cooled down to an effective temperature (low temperature) Te. And a near-optimal solution can be found by regarding the placement at the effective temperature (low temperature) Te as an optimal solution.
FIGS. 4A through 4C
are diagrams illustrating a process for optimizing the placement of components (e.g., standard cells) by applying the SA method to a placement model so as to optimize a cost value (i.e., a total wire length). In this placement model, each component is bonded to four surrounding components (i.e., a four-direction bonding is implemented). A component located in the central 4×4 grid (where number Ne of components=16) is a component E to be placed, while a peripheral component Er is a fixed component. The distance between adjacent components is a unit distance of 1. The combinatorial problem is a problem of obtaining an optimum placement from an initial placement in which components are placed at random as shown in FIG.
4
A. In accordance with the SA method, an optimum placement shown in
FIG. 4C
is obtained from the initial placement shown in
FIG. 4A
via an intermediate placement shown in
FIG. 4B
by slowing lowering the effective temperature T.
Next, it will be described with reference to
FIG. 5
how the cost value changes according to the SA method.
FIG. 5
is a graph illustrating a relationship between an effective temperature T and a cost value where the number Ne of components is 25 (=5×5). The effective temperature T and the cost value are both represented by relative scales. While the effective temperature T is in the range from 10.0 to 4.0, the cost value repeatedly increases and decreases to a large degree. By contrast, while the effective temperature T is in the range from 4.0 to 1.0, the cost value still repeatedly increases and decreases, but generally tends to decrease as the effective temperature T decreases. A quantity obtained by differentiating a cost value by an effective temperature T is a quantity corresponding to specific heat. In
FIG. 5
, Tc is a temperature, at which the specific heat reaches a peak, and can be found as a result of the slow cooling employed in the SA method.
FIG. 6
is a table showing specific examples of the results obtained by a conventional pair-wise exchange (PW) method and the SA method. The pair-wise exchange method optimizes a placement by allowing components to be exchanged only when a cost value decreases. According to the SA method, each cost value, i.e., the total wire length, can be about a half to about a third of the counterpart obtained by the PW method. Therefore, a better solution (i.e., a better component placement) can be attained.
However, in accordance with the SA method, as the number of components increases, an iterative number of optimization processes drastically increases. As shown in
FIG. 6
, if the number Ne of components increases from 25 (=5×5) to 64 (=8×8) substantially threefold, the iterative number of optimization processes increases about elevenfold. And if the number Ne of components increases from 64 (=8×8) to 100 (=10×10) substantially twofold, the iterative number of optimization processes increases about ninefold. Accordingly, if one million or more transistors are to be placed in accordance with the SA method, then the process should be performed an enormous number of times. Thus, it is impossible to complete the process within a practical time.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a method for optimizing a component placement that can attain a component placement as good as that obtained by the SA method by performing a smaller number of optimization processes.
The present invention was made with particular attention paid to the temperature Tc shown in FIG.
5
. If the MC method is carried out at an effective temperature T in an approximate range from 1 to 2 (a region defined by the two broken lines), then the component placement would be improved and the iterative number of processes might be reduced as well as the case where the SA method is carried out while slowly cooling a high effective temperature. That is to say, according to the present invention, an optimum effective temperature is estimated in advance before the MC method is carried out.
As is well known, a ferromagnetic loses its magnetism at a high temperature. The temperature at which magnetism is lost is called a “phase transition temperature”. The method for optimizing a component placement of the present invention is, as it were, a simulated phase transition (SPT) method. In accordance with this method, an effective temperature, at which transition from a state where a component placement is out of order to a state where the component placement is in order happens, i.e., a simulated phase transition temperature Tc, is employed as an optimum effective temperature. As described above, specific heat reaches its peak at the temperature Tc. In other words, Tc is a temperature at which a cost value can be improved most efficiently. On the other hand, Tc is also a temperature in a boundary where transition from the disordered state to the ordered state happens. Accordingly, at Tc, some of the components might already be in order. Thus, the number of times a component has been exchanged (hereinafter, simply referred to as an “exchange number” of a component) in accordance with the MC method is observed as a “mobility” at Tc. And based on an exchange probability proportional to the mobility, the placement is improved.
Specifically, according to the present invention, an optimum effective temperature (i.e., simulated phase transition temperature) Tc is obtained in the following manner. First, two components are selected at random out of a list of exchange candidates and the positions thereof are exchanged with each other. Then, a cost difference per unit distance is obtained by dividing a difference between cost values of respecti
Akino Toshiro
Toyonaga Masahiko
Do Thuan
Matsushita Electric - Industrial Co., Ltd.
Nixon & Peabody LLP
Robinson Eric J.
Smith Matthew
LandOfFree
Method for optimizing component placement in designing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimizing component placement in designing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing component placement in designing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555195