Layout method arranging nodes corresponding to LSI elements having a connecting relationship

• US 6,675,155 B2
• Filed: 05/20/1998
• Issued: 01/06/2004
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shinagawa, Akio, Sasagawa, Fumiyoshi
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/081,604
• Publication Number:
  US 20020010692A1
• Time in Patent Office: 2,057 Days
• Field of Search: 706/13, 716/8, 716/9
• US Class Current: 706/13
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The invention provides an arrangement optimization problem processing apparatus for arranging a plurality of nodes in an optimum condition in a two- or more-dimensional space, 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. The arrangement optimization problem processing apparatus includes a hyper node formation section for grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of nodes, a hyper node arrangement section for 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 section in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions.

Claims

1. A layout operation for arranging a layout of a plurality of nodes in a generation space of a computer system, comprising:

a definition operation of defining each node as a geographical shape set by associated coordinates, wherein each node has a connection relationship to other nodes of the plurality of nodes;

a hyper node formation operation of forming a plurality of hyper nodes from sets of the nodes;

a hyper node arrangement operation of executing an optimization problem solution algorithm to determine a plurality of 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;

a node optimum arrangement operation, carried out after the hyper node arrangement step, of executing the optimization problem solution algorithm taking arrangement relationships between 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; and

an arrangement output operation of laying out the determined arrangement of the plurality of nodes as an arrangement of a plurality of geographical shapes, based upon the arrangement relationships between the plurality of the hyper nodes.

2. The layout operation as claimed in claim 1, wherein the hyper node arrangement operation arranges the plurality of hyper nodes in the generation space taking a constraint in arrangement of the hyper nodes into consideration.

3. The layout operation as claimed in claim 2, wherein 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 further comprising a constraint search operation of determining the constraint to the hyper node based on the constraint to the sub hyper nodes.

4. The layout operation as claimed in claim 1, wherein the hyper node arrangement operation executes 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 arranges the plurality of hyper nodes in the generation space based on one of the determined solutions.

5. The layout operation as claimed in claim 4, wherein the hyper node arrangement operation arranges the plurality of hyper nodes in the generation space based on an optimum one of the determined solutions.

6. The layout operation as claimed in claim 4, wherein the hyper node arrangement operation arranges the plurality of hyper nodes in the generation space based on one of the determined solutions other than an optimum solution.

7. The layout operation as claimed in claim 4, wherein, where the generation space has a rectangular shape, when the hyper node arrangement operation and the node optimum arrangement operation define shapes of the hyper nodes and the nodes to rectangles and arrange the hyper nodes and the nodes in the generation space, respectively, the hyper node arrangement operation and the node optimum arrangement operation represent the hyper nodes and the nodes as genes composed of information regarding center coordinates of the rectangles and information regarding aspect ratios of the rectangles and execute the genetic algorithm using chromosomes composed of arrangements of the genes as solution candidates to the problem of arrangement of the plurality of hyper nodes and the plurality of nodes in the generation space, respectively.

8. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, pasting crossover wherein information regarding the center coordinates of the rectangle of one of the genes which comprise one of the chromosomes and information regarding the aspect ratio of the rectangle are replaced with the center coordinate information and the aspect ratio information, respectively, of a corresponding one of the genes which comprise another one of the chromosomes is performed as a genetic operation for the chromosomes.

9. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, pasting crossover wherein information regarding the center coordinates of the rectangle of one of the genes which comprise one of the chromosomes is replaced with the center coordinate information of a corresponding one of the genes which comprise another one of the chromosomes is performed as a genetic operation for the chromosomes.

10. The layout operation as claimed in claim 9, wherein the pasting crossover is based on a weighted average of the information regarding the center coordinates of the rectangles.

11. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, pasting crossover wherein information regarding the aspect ratio of the rectangle of one of the genes which comprise one of the chromosomes is replaced with the aspect ratio information of a corresponding one of the genes which comprise another one of the chromosomes is performed as a genetic operation for the chromosomes.

12. The layout operation as claimed in claim 11, wherein the pasting crossover is based on a weighted average of the information regarding the aspect ratios of the rectangles.

13. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, mutation wherein the information regarding the aspect ratio of the rectangle of the gene which composes the chromosome is varied is performed as a genetic operation for the chromosome.

14. The layout operation as claimed in claim 13, wherein the mutation increases or decreases the information regarding the aspect ratio of the rectangle at a fixed ratio.

15. The layout operation as claimed in claim 14, wherein it is stochastically determined whether the information regarding the aspect ratio of the rectangle should be increased or decreased in the fixed ratio by the mutation.

16. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, mutation wherein the information regarding the center coordinates of the rectangle of the gene which comprises the chromosome is varied is performed as a genetic operation for the chromosome.

17. The layout operation as claimed in claim 16, wherein the mutation adds a stochastically selected value to the information regarding the center coordinates of the rectangle to vary the information regarding the center coordinates of the rectangle.

18. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome is calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space into consideration.

19. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome is calculated taking a sum total of areas of overlapping portions of the plurality of hyper nodes arranged in the generation space into consideration.

20. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome is calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space and a sum total of areas of overlapping portions of the plurality of hyper nodes into consideration.

21. The layout operation as claimed in claim 20, wherein the calculation of the fitness value is performed by performing weighted calculation for either one of a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes and a sum total of areas of overlapping portions of the plurality of hyper nodes.

22. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome is calculated taking a sum total of areas-of gap portions among the plurality of hyper nodes arranged in the generation space into consideration.

23. The layout operation as claimed in claim 7, wherein, when the genetic algorithm is executed, before selection as a genetic operation is performed for the chromosome, a fitness value of the chromosome is calculated taking a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes arranged in the generation space and a sum total of areas of gap portions among the plurality of hyper nodes into consideration.

24. The layout operation as claimed in claim 23, wherein the calculation of the fitness value is performed by performing weighted calculation for either one of a sum total of lengths of wiring lines for interconnecting the plurality of hyper nodes and a sum total of areas of gap portions among the plurality of hyper nodes.

25. The layout operation as claimed in claim 1, wherein the hyper node arrangement operation arranges the plurality of hyper nodes in the generation space based on an optimum one of the determined solutions.

26. The layout operation as claimed in claim 1, wherein the hyper node arrangement operation arranges the plurality of hyper nodes in the generation space based on one of the determined solutions other than an optimum solution.

27. The layout operation as claimed in claim 1, wherein, where the generation space is a two-dimensional space, the hyper node arrangement operation and the node optimum arrangement operation define shapes of the hyper nodes and the nodes as two-dimensional shapes and arrange the hyper nodes and the nodes in the generation space, respectively.

28. A layout operation for arranging a plurality of elements in a two- or more-dimensional space in a generation space of a computer system, comprising:

a definition operation of defining a plurality of elements for connection in an LSI (Large Scale Integrated Circuit) floorplan;

a hyper element formation operation of grouping the plurality of elements to form a plurality of hyper elements each formed from a set of the elements;

a hyper element arrangement operation of executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper elements formed by the hyper element formation operation in the generation space and arranging the plurality of hyper elements in the generation space based on one of the determined solutions; and

an element optimum arrangement operation, carried out after the hyper node arrangement step, of executing another optimization problem solution algorithm taking arrangement relationships between the plurality of hyper elements obtained by the hyper element arrangement operation into consideration to determine a solution to a problem of arrangement of the plurality of elements in an optimum condition in the generation space and arranging the plurality of elements in the generation space based on the determined solution; and

an arrangement output operation of laying out a determined arrangement of the plurality of nodes in as an arranged plurality of elements,

based upon the arrangement relationships between the plurality of the hyper elements.

29. A layout apparatus for arranging a layout of a plurality of nodes in a generation space of a computer system, comprising:

means for defining each of a plurality of nodes as a geographical shape set by associated coordinates, wherein each node has a connection relationship to other nodes of the plurality of nodes;

hyper node formation means for grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of the nodes;

hyper node arrangement means for executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by said hyper node formation means in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions; and

node optimum arrangement means for executing the optimization problem solution algorithm, after arranging the plurality of hyper nodes, taking arrangement relationships between the plurality of hyper nodes obtained by said hyper node arrangement means 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; and

an arrangement output means for laying out the determined arrangement of the plurality of nodes as an arrangement of a plurality of geographical shapes,

based upon the arrangement relationships between the plurality of the hyper nodes.

30. A computer-readable recording medium storing a layout program for causing a computer to layout a plurality of nodes in a generation space of a computer system, the program comprising:

a definition operation of defining each of a plurality of nodes as a geographical shape set by associated coordinates, wherein each node has a connection relationship to other nodes of the plurality of nodes;

a hyper node formation operation of grouping the plurality of nodes to form a plurality of hyper nodes each formed from a set of the nodes;

a hyper node arrangement operation of executing an optimization problem solution algorithm to determine solutions to a problem of arrangement of the plurality of hyper nodes formed by said hyper node formation operation in the generation space and arranging the plurality of hyper nodes in the generation space based on one of the determined solutions;

a node optimum arrangement operation, carried out after the hyper node arrangement operation, of executing the optimization problem solution algorithm taking arrangement relationships between the plurality of hyper nodes obtained by said hyper node arrangement operation 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; and

an arrangement output operation of laying out the determined arrangement of the plurality of nodes as an arrangement of a plurality of geographical shapes,

based upon the arrangement relationships between the plurality of the hyper nodes.

31. A layout method for arranging a layout of a multiplicity of nodes, whose interconnection relationship is previously determined, in a predetermined space, comprising:

(a) defining the multiplicity of nodes as a multiplicity of geographical shapes so that each of the multiplicity of nodes is associated with a respective one of the multiplicity of geographical shapes, and also defining a first optimization problem required to optimize a layout of the multiplicity of nodes in the predetermined space;

(b) grouping the multiplicity of the nodes to form a sub-multiplicity of hyper-nodes in a hierarchy of N+1 layers so that each of the hyper-nodes in any nth layer includes a plurality of hyper-nodes or nodes in any (n−

l)th layer, where N is a natural number more than one, the 0th layer is the top layer, the Nth layer is the bottom layer including the multiplicity of nodes, and n is a natural number between one and N inclusive;

(c) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-nodes, required to optimize a layout of the hyper-nodes in the 0th layer in the predetermined space, by executing an optimization-problem solution algorithm on the second optimization problem;

(d) repeatedly determining an optimum solution to a second optimization problem required to optimize a layout of the hyper-nodes in the mth layer in the predetermined space, where m is a natural number between one and N−

1 inclusive, with increasing the value of m by one beginning from one until m becomes N−

1, by executing an optimization-problem solution algorithm on the second optimization problem corresponding to the mth layer using the optimum solution to the second optimization problem corresponding to the (m−

1)th layer;

(e) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem corresponding to the (N−

l)th layer; and

(f) laying out the multiplicity of nodes in the predetermined space based on the determined optimum solution to the first optimization problem as the layout of the multiplicity of nodes.

32. A method for arranging a layout of a multiplicity of nodes, whose interconnection relationship is previously determined, in a predetermined space, comprising:

(a) defining the multiplicity of nodes as a multiplicity of geographical shapes so that each of the multiplicity of nodes is associated with a respective one of the multiplicity of geographical shapes, and also defining a first optimization problem required to optimize a layout of the multiplicity of nodes in the predetermined space;

(b) grouping the multiplicity of nodes to form a sub-multiplicity of hyper-nodes in a hierarchy of N+1 layers so that each of the hyper-nodes in any nth layer includes a plurality of hyper-nodes or nodes in any (n−

1)th layer, where N is a natural number more than one, the 0th layer is the top layer, the Nth layer is the bottom layer including the multiplicity of nodes, and n is a natural number between one and N inclusive;

(c) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-nodes, required to optimize a layout of the hyper-nodes in the 0th layer in the predetermined space, by executing an optimization-problem solution algorithm on the second optimization problem;

(d) repeatedly determining an optimum solution to a second optimization problem required to optimize a layout of the hyper-nodes in the mth layer in the predetermined space, where m is a natural number between one and N−

1 inclusive, with increasing the value of m by one beginning from one until m becomes N−

1, by executing an optimization-problem solution algorithm on the second optimization problem corresponding to the mth layer using the optimum solution to the second optimization problem corresponding to the (m−

l)th layer;

(e) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem corresponding to the (N−

l)th layer; and

(f) laying out the multiplicity of nodes in the predetermined space based on the determined optimum solution to the first optimization problem.

33. A layout method of determining an optimum solution to a first optimization problem required to optimize a layout of a multiplicity of nodes, whose interconnection relationship is previously determined, in a predetermined space so as to arrange a multiplicity of geographical shapes, each of which is associated with a respective one of the multiplicity of nodes, in the predetermined space based on the determined optimum solution to the first optimization problem, said method comprising the steps, carried out by a computer system, of:

(a) grouping the multiplicity of nodes to form a sub-multiplicity of hyper-nodes, each of said hyper-nodes including a plurality of nodes from the multiplicity of nodes;

(b) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-nodes, required to optimize a layout of said hyper-nodes formed in said step (a) in the predetermined space, by executing an optimization-problem solution algorithm on the second optimization problem; and

(c) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem determined in said step (b).

34. A layout method of determining an optimum solution to a first optimization problem required to optimize a layout of a multiplicity of elements in a two or more dimensional predetermined space to arrange the multiplicity of elements in the predetermined space based on the determined optimum solution to the first optimization problem, said method comprising the steps, carried out by a computer system, of:

(a) grouping the multiplicity of elements to form a sub-multiplicity of hyper-elements, each of said hyper-elements including a plurality of elements from the multiplicity of elements;

(b) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-elements, required to optimize a layout of said hyper-elements formed in said step (a) in the predetermined space, by executing an optimization problem solution algorithm on the second optimization problem; and

(c) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem determined in said step (b).

35. A computer-readable medium storing a layout program for determining an optimum solution to a first optimization problem required to optimize a layout of a multiplicity of elements in a two or more dimensional predetermined space to arrange the multiplicity of elements in the predetermined space based on the determined optimum solution to the first optimization problem, wherein said program instructs a computer to carry out the following functions of:

(a) grouping the multiplicity of elements to form a sub-multiplicity of hyper-elements, each of said hyper-elements including a plurality of elements from the multiplicity of elements;

(b) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-elements, required to optimize a layout of said hyper-elements formed in said function (a) in the predetermined space, by executing an optimization problem solution algorithm on the second optimization problem; and

(c) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem determined in said function (b).

36. A layout method of determining an optimum solution to a first optimization problem required to optimize a layout of a multiplicity of nodes, whose connection relationships are predetermined, in a predetermined space to arrange a multiplicity of geographical shape sets, each of which is associated with a respective one of the multiplicity of nodes, in the predetermined space based on the determined optimum solution to the first optimization problem, said method comprising the steps, carried out by a computer system, of:

(a) grouping the multiplicity of nodes to form a sub-multiplicity of hyper-nodes in a hierarchy of N+1 layers so that each of the hyper-nodes in any nth layer includes a plurality of hyper-nodes or nodes in any (n−

1)th layer, where N is a natural number more than one, the 0th layer is the top layer, the Nth layer is the bottom layer including the multiplicity of nodes, and n is a natural number between one and N inclusive;

(b) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-nodes, required to optimize a layout of the hyper-elements in the 0th layer in the predetermined space, by executing an optimization-problem solution algorithm on the second optimization problem;

(c) repeatedly determining an optimum solution to a second optimization problem required to optimize a layout of the hyper-elements in the mth layer in the predetermined space, where m is a natural number between one and N−

1 inclusive, with increasing the value of m by one beginning from one until m becomes N−

1, by executing an optimization-problem solution algorithm on the second optimization problem corresponding to the mth layer using the optimum solution to the second optimization problem corresponding to the (m−

l)th layer; and

(d) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem corresponding to the (N−

l)th layer.

37. A computer-readable medium storing a layout program for determining an optimum solution to a first optimization problem required to optimize a layout of a multiplicity of elements in a two or more dimensional predetermined space so as to arrange the multiplicity of elements in the predetermined space based on the determined optimum solution to the first optimization problem, wherein said program instructs a computer to carry out the following functions of:

(a) grouping the multiplicity of nodes to form a sub-multiplicity of hyper-nodes in a hierarchy of N+1 layers so that each of the hyper-nodes in any nth layer includes a plurality of hyper-nodes or nodes in any (n−

l)th layer, where N is a natural number more than one, the 0th layer is the top layer, the Nth layer is the bottom layer including the multiplicity of nodes, and n is a natural number between one and N inclusive;

(b) determining an optimum solution to a second optimization problem, based upon arrangement relationships between the hyper-nodes, required to optimize a layout of the hyper-elements in the 0th layer in the predetermined space, by executing an optimization-problem solution algorithm on the second optimization problem;

(c) repeatedly determining an optimum solution to a second optimization problem required to optimize a layout of the hyper-elements in the mth layer in the predetermined space, where m is a natural number between one and N−

1 inclusive, with increasing the value of m by one beginning from one until m becomes N−

1, by executing an optimization-problem solution algorithm on the second optimization problem corresponding to the mth layer using the optimum solution to the second optimization problem corresponding to the (m−

1)th layer; and

(d) determining the optimum solution to the first optimization problem by executing the optimization problem solution algorithm on the first optimization problem, using the optimum solution to the second optimization problem corresponding to the (N−

l)th layer.

38. A method of arranging a plurality of nodes in a generation space of a computer system, comprising:

forming a plurality of hyper nodes from the nodes; and

executing an optimization problem solution algorithm to determine a plurality of solutions to a problem of arrangement of the plurality of hyper nodes, based upon arrangement relationships between the hyper-nodes.

39. The method as claimed in claim 38, wherein the forming of the hyper nodes comprises forming hyper nodes of different hierarchies, wherein a connection relationship between the hyper nodes of a higher hierarchy is determined by a connection relationship of the hyper nodes of a lower hierarchy.

40. The method as claimed in claim 38, wherein the forming of the hyper nodes comprises forming hyper nodes of different hierarchies, wherein a coupling strength between the hyper nodes of a higher hierarchy is determined by a coupling strength of the hyper nodes of a lower hierarchy.