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

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.

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.

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.

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.

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.

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

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

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

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.

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.