Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Dynamic load balancing in parallel processing on non-homogeneous clusters
Keywords:
Parallel Systems, Cluster Architectures, Parallel Algorithms, Dynamic and Static Load Balancing, Parallel Speedup, Homogeneous and Non-Homogeneous ProcessorsAbstract
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.
Downloads
Download data is not yet available.
References
[1] Al-Jaroodi J, Mohamed N, Jiang H, Swanson D. “Modeling Parallel Applications Performance on Heterogeneous System”. IEEE Computer Society, 2003.
[2] Baiardi F, Chiti S, Mori P, Ricci L. “Integrating Load Balancing and Locality in the Parallelization of Irregular Problems”. Future Generation Computer Systems, Elsevier Science B.V., Vol 17, 2001, pp 969-975.
[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, 2002, pp 389-400.
[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 Processing Symposium and 10th Symposium on Parallel and Distributed Processing, San Juan, Puerto Rico, Pages 701-707. 1999.
[7] De Giusti L, Novarini P, Naiouf M, De Giusti A. “Parallelization of the N-queens problem. Load unbalance analysis”. Workshop de Procesamiento Paralelo y Distribuido (WPPD), Congreso Argentino de Ciencias de la Computación (CACIC’03), 2003.
[8] Donaldson V, Berman F, Paturi R. “Program Speedup in a Heterogeneous Computing Network”. Journal of Parallel and Distributed Computing 21:3 (6/1994), 316-322.
[9] Dongarra J, Foster I, Fox G, Gropp W, Kennedy K, Torczon L, White A. “The Sourcebook of Parallel Computing”. Morgan Kauffman Publishers. Elsevier Science, 2003.
[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, pag 133-162, 1998.
[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 Distributed Computing. Albert Zomaya Series Editor, 2001.
[17] Menascé D, Almeida V. “Cost-Performance Analysis of Heterogeneity in Supercomputer Architectures”. Proc. ACM-IEEE Supercomputing'90 Conference, New York, Nov 1990.
[18] Naiouf M. “Procesamiento Paralelo. Balance Dinámico de Carga en Algoritmos de Sorting”. Tesis Doctoral. Universidad Nacional de La Plata, 2004.
[19] Ogura S, Nakada H, Matsuoka S. “Evaluation of the inter-cluster data transfer on Grid environment”. Proceedings of CCGrid 2003 , pp. 374-381, May 2003.
[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, 38 (3): 676-690.1991.
[22] Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J. “MPI: The Complete Reference”. Cambridge, MA: MIT Press, 1996. Available in web site: http://www.netlib.org/utk/papers/mpi-book/mpi-book.html.
[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 computer science conference on Conference in research and practice in information technology, p.171-180, February 01, 2003, Adelaide, Australia.
[27] Watts J, Taylor S. “A Practical Approach to Dynamic Load Balancing”. IEEE Transactions on Parallel and Distributed Systems, 9(3), March 1998, pp. 235-248.
[28] Zhang X, Yan Y. “Modeling and Characterizing Parallel Computing Performance on Heterogeneous Networks of Workstations”. Proceeding of the 7th Symposium on Parallel and Distributed Processing. 1995.
[2] Baiardi F, Chiti S, Mori P, Ricci L. “Integrating Load Balancing and Locality in the Parallelization of Irregular Problems”. Future Generation Computer Systems, Elsevier Science B.V., Vol 17, 2001, pp 969-975.
[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, 2002, pp 389-400.
[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 Processing Symposium and 10th Symposium on Parallel and Distributed Processing, San Juan, Puerto Rico, Pages 701-707. 1999.
[7] De Giusti L, Novarini P, Naiouf M, De Giusti A. “Parallelization of the N-queens problem. Load unbalance analysis”. Workshop de Procesamiento Paralelo y Distribuido (WPPD), Congreso Argentino de Ciencias de la Computación (CACIC’03), 2003.
[8] Donaldson V, Berman F, Paturi R. “Program Speedup in a Heterogeneous Computing Network”. Journal of Parallel and Distributed Computing 21:3 (6/1994), 316-322.
[9] Dongarra J, Foster I, Fox G, Gropp W, Kennedy K, Torczon L, White A. “The Sourcebook of Parallel Computing”. Morgan Kauffman Publishers. Elsevier Science, 2003.
[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, pag 133-162, 1998.
[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 Distributed Computing. Albert Zomaya Series Editor, 2001.
[17] Menascé D, Almeida V. “Cost-Performance Analysis of Heterogeneity in Supercomputer Architectures”. Proc. ACM-IEEE Supercomputing'90 Conference, New York, Nov 1990.
[18] Naiouf M. “Procesamiento Paralelo. Balance Dinámico de Carga en Algoritmos de Sorting”. Tesis Doctoral. Universidad Nacional de La Plata, 2004.
[19] Ogura S, Nakada H, Matsuoka S. “Evaluation of the inter-cluster data transfer on Grid environment”. Proceedings of CCGrid 2003 , pp. 374-381, May 2003.
[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, 38 (3): 676-690.1991.
[22] Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J. “MPI: The Complete Reference”. Cambridge, MA: MIT Press, 1996. Available in web site: http://www.netlib.org/utk/papers/mpi-book/mpi-book.html.
[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 computer science conference on Conference in research and practice in information technology, p.171-180, February 01, 2003, Adelaide, Australia.
[27] Watts J, Taylor S. “A Practical Approach to Dynamic Load Balancing”. IEEE Transactions on Parallel and Distributed Systems, 9(3), March 1998, pp. 235-248.
[28] Zhang X, Yan Y. “Modeling and Characterizing Parallel Computing Performance on Heterogeneous Networks of Workstations”. Proceeding of the 7th Symposium on Parallel and Distributed Processing. 1995.
Downloads
Published
2005-12-01
How to Cite
De Giusti, A. E., Naiouf, M., De Giusti, L. C., & Chichizola, F. (2005). Dynamic load balancing in parallel processing on non-homogeneous clusters. Journal of Computer Science and Technology, 5(04), p. 272–278. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/847
Issue
Section
Original Articles
