loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
9th International Parallel Processing Symposium
An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers
Santa Barbara, CA
April 25-April 28
ISBN: 0-8186-7074-6
Chengzhong Xu, Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
B. Monien, Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
R. Luling, Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
F.C.M. Lau, Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
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.
Index Terms:
resource allocation; parallel machines; multiprocessor interconnection networks; performance evaluation; nearest neighbor algorithms; load balancing; parallel computers; nearest neighbor load balancing; dimension exchange metho; mesh; torus; hypercube; k-ary n-cube; communication networks
Citation:
Chengzhong Xu, B. Monien, R. Luling, F.C.M. Lau, "An analytical comparison of nearest neighbor algorithms for load balancing in parallel computers," ipps, pp.472, 9th International Parallel Processing Symposium, 1995
Usage of this product signifies your acceptance of the Terms of Use.