Abstract
Load balancing algorithms are designed essentially to equally distribute the load on processors and maximize their utilities while minimizing the total task execution time. In order to achieve these goals, the load-balancing mechanism should be “fair” in distributing the load across the different processors. This implies that the difference between the heaviest-loaded and the lightest-loaded processors should be minimized. Therefore, the load information on each processor must be updated such that the load-balancing mechanism can be more effective. In this work, we present an application independent dynamic algorithm for scheduling tasks and load- balancing in message passing systems. We propose a DAG-based Dynamic Load Balancing algorithm for Real time applications (DAG-DLBR) that is designed to work dynamically to cope with possible changes in the load that might occur during runtime. This algorithm addresses the challenge of devising a load balancing scheme which judicially deals with the hybrid execution of existing real-time application (represented by a Direct Acyclic Graph (DAG)) together with newly arriving jobs. The main objective of this algorithm is to reduce response times of the newly arriving jobs while maintaining the time constrains of the existing DAG. To evaluate the performance of the DAG-DLBR algorithm, a comparison with the performance of two common dynamic load balancing algorithms is presented. This comparison is performed by evaluating, experimentally, the execution time of different load balancing algorithms on a homogenous real parallel machine. In addition, the values of load imbalance, the execution time, and the communication overhead time are evaluated analytically using different benchmarks as test-bed workloads. These workloads cover a wide range of dynamic applications with different task types. Experimental results illustrate the improved performance of the DAG-DLBR algorithm compared to both distributed and hierarchal based algorithms by at least 12 and 19%, respectively. This improvement is true for all workloads, even with highly dependent workload. The DAG-DLBR algorithm achieves lower computation time than its corresponding values of both the distributed and the hierarchical-based algorithms for 4, 8, 12 and 16 processors.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Wilkinson B., Allen M.: Parallel Programming Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice-Hall, Upper Saddle River (1999)
Xu C., Lau F.: Load Balancing in Parallel Computers: Theory and Practice. Kluwer, Norwell, MA (1997)
Shirazi A., Hurson A., Kavi M.: Scheduling and Load Balancing in Parallel Distributed Systems. Wiley-IEEE Computer Society Press, Los Alamitos, CA (1995)
Kwok Y., Ahmed I.: Benchmarking and comparisons of the task graph scheduling algorithms. J. Parallel Distrib. Comput. 59(3), 381–422 (1999)
Sakellariou, R., Zhao, H.: A hybrid Heuristics for DAG scheduling on heterogeneous systems. In: Proceedings of 18th International Parallel Distribution System (IPDPS’04), 26–30 April (2004)
El-Rewini H., Lewis T., Ali H.: Task Scheduling in Parallel and Distributed Systems. Prentice-Hall, Englewood Cliffs, NJ (1994)
Thanalapati T., Dandamudi S.: An efficient adaptive scheduling scheme for distributed memory multicomputers. IEEE Trans. Parallel Distrib. Syst. 12(7), 758–768 (2001)
Moharil, S., Lee, S.: Load balancing of parallel simulated annealing on a temporally heterogeneous cluster of workstation. In: Proceedings of 21st International Symposium on Parallel Distributed Processing (IPDPS’07), pp. 1–8. Long Beach, CA, 26–30 March (2007)
Moallem, A., Ludwig, S.: Using artificial life techniques for distributed grid job scheduling. In: Proceedings of ACM Symposium on Applied Computing, pp. 1091–1097. Honolulu, HI, 8–12 March (2009)
Zomaya A., Teh Y.: Observation on using genetic algorithms for dynamic load balancing. IEEE Trans. Parallel Distrib. Syst. 12(9), 899–911 (2001)
Sit, H., Ho, K., Leong, H., Luk, R., Ho, L.: An adaptive clustering approach to dynamic load balancing. In: Proceedings of International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 415–420. Hong Kong, SAR, China, 10–12 May (2004)
Hiess H., Schmitz M.: Decentralized dynamic load balancing: the particles approach. Inform. Sci. 48(1–2), 115–128 (1995)
Fu, Y., Wang, H., Lu, C., Chandra, R.: Distributed utilization control for real-time clusters with load balancing. In: Proceedings of 27th IEEE International Real-time Systems Symposium (RTSS’06), pp. 137–146. Rio de Janeiro 5–8 December (2006)
He, L., Jarvis, S., Spooner, D., Nudd, G.: Dynamic scheduling of parallel real time jobs by modeling pare capabilities in heterogeneous clusters. In: Proceedings of IEEE nternational Conference on Clusters Computing (Cluster03), pp. 2–10. Hong Kong, 1–4 December (2003)
Jovanovic Z., Maric S.: A Heuristic algorithms for dynamic task scheduling in highly parallel computing systems. Future Comput. Syst. 17, 721–732 (2001)
Dhakal S., Hayat M., Pezoa J., Yang C., Bader D.: Dynamic load balancing in distributed systems in the presence of delays: a regeneration-theory approach. IEEE Trans. Parallel Distrib. Syst. 18(4), 485–497 (2007)
Yan, K., Wang, S., Chang, C., Tsang, L.: The anatomy study of load balancing in distributed system. In: Proceedings of 7th International Conference on Parallel and Distributed Computing Systems. Applica and Technologies (PDCAT’06), pp. 460–463. Taipei, Taiwan, December (2006)
Hendrickson B., Devine K.: Dynamic load balancing in computational mechanics. Comput. Methods Appl. Mech. Eng. 184(2–4), 485–500 (2000)
Gustafson, J., Benner, R., Sears, M., Sullivan, T.: A radar simulation program for a 1024-processor hypercube. In: Proceedings of the Supercomputing’98, ACM/IEEEs, pp. 96–105. Reno, NV, 12–17 November (1989)
Arora, M., Das, S., Biswas, R.: A decentralized scheduling and load balancing algorithm for heterogeneous grid environment. In: Proceedings of International Conference on Parallel Processing Workshops, pp. 499–505. Vancouver, Canada, 12–20 August (2002)
Cortes, A.: A new distributed diffusion algorithm for dynamic load balancing in parallel systems. PhD Thesis, Department of Computer Science, Universided Autonoma de Barcelona, Spain, September (2000)
Serio, A., Ibanez, M.: Distributed load balancing for molecular dynamics simulation. In: Proceedings of 16th Annual International Symposium on High Performance Computing Systems and Applications, (HPCS’02), pp. 283–288. Monckton, NB, Canada, 16–19 June (2002)
LeMair M., Reeves P.: Strategies for load balancing on highly parallel computers. IEEE Trans. Parallel Distrib. Syst. 4(9), 970–993 (1993)
Watts J., Taylor S.: A practical approach to dynamic load balancing. IEEE Trans. Parallel Distrib. Syst. 9(3), 235–248 (1998)
Corradi, A., Leanardi, L., Zanbonelli, F.: Diffusion load balancing policies for dynamic applications. IEEE Concurrency, pp. 22–31. January–March (1999)
Hwang, D., Chung, T.: Enhanced gradient model: a dynamic-threshold based load balancing model for applicative multiprocessor system. In: Proceedings of 8th International Conference Parallel Distributed Compututing Systems, pp. 1–20, Orlando, FL, 21–23 September (1995)
Boukerche, A., Das, S.: Scalability of load balancing algorithm and its implementation on intel program. In: Proceedings of 4th International Symposium Parallel Architectures, Algorithms, and Networks (I-Span’99), pp. 274–281, Perth/Fremantle, Australia, 23–25 June (1999)
Antonis K., Garofalakis J., Mourtos I., Spirakis P.: A Hierarchical adaptive distributed algorithm for load balancing. J. Parallel Distrib. Comput. 64, 151–162 (2004)
Yagoubi B., Slimani Y.: Task load balancing strategy for grid computing. J. Comput. Sci. 3(3), 186–194 (2007)
Beltran, M., Guzman, A.: Designing load balancing algorithm capable of dealing with workload variability. In: Proceedings of 7th International Symposium on Parallel Distributed Computing, ISPDC’08, pp. 107–114, IEEE Computer Society, Krakow, Poland, 1–5 July (2008)
Mohammadpour, P., Sharifi, M., Paikan, A.: A self-training algorithm for load balancing in cluster computing. In: Proceedings of International Conference on Networked Computing and Advanced Information Management, NCM’2008, pp. 104–109. Gyeongju, Korea, 2–4 September (2008)
Christen P.: A parallel iterative linear system solver with dynamic load balancing. J. ANZIAM 42(E), C400–C414 (2000)
Campos L., Scherson I.: Rate of change load balancing in distributed and parallel systems. Parallel Comput. 26, 1213–1230 (2000)
Das S., Hanvey D., Biswas R.: Parallel processing of adaptive meshes with load balancing. IEEE Trans. Parallel Distrib. Syst. 12(12), 1269–1279 (2001)
Taylor V., Schwabe E., Holmer B., Hribar M.: Balancing load versus decreasing communication: parameterizing the tradeoff. J. Parallel Distrib. Comput. 61(5), 567–580 (2001)
Eager D., Lazowska E., Zaharjan J.: Adaptive load sharing in heterogeneous distributed systems. IEEE Trans. Softw. Eng. 12(5), 662–675 (1986)
Tout W.: Distributed load balancing for parallel main memory hash join. IEEE Trans. Parallel Distrib. Syst. 6(8), 841–849 (1995)
Vu Q., Ooi B., Rinard M., Tan K.: Histogram-based global load balancing in structured peer-to-peer systems. IEEE Trans. Knowl. Data Eng. 21(4), 595–608 (2009)
Crivelli S., Head-Gordon T.: A new load balancing strategy for the solution of dynamical large- tree-search problems using Hierarchical approach. IBM J. Res. Dev. 48(2), 153–160 (2004)
Rasmussen, M., Stuart, M., Karlsson, S.: Parallelism and scalability in an image processing application. Int. J. Parallel Prog., pp. 306–323, April (2009)
Bhatelé, J., Kalé, L., Kumar, S.: Dynamic topology aware load balancing algorithms for molecular dynamics applications. In: Proceedings of the 23rd International Conference on Supercomputing (ICS’09), Yorktown Heights, NY, pp. 110–116, June (2009)
Baruah S., Funk S., Goossens J.: Robustness results concerning EDF scheduling upon uniform multiprocessors. IEEE Trans. Comput. 52(9), 1185–1195 (2003)
Gao J., Sun Y., Das S., Guo M.: A taxonomy of application scheduling tools for high performance cluster computing. J. Cluster Comput. 9(3), 355–371 (2006)
Bharadwaj V., Ghose D., Robertazzi T.: Divisible load theory: a new paradigm for load scheduling in distributed systems. J. Cluster Comput. 6(1), 7–17 (2003)
BlazewiczDrozdowski, M., Guinand, F., Tryst, D.: Scheduling a divisible task in two dimensional toroidal mesh. J. Discrete Appl. Math. 94, 35–40 (1999)
McMillen C., Stubbs K., Rybski P., Stoeter S., Gini M., Papanikolopoulos N.: Resource scheduling and load balancing in distributed robotic control systems. J. Robot. Autom. Syst. 44(3–4), 251–259 (2003)
Gomes, K.: Parallelization of a Mobile Robot Localization Algorithm. Technical Report, The Department of Mathematical & Computer Sciences, Colorado School of Mines, USA, December (1995)
El-Rewini H., Abd-El-Barr M.: Advanced Computer Architecture and Parallel Processing. Wiley, London (2005)
Tobita, T., Kasahara, H.: A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. J. Sched 5(5), September–October (2002)
Farin, D., Mache, N., DeWith, P.: SAMPEG, a scene adaptive parallel MPEG-2 software encoder. In: Proceedings of SPIE Visual Communication and Image Processing (VCIP), 4310, pp. 272–283. San Jose, CA, 21–26 January (2001)
Bilas, A., Fritts, J., Singh, J.: Real-time parallel MPEG-2 decoding in software. In: Proceedings of the 11th International Symposium on Parallel Processing, pp. 197–204. Geneva, Switzerland, 1–5 April (1997)
Calinescu R.: Architecture Independent Loop Parallelization. Spring-Verlag, London (2000)
Yan Y., Jin C., Zhang X.: Adaptively scheduling parallel loops in distributed shared-memory systems. IEEE Trans. Parallel Distrib. Syst. 8(1), 70–81 (1997)
Cosnard M., Jeannot E.: Compact DAG representation and its dynamic scheduling. J. Parallel Distrib. Comput. 58(3), 487–514 (1999)
Hwang Y., Ahuja N.: A potential field approach to path planning. IEEE Trans. Robot. Autom. 8(2), 23–32 (1992)
Kambhampati, S., Davis, L.: Multi-resolution path planning for mobile robots. IEEE J. Robot. Autom. RA-2(3), September (1986)
Parsytec PowerXplorer Hardware User Guide.: Parsytec GmbH (1994)
Elkabbany, G.: Dynamic Load Redistribution Algorithm for Real-Time Applications in Message Passing Systems. PhD Thesis, Electronics and Communications Engineering Department, Facility of Engineering, Cairo University, Egypt, October (2007)
Tobita T., Kasahara H.: A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. J. Scheduling 5(5), 379–394 (2002)
Chow Y., Kohler W.: Models for dynamic load balancing in a heterogeneous multiple processor system. IEEE Trans. Comput. c-28(5), 354–361 (1979)
Yagoubi B., Tayeb Lilia H., Moussa H.: Load balancing in grid computing. Asian J. Inform. Tech. 5(10), 1095–1103 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
El Kabbany, G.F., Wanas, N.M., Hegazi, N.H. et al. A Dynamic Load Balancing Framework for Real-time Applications in Message Passing Systems. Int J Parallel Prog 39, 143–182 (2011). https://doi.org/10.1007/s10766-010-0134-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10766-010-0134-5