Dynamic load balancing in parallel processing on non-homogeneous clusters

• Autores: Armando De Giusti, Marcelo Naiouf , Laura Cristina De Giusti, Franco Chichizola
• Localización: Journal of Computer Science and Technology, ISSN-e 1666-6038, Vol. 5, Nº. 4, 2005 (Ejemplar dedicado a: Sixteenth Issue), págs. 272-278
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • This paper analyzes the dynamic and static balancing of non-homogenous cluster architectures, simultaneously analyzing the theoretical parallel Speedup as well as the Speedup experimentally obtained. Three interconnected clusters have been used in which the machines within each cluster have homogeneous processors although different among clusters. Thus, the set can be seen as a 25-processor heterogeneous cluster or as a multi-cluster scheme with subsets of homogeneous processors. A classical application (Parallel N-Queens) with a parallel solution algorithm, where processing predominates upon communication, has been chosen so as to go deep in the load balancing aspects (dynamic or static) without distortion of results caused by communication overhead. At the same time, three forms of load distribution in the processors (Direct Static, Predictive Static and Dynamic by Demand) have been studied, analyzing in each case parallel Speedup and load unbalancing regarding problem size and the processors used.

• Referencias bibliográficas
  • References [1] Al-Jaroodi J, Mohamed N, Jiang H, Swanson D. “Modeling Parallel Applications Performance on Heterogeneous System”. IEEE Computer...
  • [2] Baiardi F, Chiti S, Mori P, Ricci L. “Integrating Load Balancing and Locality in the Parallelization of Irregular Problems”. Future Generation...
  • [3] Bernhardsson B. ”Explicit Solution to the nqueens Problems for all n”. ACM SIGART Bulletin,2:7,1991.
  • [4] Bohn C, Lamont G. “Load Balancing for Heterogeneous Clusters of PCs”. Future Generation Computer Systems, Elsevier Science B.V., Vol 18,...
  • [5] Bruen A, Dixon R. “Then n-queens Problem. Discrete Mathematics”. 12:393-395, 1997.
  • [6] Campos L, Scherson I. “Rate of Change Load Balancing in Distributed and Parallel System”. Proceeding of the 13th International Parallel...
  • [7] De Giusti L, Novarini P, Naiouf M, De Giusti A. “Parallelization of the N-queens problem. Load unbalance analysis”. Workshop de Procesamiento...
  • [8] Donaldson V, Berman F, Paturi R. “Program Speedup in a Heterogeneous Computing Network”. Journal of Parallel and Distributed Computing...
  • [9] Dongarra J, Foster I, Fox G, Gropp W, Kennedy K, Torczon L, White A. “The Sourcebook of Parallel Computing”. Morgan Kauffman Publishers....
  • [10] Goldman. “Scalable Algorithms for Complete Exchange on Multi-Cluster Networks”. In: CCGRID'02, IEEE/ACM, Berlín, p.286-287, 2002.
  • [11] Grama A, Gupta A, Karypis G, Kumar V. “Introduction to Parallel Computing”. Second Edition. Pearson Addison Wesley, 2003.
  • [12] Hedetniemi S, Hedetniemi T, Reynolds R. “Combinatorial problems on chessboards: II”. Chapter 6 in Domination in graphs: advanced topic,...
  • [13] Hui C, Chanson S. “Improve Strategies for Dynamic Load Balancing”. IEEE Concurrency, pages 58-67. 1999.
  • [14] Jiang, Yeung. “Scalable Inter-Cluster Communication System for Clustered Multiprocessors”. 1997.
  • [15] Jordan H, Alaghband G. “Fundamentals of Parallel Computing”. Prentice Hall, 2002.
  • [16] Leopold C. "Parallel and Distributed Computing. A survey of Models, Paradigms, and Approaches". Wiley Series on Parallel and...
  • [17] Menascé D, Almeida V. “Cost-Performance Analysis of Heterogeneity in Supercomputer Architectures”. Proc. ACM-IEEE Supercomputing'90...
  • [18] Naiouf M. “Procesamiento Paralelo. Balance Dinámico de Carga en Algoritmos de Sorting”. Tesis Doctoral. Universidad Nacional de La Plata,...
  • [19] Ogura S, Nakada H, Matsuoka S. “Evaluation of the inter-cluster data transfer on Grid environment”. Proceedings of CCGrid 2003 , pp....
  • [20] Pfister G. “In Search of Clusters”. Prentice Hall, 2nd Edition, 1998.
  • [21] Ross K, Yao D. “Optimal Load Balancing and Scheduling in a Distributed Computer System”. Journal of Association for Computing Machinery,...
  • [22] Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J. “MPI: The Complete Reference”. Cambridge, MA: MIT Press, 1996. Available in web...
  • [23] Somers J. “The N Queens Problem a study in optimization”. www.jsomers.com/nqueen_demo/nqueens.html.
  • [24] Takaken, “N Queens Problem (number of Solutions)”. http://www.ic-net.or.jp/home/takaken /e /queen/.
  • [25] Tinetti F. “Cómputo Paralelo en Redes Locales de Computadoras”. Tesis Doctoral. Univ. Autónoma de Barcelona, 2004. https://lidi.info.unlp.edu.ar/~fernando/publis/publi.html
  • [26] Vaughan F, Grove D, Coddington P. “Communication Performance Issues for Two Cluster Computers”. Proceedings of the twenty-sixth Australasian...
  • [27] Watts J, Taylor S. “A Practical Approach to Dynamic Load Balancing”. IEEE Transactions on Parallel and Distributed Systems, 9(3), March...
  • [28] Zhang X, Yan Y. “Modeling and Characterizing Parallel Computing Performance on Heterogeneous Networks of Workstations”. Proceeding of...