Title | ||
---|---|---|
An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers |
Abstract | ||
---|---|---|
With nearest neighbor load balancing algorithms, a processor makes balancing decisions based on its local information and manages work load migrations within its neighborhood. This paper compares a couple of fairly well-known nearest neighbor algorithms, the dimension exchange and the diffusion methods and their variants in terms of their performances in both one-port and all-port communication architectures. It turns out that the dimension exchange method outperforms the diffusion method in the one-port communication model, and that the strength of the diffusion method is in asynchronous implementations in the all-port communication model. The underlying communication networks considered assume the most popular topologies, the mesh and the torus and their special cases: the hypercube and the k-ary n-cube. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1109/IPPS.1995.395973 | IPPS |
Keywords | Field | DocType |
computer architecture,hypercube,nearest neighbor,approximation algorithms,bandwidth,load balancing,concurrent computing,computer networks,parallel computer,communication networks,load balance,resource allocation,torus,algorithm design and analysis | k-nearest neighbors algorithm,Asynchronous communication,Telecommunications network,Load balancing (computing),Computer science,Parallel computing,Algorithm,Network topology,Models of communication,Resource allocation,Hypercube | Conference |
ISBN | Citations | PageRank |
0-8186-7074-6 | 22 | 1.67 |
References | Authors | |
11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Z. Chen | 1 | 3443 | 271.62 |
Burkhard Monien | 2 | 2199 | 279.35 |
Reinhard Lüling | 3 | 313 | 35.55 |
Francis C. M. Lau | 4 | 395 | 40.86 |