Multidimensional spectral load balancing

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

Claim 3

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.

Claim 4

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.

Claim 6

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.

Claim 7

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.

Claim 12

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.

Claim 13

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.