Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-05-20
2004-01-06
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C716S030000, C716S030000
Reexamination Certificate
active
06675155
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an arrangement optimization problem processing method and an arrangement optimization problem processing apparatus as well as a computer-readable recording medium on which an arrangement optimization problem processing program is recorded, suitable for use, for example, to process a circuit arrangement optimization problem for arranging circuits in an optimum condition on a large scale integrated circuit (LSI), more generally a node arrangement optimization problem (or element arrangement optimization problem) for arranging a plurality of nodes (or elements) in an optimum condition in a two- or more-dimensional space.
2. Description of the Related Art
A node arrangement optimum problem particularly is a problem for arranging (mapping) a plurality of nodes, whose connection relationships are indicated in a system space, in an optimum condition in a generation space, and is called graph mapping problem.
First, connection relationships of a plurality of nodes in a system space are shown in FIG.
22
. Referring to
FIG. 22
, reference symbols
130
a
to
130
h
denote fixed nodes whose arrangement in a generation space is determined already, and reference numerals
100
to
102
,
110
,
111
and
120
to
122
denote non-fixed nodes whose optimum arrangement in the generation space is to be determined. Further, reference numeral
1000
denotes the system space.
In the system space
1000
, connection relationships between the plurality of nodes are given as a graph
1001
. In the graph
1001
, the nodes
130
a
to
130
h,
100
to
102
,
110
,
111
and
120
to
122
are regarded as vertices, and the connection relationships (indicated by double-sided arrow marks in
FIG. 22
) between the nodes are regarded as sides between the vertices. It is to be noted that the coupling strength between each two nodes is indicated by the thickness of the pertaining double-sided arrow mark.
When it is tried to arrange the plurality of non-fixed nodes
100
to
102
,
110
,
111
and
120
to
122
in the generation space, the following constraints are taken into consideration:
i) Magnitudes of the Nodes in the Generation Space
Each of the nodes has a peculiar magnitude.
ii) Connection Relationships of a Plurality of Nodes in the System Space
Connection relationships between a plurality of nodes are given as a graph
1001
. Further, a certain node is connected to a fixed node.
Then, by executing, for example, a genetic algorithm as an algorithm for solution to an optimization problem while the constraints described above are taken into consideration, optimum arrangement of the plurality of nodes
100
to
102
,
110
,
111
and
120
to
122
in the generation space is determined, and based on the determination, the plurality of nodes
100
to
102
,
110
,
111
and
120
to
122
are arranged in the generation space.
It is to be noted that a genetic algorithm is an algorithm devised based on a concept of the principle of evolution of organisms. In the genetic algorithm, candidates for a solution to an arrangement optimization problem are represented as chromosomes which are arrangements of genes, and various genetic operations (selection/self-reproduction, mutation and crossover) are performed for the chromosomes to update the generation to determine an optimum solution given as a gene arrangement of a chromosome having a high fitness value (that is, an optimum arrangement of the plurality of nodes
100
to
102
,
110
,
111
and
120
to
122
in the generation space).
An example of a result of arrangement of the plurality of nodes
100
to
102
,
110
,
111
and
120
to
122
in the generation space is shown in FIG.
23
.
Generally, the generation space is a two- or more-dimensional space, and each node may have an arbitrary shape in accordance with the dimensions of the generation space. Referring to
FIG. 23
, the generation space
2000
shown has a rectangular shape, and the nodes (non-fixed nodes
100
to
102
,
110
,
111
and
120
to
122
shown in
FIG. 22
) have shapes defined to rectangles and arranged in the generation space
2000
. It is to be noted that, also in
FIG. 23
, reference symbols
130
a
to
130
h
denote fixed nodes whose arrangement in the generation space is determined already.
By executing a genetic algorithm to process a node arrangement optimization problem in this manner, an optimum arrangement of a plurality of nodes in an actual space in which only connection relationships are indicated is obtained.
In regard to, for example, an LSI mentioned above, if an optimum arrangement of circuits on the LSI can be determined, then not only minimization of the LSI can be achieved, but also minimization in length of wiring lines for interconnecting the circuits can be achieved to augment the wiring facility. Consequently, higher speed processing in the LSI can be achieved.
However, there is a subject to be solved in that, where a genetic algorithm is employed as an optimization problem solution algorithm which is used to process a node arrangement optimization problem, when the scale of the optimization problem is large, that is, when the number of nodes whose optimum arrangement is to be determined is very large, very much time is required to determine an optimum arrangement of the nodes.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an arrangement optimization problem processing method and apparatus by which an optimum arrangement of a plurality of nodes can be determined at a high speed even where a node arrangement optimization problem having a large problem scale is to be processed and a computer-readable recording medium on which an arrangement optimization problem processing program for causing a computer to operate to process a node arrangement optimization problem is recorded.
In order to attain the object described above, according to an aspect of the present invention, there is provided an arrangement optimization problem processing method for arranging a plurality of nodes, whose connection relationships are indicated in a system space, in a generation space, comprising a hyper node formation step of grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of nodes, a hyper node arrangement step of executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by the hyper node formation step in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions, and a node optimum arrangement step of executing the optimization problem solution algorithm taking arrangement relationships of the plurality of hyper nodes obtained by the hyper node arrangement step into consideration to determine a solution to a problem of arrangement of the plurality of nodes in an optimum condition in the generation space and arranging the plurality of nodes in the generation space based on the determined solution.
The hyper node arrangement step may arrange the plurality of hyper nodes in the generation space taking a constraint in arrangement of the hyper nodes into consideration.
Further, the arrangement optimization problem processing method may be constructed such that each of the hyper nodes includes a plurality of sub hyper nodes each formed from a partial set of a plurality of nodes which form the hyper node, and the arrangement optimization problem processing method further comprise a constraint search step of determining the constraint to the hyper node based on the constraint to the sub hyper nodes.
The hyper node arrangement step may execute a genetic algorithm as the optimization problem solution algorithm to determine solutions to the problem of arrangement of the plurality of hyper nodes formed by the hyper node formation step in the generation space and arrange the plurality of hyper nodes in the generation space based on one of the determined solutions.
The hyper node arrange
Sasagawa Fumiyoshi
Shinagawa Akio
Davis George B.
Fujitsu Limited
LandOfFree
Layout method arranging nodes corresponding to LSI elements... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Layout method arranging nodes corresponding to LSI elements..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layout method arranging nodes corresponding to LSI elements... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3190583