Optimal parameters for load balancing using the diffusion method in k- ary n-cube network

DOI10.1016/0020-0190(93)90030-DMaRDI QIDQ689618zbMATH OpenOpenAlexFDO

Authors F. C. M. Lau, Cheng-Zhong Xu

Publication date 15 November 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90030-d

zbMATH Keywords

diffusion methoddistributed schedulingload balancingparallel processing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Review text

The diffusion method is a simple but practical method for dynamic load balancing in distributed memory message-passing multiprocessors. It is iterative in nature and is fully distributed. Its efficiency depends on a parameter, the diffusion parameter, which dictates how excess workloads are to be diffused away. We derive optimal values for this parameter for the cases of the \(k\)-ary \(n\)-cube and its variant, the \(n\)-dimensional torus. With these optimal paarameters, the diffusion method is guaranteed to terminate at a balanced state in optimal time.

Recommendations

• scientific article; zbMATH DE number 2087984
• An improved diffusion algorithm for dynamic load balancing.
• scientific article; zbMATH DE number 967422
• A Scalable Diffusion Algorithm for Dynamic Mapping and Load Balancing on Networks of Arbitrary Topology
• Analysis of the generalized dimension exchange method for dynamic load balancing

Cites work

• Analysis of the generalized dimension exchange method for dynamic load balancing
• Convergence and asymptotic agreement in distributed decision problems
• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)

Cited in

(7)

• Analysis of the generalized dimension exchange method for dynamic load balancing
• Determination of the parameters in the dynamic weighted round-robin method for network load balancing
• The move-to-partner rule for self-organizing task allocation on a linear array
• scientific article; zbMATH DE number 2087984 (Why is no real title available?)
• THE LIQUID MODEL LOAD BALANCING METHOD
• The influence of graph structure on generalized dimension exchange
• Convergence of the diffusion method for weighted torus graphs using Fourier analysis

This page was built for publication: Optimal parameters for load balancing using the diffusion method in \(k\)- ary \(n\)-cube network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q689618)