Token-based adaptive load balancing for dynamically parallel computations on multicomputer platforms

ABSTRACT

The paper suggests an algorithm for token-based adaptive load balancing for dynamically parallel computations on multicomputer platforms. The proposed algorithm for load balance is initiated and performed by the idle or under-loaded processes and requires token message circulating among the parallel processes and bearing information about the load distribution throughout the system. The efficiency of the algorithm is estimated for the case study of Sam Loyd's puzzle utilizing parallel version of branch-and-bound search algorithm with depth-first search strategy. The experimental study is based on flat parallel program implementations. Speedup and efficiency of the parallel system are estimated as well as scalability of the application workload and the multicomputer size.

REFERENCES

• 1: Koip P., Parallel Algorithms for Combinatorial Search Problems, University of Massachusetts, 2005
• 2: Grama A., A. Gupta, G. Kapyris, V. Kumar, Introduction to Parallel Computing, Addison Wesley, 2003.
• 3: Raghavan P., Parallel Combinatorial Search, California, 2005.
• 4: El-Ghazali Talbi, Parallel Combinatorial Optimization (Wiley Series on Parallel and Distributed Computing), Wiley-Interscience, 2006
• 5: Borovska P., Parallel Combinatorial Search on Computer Cluster: Sam Loyd's Puzzle, International Conference on Computer Systems and Technologies -- CompSysTech'06, 2006.
• 6: Reinhard Lüling , Burkhard Monien, A dynamic distributed load balancing algorithm with provable good performance, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.164-172, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165252]
• 7: Parag Kulkarni , Indranil SenGupta, Dual and multiple token based approaches for load balancing, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.2, p.95-110, February 2005 [doi>10.1016/j.sysarc.2004.10.001]
• 8: A. Plastino , C. C. Ribeiro , N. Rodriguez, Developing SPMD applications with load balancing, Parallel Computing, v.29 n.6, p.743-766, June 2003 [doi>10.1016/S0167-8191(03)00060-7]
• 9: Borovska P., Efficiency of Load Balancing Methods on Multicomputer Platforms, Forth International Scientific Conference "Challenges in Higher Education and Research", June 2006, Sozopol, Bulgaria, Heron Press, Sofia, ISBN 954-580-206-5, pp.42--46.

INDEX TERMS

Keywords:
distributed load balancing, parallel computing, parallel programming, scalability