Element placement method and apparatus

Claim 2

An LSI element placement method of placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, said method comprising the steps of: a partial circuit extraction step of sequentially extracting data of a predetermined number of branches included in the circuit diagram from the first terminal side of the circuit diagram so as to overlap the data by a predetermined number; and an element placement step of performing an element placement operation based on a genetic algorithm in the extracted partial circuit data and said overlapping data, thereby generating an element placement result including placement coordinate data of all elements included in the partial circuit data.

Claim 3

A method according to claim 1, further comprising a file generation step of generating a placement result file on the basis of the element placement result.

Claim 4

A method according to claim 2, further comprising a set step of presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer m, wherein said partial circuit extraction step includes a step of, when the branch data are to be extracted for the first time, continuously extracting m branch data from the first terminal to the second terminal of the circuit diagram, a step of, when the branch data are to be extracted for the second and subsequent times, continuously extracting m branch data including branch data extracted in an immediately preceding extraction step except for n branch data from the first terminal, and a step of extracting all data when the number of branch data is less than m in a last extraction step, and said file generation stop includes a step of recording an element placement result associated with elements included in n continuous branch data located closest to the first terminal, of branch data included in the element placement result generated by the element placement step, and a step of recording an element placement result associated with all elements included in a last element placement result generated by the element placement step.

Claim 5

A method according to claim 2, further comprising a set step of presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer m, wherein said partial circuit extraction step includes a step of, when the branch data are to be extracted for the first time continuously extracting m branch data from the first terminal to the second terminal of the circuit diagram, a step of, when the branch data are to be extracted for the second and subsequent times, extracting n branch data from the first terminal side of branch data extracted in an immediately preceding extraction step, a step of extracting all data when the number of branch data is less than n in a last extraction operation, and said file generation step includes a step of recording an element placement result associated with elements included in n continuous branch data located closest to the first terminal, of branch data included in the element placement result generated by the element placement step, and a step of recording an element placement result associated with all elements included in a last element placement result generated by the element placement step.

Claim 7

A method according to claim 5, wherein said population of new solutions generation step includes a selection step of selecting two solutions on the basis of the evaluated fitness of the population of solutions, a crossover step of exchanging a predetermined number of components between the two selected solutions, and a mutation step of performing a predetermined arithmetic operation with respect to a predetermined number of components of the solutions for which the exchange has been performed.

Claim 8

A method according to claim 5, wherein the population of initial solutions generation step includes the step of generating a population of solutions by receiving and inheriting values of the first coordinates of elements associated with the partial circuit data, without any modification, which elements are common to elements in the partial circuit data used for an immediately preceding element placement operation, of the partial circuit data extracted in the partial circuit extraction step.

Claim 10

A method according to claim 8, wherein said adjustment step includes a step of holding the values of the adjusted first coordinates until adjustment of first coordinates is performed with respect to a population of new solutions.

Claim 11

A method according to claim 6, wherein said element placement step includes a step of setting a sequence of numbers, as the solutions, obtained by arranging and coding candidate values for first coordinates corresponding to each element included in the partial circuit as the placement target in accordance with an order in which branches are arranged from the first terminal and an order in which elements in each branch are arranged, said selection step includes a step of selecting two solutions in accordance with probabilities determined on the basis of fitness associated with the solutions in units of solutions, said crossover step includes a step of performing exchange of the components in accordance with crossover ratios determined on the basis of an order in which branches are newly added to the partial circuit as the placement target in the extraction step in units of branches, and said mutation step includes a step of performing the predetermined arithmetic operation in accordance with mutation ratios determined on the basis of the order in units of branches.

Claim 12

A method according to claim 1, wherein said element placement stop includes a selection step of selecting a predetermined number of solutions of the next population from the present population consisting of the predetermined number of solutions, said selection step including an evaluation step of evaluating a plurality of costs including at least a first cost associated with an element placement area in units of the first solutions and a second cost associated with a positional relationship between elements, a first generation step of calculating a selection probability of each of the first solutions by using a predetermined function on the basis of the first cost to select a plurality of second solutions larger in number than a predetermined number from a population of first solutions, and generating a population of second solutions including the second solutions, a second generation step of calculating a selection probability of each of the second solutions by using a predetermined function on the basis of the second cost to select a plurality of third solutions larger in number than the first solutions and smaller in number than the second solutions from the population of second solutions, and generating a population of third solutions including the third solutions, and a third generation step of repeating the second generation step until a population of final solutions are generated with reference to all costs.

Claim 13

A method according to claim 11, wherein said element placement step includes a second coordinate determination step of determining second coordinates of all elements associated with the population of first solutions in units of the first solutions prior to execution of the evaluation step, a crossover step of selectively forming solution pairs equal to half the number of solutions included in the population of last solutions after execution of the third generation step, and exchanging components between solutions constituting each of the solution pairs, a mutation step of performing a predetermined arithmetic operation with respect to a predetermined component of each of the solutions which have undergone the exchange to generate a population of new solutions, and a step of repeating said second coordinate determination step to said mutation step, a predetermined number of times, with respect to a population of new solutions generated in the mutation step.

Claim 14

A method according to any one of claim 11 or claim 12, wherein said evaluation step includes a step of evaluating a cost associated with adjacency of elements, a cost associated with an element area, and a cost associated with a wire length.

Claim 15

A method according to claim 8 or 12, wherein said second coordinate determination step includes a step of determining a second coordinate of each element associated with the solution by a compaction operation.

Claim 16

An LSI element placement method of placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, comprising: a division step of dividing the circuit diagram into a plurality of partial circuits, each constituted by a plurality of branches; and a parallel processing step of simultaneously applying genetic algorithms to element placement of the respective partial circuits, wherein said parallel processing step includes a step of obtaining fitness used for the genetic algorithms with respect to the respective partial circuits with reference to information about a connection relationship between elements of each partial circuit as a placement target, and information about a placement result based on a best solution every predetermined number of generations of the immediately left partial circuit as a placement target.

Claim 17

An LSI element placement method of placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, comprising: a division step of dividing the circuit diagram into a plurality of partial circuits, each constituted by a plurality of branches; and a parallel processing step of simultaneously applying genetic algorithms to element placement of the respective partial circuits, wherein said parallel processing step includes a step of obtaining fitness used for the genetic algorithms with respect to the respective partial circuits with reference to information about a connection relationship between elements of each partial circuit as a placement target, and information about a placement result based on a best solution every predetermined number of generations of the immediately left partial circuit as a placement target.

Claim 18

A method according to claim 15, wherein said parallel processing step includes a step of arranging and coding first coordinates by using a genetic algorithm applied to each of the partial circuits as the placement targets, in units of branches, in accordance with an order in which elements are arranged, and a step of determining a second coordinate of each element which is perpendicular to the first coordinate by performing a compaction operation with respect to a placement result based on a best solution determined every predetermined number of generations of an immediately preceding partial circuit as a placement target.

Claim 19

An LSI element placement apparatus for placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, said apparatus comprising: partial circuit data extraction means for sequentially extracting data of a predetermined number of branches included in the circuit diagram from a first terminal side of the circuit diagram so as to overlap the data by a predetermined number; and element placement means for performing an element placement operation based on a genetic algorithm in the partial circuit data extracted by said partial circuit data extraction means and said overlapping data, thereby generating an element placement result including placement coordinate data of all elements included in the partial circuit data.

Claim 20

An LSI element placement apparatus for placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, said apparatus comprising: partial circuit data extraction means for sequentially extracting data of a predetermined number of branches included in the circuit diagram from a first terminal side of the circuit diagram so as to overlap the data by a predetermined number; and element placement means for performing an element placement operation based on a genetic algorithm in the partial circuit data extracted by said partial circuit data extraction means and said overlapping data, thereby generating an element placement result including placement coordinate data of all elements included in the partial circuit data.

Claim 21

An apparatus according to claim 17, further comprising placement result file generation means for generating a placement result file on the basis of the element placement result obtained by said element placement means.

Claim 22

An apparatus according to claim 18, further comprising set means for presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer, wherein said partial circuit data extraction means includes means for, when the branch data are to be extracted for the first time, continuously extracting m branch data from the first terminal to the second terminal of the circuit diagram, means for, when the branch data are to be extracted for the second and subsequent times, continuously extracting m branch data including branch data extracted in an immediately preceding extraction operation except for n branch data from the first terminal, and means for extracting all data when the number of branch data is less than m in a last extraction operation, and said placement result file generation means includes means for recording only an element placement result associated with elements included in n continuous branch data located closest to the first terminal, of branch data included in the element placement result generated by said element placement means, and means for recording an element placement result associated with all elements included in a last element placement result generated by said element placement means.

Claim 23

An apparatus according to claim 18, further comprising set means for presetting a predetermined first positive integer m and a second positive integer n smaller than the first positive integer, wherein said partial circuit data extraction means includes means for, when the branch data are to be extracted for the first time, continuously extracting m branch data from the first terminal to the second terminal of the circuit diagram, means for, when the branch data are to be extracted for the second and subsequent times, extracting n branch data from the first terminal side of branch data extracted in an immediately preceding extraction operation, means for extracting all data when the number of branch data is less than n in a last extraction operation, and said placement result file generation means includes means for recording only an element placement result associated with elements included in n continuous branch data located closest to the first terminal, of branch data included in the element placement result generated by said element placement means, and means for recording an element placement result associated with all elements included in a last element placement result generated by said element placement means.

Claim 25

An apparatus according to claim 21, wherein said population of new solutions generation means includes selection means for selecting two solutions on the basis of the evaluated fitnesses of the population of solutions, crossover means for exchanging a predetermined number of components between the two selected solutions, and mutation means for performing a predetermined arithmetic operation with respect to a predetermined number of components of the solutions for which the exchange has been performed.

Claim 26

An apparatus according to claim 21, wherein said population of initial solutions generation means includes means for generating a population of solutions by receiving and succeeding a value of the first coordinate of an element associated with branch data, without any modification, which element is common to an element associated with branch data, used for an immediately preceding element placement operation, of the branch data extracted by said partial circuit data extraction means.

Claim 28

An apparatus according to claim 24, wherein said adjustment means includes means for holding the values of the adjusted first coordinates until adjustment of first coordinates is performed with respect to a population of new solutions.

Claim 29

An apparatus according to claim 17, wherein said element placement means includes means for setting a sequence of numbers, as the solutions, obtained by arranging and coding candidate values for the first coordinates corresponding to elements included in the partial circuit as the placement target in accordance with an order in which branches are arranged from the first terminal and an order in which elements in each branch are arranged, said selection means includes means for performing an operation in accordance with probabilities determined on the basis of fitness associated with the solutions in units of solutions, said crossover means includes means for performing an operation in accordance with crossover ratios determined on the basis of an order in which branches are newly added to the partial circuit as the placement target by said partial circuit data extraction means in units of branches, and said mutation means includes means for performing an operation in accordance with mutation ratios determined on the basis of the order in units of branches.

Claim 30

An apparatus according to claim 17, wherein said element placement means includes selection means for selecting a predetermined number of solutions of the next population from the population consisting of the predetermined number of solutions, said selection means including evaluation means for evaluating a plurality of costs including at least a first cost associated with an element placement area and a second cost associated with a positional relationship between elements in units of the first solutions, first generation means for calculating a selection probability of each of the first solutions by using a predetermined function on the basis of the first cost to select a plurality of second solutions larger in number than a predetermined number from the population of first solutions and generating a population of second solutions including the second solutions, second generation means for calculating a selection probability of each of the second solutions by using a predetermined function on the basis of the second cost to select a plurality of third solutions larger in number than the first solutions and smaller in number than the second solutions from the population of second solutions, and generating a population of third solutions including the third solutions, and means for repeatedly operating said second generation means until a population of final solutions are generated with reference to all costs.

Claim 31

An apparatus according to claim 27, wherein said element placement means includes second coordinate determination means for determining second coordinates of all elements associated with the population of first solutions in units of the first solutions by a compaction operation prior to execution of an operation of said evaluation means, crossover means for selectively forming solution pairs equal to half the number of solutions included in the population of last solutions after execution of an operation of said third generation means, and exchanging components between solutions constituting each of the solution pairs, mutation means for performing a predetermined arithmetic operation with respect to a predetermined component of each of the solutions which have undergone the exchange to generate a population of new solutions, and means for repeating operations of the second coordinate determination means to said mutation means, a predetermined number of times, with respect to a population of new solutions generated by said mutation means.

Claim 32

An apparatus according to claim 27 or 28, wherein said evaluation means includes means for evaluating a cost associated with adjacency of elements, a cost associated with an element area, and a cost associated with a wire length.

Claim 33

An apparatus according to claim 21, wherein said second coordinate determination means includes means for determining a second coordinate of each element associated with the solution by a compaction operation.

Claim 34

An apparatus according to claim 19 or 20, further comprising means for setting the first and second positive integers m and n, set by said set means, as values which locally vary.

Claim 35

An LSI element placement apparatus for placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, comprising: means for dividing the circuit diagram into a plurality of partial circuits, each constituted by a plurality of branches; and processing means for simultaneously applying genetic algorithms to element placement of the respective partial circuits, wherein said processing means includes means for obtaining fitness used for the genetic algorithms with respect to the respective partial circuits with reference to information about a connection relationship between elements of each partial circuit as a placement target, and information about a placement result based on a best solution every predetermined number of generations of the immediately left partial circuit as a placement target.

Claim 36

An LSI element placement apparatus for placing elements in accordance with an order in which branches are arranged, each branch being constituted by an element array included in a circuit diagram having first and second terminals, comprising: means for dividing the circuit diagram into a plurality of partial circuits, each constituted by a plurality of branches; and processing means for simultaneously applying genetic algorithms to element placement of the respective partial circuits, wherein said processing means includes means for obtaining fitness used for the genetic algorithms with respect to the respective partial circuits with reference to information about a connection relationship between elements of each partial circuit as a placement target, and information about a placement result based on a best solution every predetermined number of generations of the immediately left partial circuit as a placement target.

Claim 37

An apparatus according to claim 32, wherein said processing means includes means for arranging and coding first coordinates by using a genetic algorithm applied to each of the partial circuits as the placement targets, in units of branches, in accordance with an order in which elements are arranged, and means for determining a second coordinate of each element which is perpendicular to the first coordinate by performing a compaction operation with respect to a placement result based on a best solution determined every predetermined number of generations of an immediately preceding partial circuit as a placement target.