Multidimensional spectral load balancing

Details Multidimensional spectral load balancing Multidimensional spectral load balancing

1996-07-15

1996-12-24

Trans, Vincent N.

Boots, shoes, and leggings

395800, G06F 1516, G06F 1750

Patent

active

055879225

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.

REFERENCES:
patent: 4577276 (1986-03-01), Dunlop et al.
Suaris, Peter R., "An Algorithm for Quadrisection and Its Application to Standard Cell Placement," IEEE Transactions on Circuits and Systems, vol. 35, No. 3, pp. 294-302 (1988).
Tokuyama, Takeshi, et al, "Geometric Algorithms for a Minimum Cost Assignment Problem," IBM Research, Tokyo Research Laboratory, pp. 262-271 (1991).
Rendl, Franz, et al, "A Projection Technique for Partioning the Nodes of a Graph," Research Report, Cor 9020, (Nov. 1990).
Mohar, Bojan, "Laplace Eigenvalues of Graphs--A Survey," Discrete Mathematics, vol. 109, pp. 171-183 (1992).
Kernigham, B. W., et al, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, pp. 291-307 (1970).
Hammond, Steven W., "Mapping Unstructured Grid Computations to Massively Parallel Computers," Research Institute for Advanced Computer Science (NASA Ames Research Center), Technical Report 92.14 (Jun. 1992).
Mohar, Bojan, "The LaPlacian Spectrum of Graphs," Intl. Conference on Theorp, Application of Graphs, Kalamazoo, MI (1988).
Simon, Horst D., "Partitioning of Unstructured Problems for Parallel Processing," NASA Ames Research Center, Report PNR-91-008 (Feb. 1991).
Hendrickson, Bruce, et al, "Multidimensional Spectral Load Balancing," Sandia National Laboratories Report, SAND93-0074-UC-405 (Jan. 1993).
Hendrickson, Bruce, et al, "An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations," Sandia National Laboratories Report, SAND92-1460-UC-405 (Sep. 1992).

Affiliated with

Also associated with

Rating

Multidimensional spectral load balancing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multidimensional spectral load balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multidimensional spectral load balancing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1183143