Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-07-23
2002-06-25
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S011000
Reexamination Certificate
active
06412100
ABSTRACT:
BACKGROUND OF THE INVENTION
(1) Field of the Invention
The present invention relates to a layout optimization problem solving method and program for use in solving a circuit layout optimization problem relating to optimum arrangement of circuits on, for example, a large-scale integrated (LSI) circuit; more commonly, to an element layout optimization problem relating to optimum arrangement of a plurality of elements (or elements to be arranged) in two or more dimensions, as well as to a computer-readable recording medium having the layout optimization problem solving program recorded thereon.
(2) Description of the Related Art
The element layout optimization problem is one relating to optimum arrangement, in a required space (or in a required area if the elements are two-dimensional), of a plurality of elements having a specified connection relationship. The problem is also called a graph mapping problem.
For example, if the optimum arrangement of individual circuits on the LSI circuit is determined, the LSI circuit can be made compact, and the length of wiring patterns used for interconnecting the circuits is minimized, thus enabling an improvement in wiring and the processing speed of the LSI circuit.
The element layout optimization problem can be solved by execution of an optimization problem solving algorithm (for example, a genetic algorithm, a min-cut method, an n-element exchange method, or a like method) to thereby determine the optimum layout of a plurality of elements in a required space, and by arranging the plurality of elements in the space on the basis of the determination.
If the element layout optimization is of large scale (that is, the number of elements to be optimally arranged is very large), the optimum layout of the elements is determined by taking the individual elements as points (or as the same shape) without consideration of size of the individual elements, in order to execute the optimization problem solving algorithm at high speed.
Since each of the elements has its own unique size, an overlap or clearance arises among elements even when the elements are arranged according to the thus-determined optimum layout, so that the arrangement of the elements is excessively loose or excessively dense.
In order to process the element layout optimization problem of large scale at high speed, an optimization problem solving algorithm is executed without consideration of size of the respective elements, and the resultant non-uniformity in density of the layout elements (layout unbalance) must be removed or reduced.
SUMMARY OF THE INVENTION
The present invention has been conceived to solve the foregoing problem, and the object of the present invention is to provide a layout optimization problem processing method which enables uniform arrangement of elements within space by reducing non-uniform arrangement in density of the elements, thereby processing an element layout optimization problem of large scale at high speed. Further, another object of the present invention is to provide a computer-readable recording medium on which is recorded a layout optimization problem processing program used for activating a computer to solve the element layout optimization problem.
To this end, the present invention provides a method of processing a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, comprising the steps of:
a first algorithm executing step of executing a genetic algorithm when information concerning the plurality of elements staying in an initial condition is available so that non-uniformity in density of the plurality of elements is reduced to bring the plurality of elements into a layout unbalance reduction halfway stage; and
a second algorithm executing step of executing a local layout unbalance reducing algorithm when information concerning the plurality of elements staying in the layout unbalance reduction halfway stage is available, whereby the non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage is further reduced.
Here, the genetic algorithm can be executed in the first algorithm executing step by expressing the states of layout of the plurality of elements as genes; and by using, as a candidate solution for a problem of arranging the plurality of elements within the space, a chromosome which comprises a sequence of the genes and is defined as the space.
At the time of execution of the genetic algorithm, crossover can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by exchanging at least one region selected from the plurality of regions in the chromosome with a counterpart portion in another chromosome.
Further, at the time of execution of the genetic algorithm, crossover can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by pasting a specific region of the plurality of regions within the chromosome to a counterpart portion region of another chromosome if the specific region is found to have lower non-uniformity in density than that of the counterpart region.
At the time of execution of the genetic algorithm, mutation can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by moving at least one of the plurality of elements within its respective regions.
Further, at the time of execution of the genetic algorithm, selection can be carried out as a genetic operation in the first algorithm executing step by use of a fitness function which enables a chromosome having lower non-uniformity in density of the plurality of elements to assume a great fitness value.
The present invention also provides a method of processing a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, comprising the steps of:
a first algorithm executing step of executing a genetic algorithm; and
a second algorithm executing step of executing a local layout unbalance reducing algorithm;
wherein the first algorithm executing step and the second algorithm executing step are combined to calculate the optimum value of a parameter utilized upon executing the local layout unbalance reducing algorithm, whereby non-uniformity in density of the plurality of elements staying in the initial layout is reduced.
In the first algorithm executing step, the parameter used for executing the local layout unbalance reducing algorithm can be expressed as a gene, and a chromosome comprising the sequence of the gene is used as a candidate solution for a problem of determining the parameter, thereby effecting the genetic algorithm.
In the second algorithm executing step, when the space within which the plurality of elements are arranged is divided into a plurality of sub-divided spaces, the parameter comprises information for specifying the sizes of the sub-divided spaces.
At this time, when the genetic algorithm is executed, a weighted average between genes of two parent chromosomes can be taken as a gene of a child chromosome in the first algorithm executing step, thereby effecting crossover as a genetic operation.
In the first algorithm executing step, when the genetic algorithm is executed, a portion of the chromosome may be pasted to a counterpart portion of another chromosome while the total sum of data for sp
Sasagawa Fumiyoshi
Shinagawa Akio
Fujitsu Limited
Garbowski Leigh Marie
Smith Matthew
Staas & Halsey , LLP
LandOfFree
Method for solving a layout optimization problem, and... 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 solving a layout optimization problem, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for solving a layout optimization problem, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2950340