Element placement method and apparatus

• US 5,465,218 A
• Filed: 02/10/1994
• Issued: 11/07/1995
• Est. Priority Date: 02/12/1993
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Handa, Keiichi
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US08/194,389
• Time in Patent Office: 635 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

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, the method including 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, thereby generating an element placement result including placement coordinate data of all elements included in the partial circuit data.

Claims

1. 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.

2. 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.

3. 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.

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, 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.

5. A method according to any one of claims 1-4, wherein said element placement step includes a population of initial solutions generation step of using the branch data extracted in the extraction step and said overlapping data to generate a population of solutions including a plurality of solutions constituted by candidate values for predetermined first coordinates of all elements included in the branch data,

a second coordinate determination step of determining second coordinates perpendicular to the first coordinates of all elements associated with the population of solutions in units of solutions by using a compaction method,

a fitness evaluation step of evaluating a fitness of each solution for which the second coordinate has been determined,

a population of new solutions generation step of generating a population of new solutions by performing predetermined processing on the basis of the evaluation of each fitness,

a step of repeating the second coordinate determination step to a population of new solutions step a predetermined number of times, and

an optimal solution selection step of evaluating fitness with respect to a population of new solutions, selecting a solution having the best fitness from the population of solutions, and outputting an element placement result associated with said branches extracted in said partial circuit extracting step and said overlapping data.

6. 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.

7. 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.

8. A method according to any one of claims 1-4, wherein

said element placement step includes

a population of solutions generation step of using the branch data extracted in said partial circuit extraction step and said overlapping data to generate a population of solutions including a plurality of solutions constituted by candidate values for predetermined first coordinates of all elements included in the branch data,

a second coordinate determination step of determining second coordinates perpendicular to the first coordinates of all elements associated with the population of solutions in units of solutions by a compaction operation,

a search step of searching a pair of elements for each solution of the population of solutions, of elements included in the adjacent branches, which have the first coordinates which are close to each other, in accordance with a predetermined probability, and

an adjustment step of, when a pair of elements which are close to each other are found, adjusting first coordinate values of the elements to be equal to each other.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. An apparatus according to any one of claims 17-20, wherein

said element placement means includes

a population of initial solutions generation means for using the branch data extracted by said partial circuit data extraction means and said overlapping data to generate a population of solutions including a plurality of solutions constituted by candidate values for predetermined first coordinates of all elements included in the branch data,

second coordinate determination means for determining second coordinates perpendicular to the first coordinates of all elements associated with the population of solutions in units of solutions,

fitness evaluation means for evaluating a fitness of each solution for which the second coordinate has been determined, and

near-optimal solution selection means for selecting a solution having the best fitness from a population of solutions, and outputting an element placement result associated with branches included in the circuit diagram.

22. 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.

23. 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.

24. An apparatus according to any one of claims 17-20, wherein

said element placement means includes

a population of solutions generation means for using the branch data extracted by said partial circuit data extraction means and said overlapping data to generate a population of solutions including a plurality of solutions constituted by candidate values for predetermined first coordinates of all elements included in the branch data,

second coordinate determination means for determining second coordinates perpendicular to the first coordinates of all elements associated with the population of solutions in units of solutions by a compaction operation,

search means for searching a pair of elements for each solution of the population of solutions, of elements included in the adjacent branches, which have the first coordinates which are close to each other, in accordance with a predetermined probability, and adjustment means for, when a pair of elements which are close to each other are found, adjusting first coordinate values of the elements to be equal to each other.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.