Diffusive load balancing schemes on heterogeneous networks

ABSTRACT

Up to now, diffusive load balancing schemes have only been developed for homogeneous networks. We generalize existing diffusion schemes, in order to deal with heterogeneous networks. In these networks, every processor can have arbitrary computing power, and the load has to be balanced proportionally to these weights. The balancing flow that is calculated by the schemes for homogeneous networks is minimal with regard to the l2-norm and we prove this to hold true for the generalized schemes, too. By means of a number of experiments we demonstrate the usability of the generalized schemes on heterogeneous networks.

REFERENCES

• 1: J. E. Boillat, Load balancing and Poisson equation in a graph, Concurrency: Practice and Experience, v.2 n.4, p.289-313, Dec. 1990 [doi>10.1002/cpe.4330020403]
• 2: J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, pages 195-199, 1970.
• 3: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 4: Thomas Decker , Burkhard Monien , Robert Preis, Towards Optimal Load Balancing Topologies, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.277-287, August 29-September 01, 2000
• 5: P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of markov chains. The Annals of Applied Probability, 1:36-61, 1991.
• 6: Ralf Diekmann , Andreas Frommer , Burkhard Monien, Efficient schemes for nearest neighbor load balancing, Parallel Computing, v.25 n.7, p.789-812, July 1999 [doi>10.1016/S0167-8191(99)00018-6 ]
• 7: Ralf Diekmann , S. Muthukrishnan , Madhu V. Nayakkankuppam, Engineering Diffusive Load Balancing Algorithms Using Experiments, Proceedings of the 4th International Symposium on Solving Irregularly Structured Problems in Parallel, p.111-122, June 12-13, 1997
• 8: J. Dodziuk and W. Kendall. Combinatorial laplacians and isoperimetric inequality. Pitman Res. Notes Math. Set., pages 68-74, 1986.
• 9: Robert Elsässer , Andreas Frommer , Burkhard Monien , Robert Preis, Optimal and Alternating-Direction Load Balancing Schemes, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.280-290, August 31-September 03, 1999
• 10: G. Fox, R. Williams, and P. Messina. Parallel Computing Works! Morgan Kaufmann, 1994.
• 11: Bhaskar Ghosh , S. Muthukrishnan , Martin H. Schultz, First and second order diffusive methods for rapid, coarse, distributed load balancing (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.72-81, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237509]
• 12: G. Golub and R. Varga. Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order richardson iterative methods. In Numer. Math., pages 147-156, 1961.
• 13: Y. F. Hu , R. J. Blake, An improved diffusion algorithm for dynamic load balancing, Parallel Computing, v.25 n.4, p.417-444, April 1999 [doi>10.1016/S0167-8191(99)00002-2 ]
• 14: Y. Hu, R. Blake, and D. Emerson. An optimal migration algorithm for dynamic load balancing. Concurrency: Practice ~ Experience, 10(6):467-483, 1998.
• 15: B. Mohar, Isoperimetric numbers of graphs, Journal of Combinatorial Theory Series B, v.47 n.3, p.274-291, Dec. 1989 [doi>10.1016/0095-8956(89)90029-4]
• 16: L. Reichel. The application of leja points to richardson iteration and polynomial preconditioning. Linear Algebra and its Applications, 154-156:389-414, 1991.
• 17: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 18: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 19: V. S. Sunderam , G. A. Geist, Heterogeneous parallel and distributed computing, Parallel Computing, v.25 n.13-14, p.1699-1721, Dec. 1999 [doi>10.1016/S0167-8191(99)00088-5 ]
• 20: R. Varga. Matrix Iterative Analysis. Prentice-Hall, 1962.
• 21: Chengzhong Xu , Chenzhong Xu , Francis C. Lau, Load Balancing in Parallel Computers: Theory and Practice, Kluwer Academic Publishers, Norwell, MA, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory, Verification