The problem of computing a large set of different tasks on a set of heterogeneous resources connected by a network is very common nowadays in very different environments and load balancing is indispensable for achieving high performance and high throughput in systems such as clusters. Cluster heterogeneity increases the difficulty of balancing the load across the system nodes and, although the relationship between heterogeneity and load balancing is difficult to describe analytically, in this paper different models and performance metrics are proposed to describe heterogeneous cluster behavior and to perform an exhaustive analysis of the effects of heterogeneity on load balancing algorithm performance. This analysis allows us to propose efficient solutions capable of dealing with heterogeneity for all the load balancing algorithm stages. Furthermore, a load balancing algorithm has been implemented following these solutions to demonstrate, with experimental results, its efficiency on real heterogeneous clusters.
Ali, S., Maciejewski, A.A., Siegel, H.J., and Kim, J.K. (2003). Definition of a robustness metric for resource allocation. In Proceedings of the International Symposium on Parallel and Distributed Processing. IEEE Computer Society.
2.
Ali, S., Maciejewski, A.A., Siegel, H.J., and Kim, J.K. (2004). Measuring the robustness of a resource allocation , IEEE Transactions on Parallel and Distributed Systems, 15(7): 630-641.
3.
Arora, M., Das, S.K., and Biswas, R. (2002). A de-dentralized scheduling and load balancing algorithm for heterogeneous Grid environments. In Proceedings of the International Conference on Parallel Processing Workshops , pp. 499-505. IEEE Computer Society.
4.
Awerbuch, B., Azar, Y., Leonardi, S., and Regev, O. (1999). Minimizing the flow time without migration. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 198-205. New York: ACM Press .
5.
Baker, M. (2000). Cluster Computing White Paper. IEEE Task Force on Cluster Computing. Computing Research Repository.
6.
Barak, A. and La'adan, O. (1998). The MOSIX multicomputer operating system for high performance cluster computing, Journal of Future Generation Computer Systems, 13(5): 361-372.
7.
Barak, A., La'adan, O., and Shiloh, A. (1999). Scalable cluster computing with MOSIX for Linux . In Proceedings of the Linux EXPO'99, pp. 95-100. New York: Elsevier.
8.
Beaumont, O., Boudet, V., Petitet, A., Rastello, F., and Robert, Y. (2001a). A proposal for a heterogeneous cluster scalapack (dense linear solvers), IEEE Transactions on Computers, 50(10): 1052-1070.
9.
Beaumont, O., Boudet, V., Rastello, F., and Robert, Y. (2001b). Matrix multiplication on heterogeneous platforms , IEEE Transactions on Parallel and Distributed Systems, 12(10): 1033-1051.
10.
Becchetti, L., Leonardi, S., and Muthukrishnan, S. (2000). Scheduling to minimize average stretch without migration. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 548-557. Society for Industrial and Applied Mathematics.
11.
Bell, G. and Gray, J. (2002). What's next in high-performance computing? Communications of the ACM, 45(2): 91-95.
12.
Beltrán, M., Guzmán, A., and Bosque, J. (2006). Dealing with heterogeneity in load balancing algorithms . In Proceedings of the 5th International Symposium on Parallel and Distributed Computing, pp. 123-132. IEEE Computer Society.
13.
Beltrán, M., Guzmán, A., and Bosque, J. (2008). A new CPU availability prediction model for time-shared systems, IEEE Transactions on Computers, 57(7): 865-875.
14.
Boer, R.J.M. (1996). Resource management in the Condor system, Master's Thesis, Delft University of Technology, Faculty of Technical Mathematics and Informatics.
15.
Bricker, A., Litzkow, M., and Livny, M. (1992). Condor technical summary, Technical Report CS-TR-92-1069 , Computer Science Department, University of Wisconsin .
16.
Cheng, K.-W., Yang, C.-T., Lai, C.-L., and Chang, S.-C. (2004). A parallel loop self-scheduling on Grid computing environments. In Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 409-414. IEEE Computer Society.
17.
Dongarra, J. and Lastovetsky, A. (2006). An overview of heterogeneous high performance and grid computing, In Engineering the Grid: Status and Perspective, pp. 1-25. American Scientific Publishers.
18.
Dovolnov, E., Kalinov, A., and Klimov, S. (2003). Natural block data decomposition for heterogeneous clusters. In Proceedings of the 17th International Parallel and Distributed Processing Symposium. IEEE Computer Society, 184-93.
19.
Goscinski, A. (1991). Distributed Operating Systems: The Logical Design . Boston, Addison Wesley.
20.
Higgins, R. and Lastovetsky, A. (2005). Scheduling for heterogeneous networks of computers with persistent fluctuation of load. In Proceedings of the 13th International Conference on Parallel Computing, pp. 171-178. IASTER .
21.
Kaddoura, M., Ranka, S., and Wang, A. (1996). Array decompositions for nonuniform computational environments, Journal of Parallel and Distributed Computing , 36(2): 91-105.
22.
Kalinov, A. and Lastovetsky, A. (2001). Heterogeneous distribution of computations solving linear algebra problems on networks of heterogeneous computers, Journal of Parallel and Distributed Computing, 61(4): 520-535.
23.
Lee, G.-H., Woo, W.-D., and Yoon, B.-N. (1998). An adaptive load balancing algorithm using simple prediction mechanism. In Proceedings of the 9th International Workshop on Database and Expert Systems Applications, pp. 496- 501. IEEE Computer Society.
24.
Lu, C. and Lau, S.-M. (1996). An adaptive load balancing algorithm for heterogeneous distributed systems with multiple task classes. In Proceedings of the 16th International Conference on Distributed Computing Systems, pp. 629- 636. IEEE Computer Society.
25.
Milojicic, D.S., Douglis, F., Paindaveine, D., Wheeler, M., and Zhou, Z. (2000). Process migration, ACM Computing Surveys, 32(3): 241-299.
26.
Mitzenmacher, M., Prabhakar, B., and Shah, D. (2002). Load balancing with memory. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 799-808. IEEE Computer Society.
Ohtaki, Y., Takahashi, D., Boku, T., and Sato, M. (2004). Parallel implementation of Strassen's matrix multiplication algorithm for heterogeneous clusters. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, pp. 799-808. IEEE Computer Society.
29.
Pfister, G. (1998). In Search of Clusters: The Ongoing Battle in Lowly Parallel Computing, Austhin, Texas, Prentice-Hall.
30.
Qin, X. and Jiang, H. (2005). A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs on heterogeneous clusters, Journal of Parallel and Distributed Computing, 65(8): 885-900.
31.
Ranaweera, S. and Agrawal, D. (2001). Scheduling of periodic time critical applications for pipelined execution on heterogeneous systems. In Proceedings of the International Conference on Parallel Processing, pp. 131- 138. IEEE Computer Society.
32.
Rieffel, J.W.M. and Taylor, S. (1998). Dynamic management of heterogeneous resources . In High Performance Computing: Grand Challenges in Computer Simulation, pp. 151-156. ACM Press.
33.
Shen, K., Yang, T., and Chu, L. (2002). Cluster load balancing for fine-grain network services. In International Parallel and Distributed Processing Symposium, pp. 51-58. IEEE Computer Society.
34.
Siegel, H.J., Antonio, J.K., Metzger, R.C., Tan, M., and Li, Y.A. (1995). Heterogeneous computing. In Handbook of Parallel and Distributed Computing, edited by A. Y. Zomaya.New Yorks: McGraw-Hill .
35.
Singhal, M. and Shivaratri, N. (1994). Advanced Concepts in Operating Systems, McGraw Hill.
36.
Wolski, R., Spring, N., and Hayes, J. (1999). Predicting the CPU availability of time-shared Unix systems on the computational grid. In Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing , pp. 105-112. IEEE Computer Society.
37.
Xu, C. and Lau, F.C.M. (1997). Load Balancing in Parallel Computers: Theory and Practice, Boston: Kluwer Academic Publishers.
