×

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

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×