Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-11-13
2004-06-08
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06748574
ABSTRACT:
BACKGROUND OF THE INVENTION
1) Field of the Invention
The present invention relates to a method of and apparatus for determining an optimal solution to a uniform-density layout problem (a layout problem with a density-uniformalization condition), and also relates to a storage medium on which a program for determining the optimal solution is stored.
2) Description of the Related Art
In various fields, a kind of problem is known which requires arranging multiple elements (object elements) under certain conditions (layout conditions) in an optimum state. Such kind of problem is commonly called “a layout problem”, “an optimal layout problem”, “a layout optimization problem”, “a graph-mapping problem”, and the like (in the following, such kind of problem is referred to simply as “a layout problem” for convenience of description. The term “layout problem” is used in a common broad meaning for the present, until it is defined strictly later).
To take the above-mentioned LSI-circuits designing as an example, it is required to arrange multiple circuit elements (object elements) on a substrate with meeting the following conditions (layout conditions).
Each of the circuit elements must have a specific size and shape of its own.
The circuit elements must be subjected to a predetermined interconnection relationship.
The circuit elements must be arranged within a specified region on the substrate.
Such requirement is therefore just equivalent to the above-mentioned layout problem.
Other examples of the layout problem include a problem of optimizing delivery routes using trucks, a problem of optimizing operation schedules of factories, a problem of optimizing service diagrams of transport facilities, a problem of optimizing service schedules of nurses, a problem of optimizing Gantt chart (chart showing the relation between working hours and the quantity of production), etc.
A desirable solution to the layout problem is a layout of the object elements that satisfies the layout conditions in as optimum the state as possible. Such a solution is commonly called “a layout-optimizing solution”, “an optimal layout solution”, or simply “an optimal solution” (in the following, such kind of solution is referred to simply as “an optimal solution” for convenience of description. The term “optimal solution” also is used in a common broad meaning for the present, until it is defined strictly later).
A common process of obtaining an optimal solution to a layout problem is to introduce an objective function representing the desirability of a layout solution to the layout conditions and to determine the optimal solution using the objective function.
Specifically, an objective function is formulated so that it increases (or decreases) as desirable the state as it satisfies the layout conditions. And a layout solution that minimizes (or maximizes) the formulated objective function is calculated and determined as the optimal solution.
However, when there are many object elements and the layout conditions are complicated, the objective function is of so high order and so complicated that it is impossible or, even if not so, extremely difficult in practice to calculate exactly the right solution that minimizes (or maximizes) the objective function, because it requires huge operation time.
In such a case, the following technique is commonly used: to improve gradually an initial layout solution to the objective function using an iterative improvement method; to evaluate repeatedly a current layout solution in the improving one after another against specified criteria; and, when there appears any layout solution that satisfies the criteria, to determine the satisfactory layout solution as an approximately optimal solution to the objective function (such a process is often called “optimization of an objective function”). Examples of algorithms used for such optimization include the min-cut algorithm, the n-elements exchanging algorithm, the self-organization algorithm, etc.
To deal with a problem being of a higher order and more complicated, a technique using a so-called genetic algorithm is often used (although such an algorithm is otherwise called by various names, such as an evolutionary programming, and although their strict meanings differ from each other, the term “genetic algorithm” is generically used in a broad meaning throughout the following description). In this technique, various layout solutions being candidates for an optimal solution are expressed as genes, and a group of chromosomes each being a linear string of the genes are generated. Various kinds of operation such as selection, reproduction, crossover, mutation, etc. (genetic operations), are repeatedly performed on the group of chromosomes (population) while the generation of the population is updated. When there appears any gene representing a layout solution that satisfies given criteria, the satisfactory layout solution is determined as an approximately optimal solution to the objective function.
With such techniques as described above, it is possible to obtain, although not a strictly optimal solution objective function that would completely minimize (or maximize) the objective function, an approximately optimal solution that would almost minimize (or maximize) the objective function, with high accuracy enough for practical use.
In the following description, both the process of calculating a strictly optimal solution to a layout problem, as above-described firstly, and the techniques of obtaining any layout solution that satisfies given criteria to determine as an approximately optimal solution to a layout problem, as above-described subsequently, are generically called “to solve a layout problem” or “to search for an optimal solution to a layout problem”.
In the meantime, there is a kind of layout problem including a condition that the multiple object elements must be distributed in substantially uniform density (hereinafter called a “density-uniformalization condition”). The layout problem of this kind is referred to as a “uniform-density layout problem” in the following description.
To take the above-mentioned LSI-circuits designing for example again, in addition to the several layout conditions enumerated previously, another condition requiring the multiple object elements to be distributed in substantially uniform density will be demanded actually.
When object elements are numerous and the other layout conditions are much complicated, the density-uniformalization condition is too difficult and too rigid to be satisfied. Consequently, even if any objective function reflecting all the layout conditions including density-uniformalization condition (generic objective function) were formulated, the order of such an objective function would be excessive, so that it is quite difficult to search for an optimal solution to the objective function.
Thus the following technique has been taken conventionally in order to search for an optimal solution to the uniform-density layout problem: generating an objective function based on the remaining layout conditions other than the density-uniformalization condition; searching for a provisional optimal solution using the generated objective function; and improving the provisional optimal solution by executing an algorithm of some kind for reducing non-uniformity in density of the multiple object elements. Examples of such conventional non-uniformity reducing algorithm include the ones that the inventors proposed previously (Japanese Patent Laid-Open Publication No. HEI 11-134315 and Japanese Patent Laid-Open Publication No. 2000-90065), the one disclosed in REN-SONG TSAY et al., “PROUD: A SEA-OF-GATES PLACEMENT ALGORITHM” (IEEE DESIGN & TEST OF COMPUTERS, 1988), etc.
However, when solving a uniform-density layout problem by the above-mentioned conventional technique, huge arithmetic processing will be needed for executing the non-uniformity reducing algorithm in addition to the optimization of the objective function relating to the other layout conditions, so that it will take very long time to search fo
Sasagawa Fumiyoshi
Shinagawa Akio
Bowers Brandon
Fujitsu Limited
Siek Vuthe
Staas & Halsey , LLP
LandOfFree
Method of and apparatus for determining an optimal solution... 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 of and apparatus for determining an optimal solution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and apparatus for determining an optimal solution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326202