Multidimensional spectral load balancing

• US 5,587,922 A
• Filed: 07/15/1996
• Issued: 12/24/1996
• Est. Priority Date: 06/16/1993
• Status: Expired due to Fees

• Current Assignee: Sandia Corporation (Martin Marietta Corporation)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Leland, Robert W., Hendrickson, Bruce A.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/680,718
• Time in Patent Office: 162 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/800
• US Class Current: 716/124
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method of and apparatus for graph partitioning involving the use of a plurality of eigenvectors of the Laplacian matrix of the graph of the problem for which load balancing is desired. The invention is particularly useful for optimizing parallel computer processing of a problem and for minimizing total pathway lengths of integrated circuits in the design stage.

Claims

1. A parallel computational system optimized to solve a given problem, comprising:

a) a plurality of computational units;

b) data links connecting pairs of said computational units, said datalinks defining the connection topology of said parallel computational system, and;

c) a procedure to subdivide the given problem among the plurality of computation units, said procedure comprising;

i) constructing a graph corresponding to the given problem, said graph comprising a plurality of vertices representing a corresponding plurality of computational subtasks of the given problem, and a plurality of weighted edges representing information flow between the computational subtasks;

ii) generating a Laplacian matrix of said graph;

iii) computing k eigenvectors of said Laplacian matrix, k being an integer greater than 1;

iv) selecting an orthogonal basis for a space spanned by the eigenvectors;

v) partitioning said computational subtasks into 2^k subsets by means of the orthogonal basis, and;

vi) assigning each of said subsets of computational subtasks to at least one of said computational units in a manner consistent with the connection topology.

2. A method to design a circuit board which optimizes the interconnections between circuit elements within a given logical circuit structure, the method comprising the steps of:

a) constructing a graph representing the given logical circuit structure, said graph comprising a plurality of vertices representing the circuit elements, and a plurality of edges representing connections between said circuit elements;

b) subdividing the given logical circuit structure among a set of at least four subcircuits, said subdivision comprising;

i) generating a Laplacian matrix of the graph;

ii) computing k eigenvectors of said Laplacian matrix, k being an integer greater than 1;

iii) selecting an orthogonal basis for a space spanned by the eigenvectors;

iv) partitioning vertices of the graph into at least four subsets by means of the orthogonal basis;

v) assigning each of said subsets c,f vertices to at least one of said subcircuits, and;

c) designing and constructing a circuit board to implement said subdivision.

3. A circuit manufactured according to the method of claim 2.

4. A method of controlling a parallel computer for efficient operation on a task,

a) where the parallel computer comprises a plurality of processing elements and a plurality of communication links connecting the processing elements in a connection topology, and

b) where the task is divided into a plurality of subtasks, where each subtask communicates information to one or more other subtasks,

c) said method comprising:

i) constructing a graph corresponding to the task and comprising a plurality of vertices representing the subtasks and a plurality of weighted edges representing information communicated between subtasks;

ii) generating a Laplacian matrix of the graph;

iii) determining k eigenvectors of the Laplacian matrix, where k is an integer greater than 1;

iv) selecting an orthogonal basis for a space spanned by the eigenvectors;

v) partitioning the subtasks into 2^k subsets by means of the orthogonal basis; and

vi) assigning each of the subtasks to at least one of the processing elements consistent with the connection topology.

5. The method of claim 4 wherein step c iii) comprises computing eigenvectors λ

₂ through λ

_k+1 of the Laplacian matrix, where λ

_k+1 ≧

λ

_k and 4≧

k≧

2.

6. The method of claim 4 where the steps contained within step c are performed recursively.

7. The method of claim 6 wherein step c additionally comprises the step of determining if the graph is disconnected.

8. The method of claim 7 wherein step c additionally comprises the step of adding to the graph one or more edges to render the graph connected.

9. A method of placing a plurality of circuit elements of a logical circuit structure on a substrate so that the cost of connections between the elements is minimized, comprising:

a) constructing a graph representing the logical circuit structure, comprising a plurality of vertices representing the elements and a plurality of edges representing connections between the elements;

b) generating a Laplacian matrix of the graph;

c) determining k eigenvectors of the Laplacian matrix, where k is an integer greater than 1;

d) selecting an orthogonal basis for a space spanned by the eigenvectors;

e) partitioning the vertices of the graph into at least four subsets by means of the orthogonal basis;

f) assigning each of the subsets to at least one subcircuit;

g) assigning the subcircuits to regions of the substrate;

h) determining each element'"'"'s corresponding subcircuit; and

i) placing the elements on the substrate in regions assigned to their corresponding subcircuit.

10. The method of claim 9 wherein step c comprises computing eigenvectors λ

₂ through λ

_k+1 of the Laplacian matrix, where λ

_k ≦

λ

_k+1 and 2≦

k≦

4.

11. The method of claim 9 wherein steps a through f are performed recursively.

12. The method of claim 11 additionally comprising the step of determining whether the graph is disconnected.

13. The method of claim 12 additionally comprising the step of adding to the graph one or more edges to render the graph connected.