Multidimensional spectral load balancing
First Claim
Patent Images
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 2k 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 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 2k 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. - View Dependent Claims (3)
-
-
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 2k 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. - View Dependent Claims (5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13)
-
Specification