[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A Dynamic Load Balancing Framework for Real-time Applications in Message Passing Systems

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Wilkinson B., Allen M.: Parallel Programming Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice-Hall, Upper Saddle River (1999)

    Google Scholar 

  2. Xu C., Lau F.: Load Balancing in Parallel Computers: Theory and Practice. Kluwer, Norwell, MA (1997)

    Google Scholar 

  3. Shirazi A., Hurson A., Kavi M.: Scheduling and Load Balancing in Parallel Distributed Systems. Wiley-IEEE Computer Society Press, Los Alamitos, CA (1995)

    Google Scholar 

  4. Kwok Y., Ahmed I.: Benchmarking and comparisons of the task graph scheduling algorithms. J. Parallel Distrib. Comput. 59(3), 381–422 (1999)

    Article  MATH  Google Scholar 

  5. 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)

  6. El-Rewini H., Lewis T., Ali H.: Task Scheduling in Parallel and Distributed Systems. Prentice-Hall, Englewood Cliffs, NJ (1994)

    Google Scholar 

  7. Thanalapati T., Dandamudi S.: An efficient adaptive scheduling scheme for distributed memory multicomputers. IEEE Trans. Parallel Distrib. Syst. 12(7), 758–768 (2001)

    Article  Google Scholar 

  8. 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)

  9. 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)

  10. Zomaya A., Teh Y.: Observation on using genetic algorithms for dynamic load balancing. IEEE Trans. Parallel Distrib. Syst. 12(9), 899–911 (2001)

    Article  Google Scholar 

  11. 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)

  12. Hiess H., Schmitz M.: Decentralized dynamic load balancing: the particles approach. Inform. Sci. 48(1–2), 115–128 (1995)

    Article  Google Scholar 

  13. 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)

  14. 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)

  15. Jovanovic Z., Maric S.: A Heuristic algorithms for dynamic task scheduling in highly parallel computing systems. Future Comput. Syst. 17, 721–732 (2001)

    Article  MATH  Google Scholar 

  16. 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)

    Article  Google Scholar 

  17. 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)

  18. Hendrickson B., Devine K.: Dynamic load balancing in computational mechanics. Comput. Methods Appl. Mech. Eng. 184(2–4), 485–500 (2000)

    Article  MATH  Google Scholar 

  19. 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)

  20. 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)

  21. 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)

  22. 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)

  23. LeMair M., Reeves P.: Strategies for load balancing on highly parallel computers. IEEE Trans. Parallel Distrib. Syst. 4(9), 970–993 (1993)

    Google Scholar 

  24. Watts J., Taylor S.: A practical approach to dynamic load balancing. IEEE Trans. Parallel Distrib. Syst. 9(3), 235–248 (1998)

    Article  Google Scholar 

  25. Corradi, A., Leanardi, L., Zanbonelli, F.: Diffusion load balancing policies for dynamic applications. IEEE Concurrency, pp. 22–31. January–March (1999)

  26. 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)

  27. 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)

  28. Antonis K., Garofalakis J., Mourtos I., Spirakis P.: A Hierarchical adaptive distributed algorithm for load balancing. J. Parallel Distrib. Comput. 64, 151–162 (2004)

    Article  MATH  Google Scholar 

  29. Yagoubi B., Slimani Y.: Task load balancing strategy for grid computing. J. Comput. Sci. 3(3), 186–194 (2007)

    Article  Google Scholar 

  30. 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)

  31. 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)

  32. Christen P.: A parallel iterative linear system solver with dynamic load balancing. J. ANZIAM 42(E), C400–C414 (2000)

    MathSciNet  Google Scholar 

  33. Campos L., Scherson I.: Rate of change load balancing in distributed and parallel systems. Parallel Comput. 26, 1213–1230 (2000)

    Article  MATH  Google Scholar 

  34. Das S., Hanvey D., Biswas R.: Parallel processing of adaptive meshes with load balancing. IEEE Trans. Parallel Distrib. Syst. 12(12), 1269–1279 (2001)

    Article  Google Scholar 

  35. 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)

    Article  MATH  Google Scholar 

  36. Eager D., Lazowska E., Zaharjan J.: Adaptive load sharing in heterogeneous distributed systems. IEEE Trans. Softw. Eng. 12(5), 662–675 (1986)

    Google Scholar 

  37. Tout W.: Distributed load balancing for parallel main memory hash join. IEEE Trans. Parallel Distrib. Syst. 6(8), 841–849 (1995)

    Article  Google Scholar 

  38. 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)

    Article  Google Scholar 

  39. 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)

    Article  Google Scholar 

  40. Rasmussen, M., Stuart, M., Karlsson, S.: Parallelism and scalability in an image processing application. Int. J. Parallel Prog., pp. 306–323, April (2009)

  41. 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)

  42. Baruah S., Funk S., Goossens J.: Robustness results concerning EDF scheduling upon uniform multiprocessors. IEEE Trans. Comput. 52(9), 1185–1195 (2003)

    Article  Google Scholar 

  43. 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)

    Article  Google Scholar 

  44. 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)

    Article  Google Scholar 

  45. BlazewiczDrozdowski, M., Guinand, F., Tryst, D.: Scheduling a divisible task in two dimensional toroidal mesh. J. Discrete Appl. Math. 94, 35–40 (1999)

    Google Scholar 

  46. 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)

    Article  Google Scholar 

  47. Gomes, K.: Parallelization of a Mobile Robot Localization Algorithm. Technical Report, The Department of Mathematical & Computer Sciences, Colorado School of Mines, USA, December (1995)

  48. El-Rewini H., Abd-El-Barr M.: Advanced Computer Architecture and Parallel Processing. Wiley, London (2005)

    Google Scholar 

  49. Tobita, T., Kasahara, H.: A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. J. Sched 5(5), September–October (2002)

  50. 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)

  51. 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)

  52. Calinescu R.: Architecture Independent Loop Parallelization. Spring-Verlag, London (2000)

    Google Scholar 

  53. 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)

    Article  Google Scholar 

  54. Cosnard M., Jeannot E.: Compact DAG representation and its dynamic scheduling. J. Parallel Distrib. Comput. 58(3), 487–514 (1999)

    Article  Google Scholar 

  55. Hwang Y., Ahuja N.: A potential field approach to path planning. IEEE Trans. Robot. Autom. 8(2), 23–32 (1992)

    Article  Google Scholar 

  56. Kambhampati, S., Davis, L.: Multi-resolution path planning for mobile robots. IEEE J. Robot. Autom. RA-2(3), September (1986)

  57. Parsytec PowerXplorer Hardware User Guide.: Parsytec GmbH (1994)

  58. 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)

  59. Tobita T., Kasahara H.: A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. J. Scheduling 5(5), 379–394 (2002)

    Article  MATH  Google Scholar 

  60. Chow Y., Kohler W.: Models for dynamic load balancing in a heterogeneous multiple processor system. IEEE Trans. Comput. c-28(5), 354–361 (1979)

    Article  MathSciNet  Google Scholar 

  61. Yagoubi B., Tayeb Lilia H., Moussa H.: Load balancing in grid computing. Asian J. Inform. Tech. 5(10), 1095–1103 (2006)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, Electronics Research Institute, El-Tahrir St. Dokki, Giza, Egypt

    Ghada F. El Kabbany & Nadia H. Hegazi

  2. Cairo Microsoft Innovation Lab (CMIC), 306 Chorniche El-Nile, Maadi, Cairo, Egypt

    Nayer M. Wanas

  3. Department of Computer Engineering, Faculty of Engineering, Cairo University, Giza, Egypt

    Samir I. Shaheen

Authors
  1. Ghada F. El Kabbany
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nayer M. Wanas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nadia H. Hegazi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Samir I. Shaheen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ghada F. El Kabbany.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10766-010-0134-5

Keywords

Search

Navigation