More Web Proxy on the site http://driver.im/

research-article

Prediction-Based Dynamic Load-Sharing Heuristics

Authors:

M. Devarakonda,

R. K. IyerAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 4, Issue 6

Pages 638 - 648

https://doi.org/10.1109/71.242159

Published: 01 June 1993 Publication History

Abstract

Presents dynamic load-sharing heuristics that use predicted resource requirements ofprocesses to manage workloads in a distributed system. A previously developed statisticalpattern-recognition method is employed for resource prediction. Whilenonprediction-based heuristics depend on a rapidly changing system status, the newheuristics depend on slowly changing program resource usage patterns. Furthermore,prediction-based heuristics can be more effective since they use future requirementsrather than just the current system state. Four prediction-based heuristics, twocentralized and two distributed, are presented. Using trace driven simulations, they arecompared against random scheduling and two effective nonprediction based heuristics.Results show that the prediction-based centralized heuristics achieve up to 30% betterresponse times than the nonprediction centralized heuristic, and that theprediction-based distributed heuristics achieve up to 50% improvements relative to theirnonpredictive counterpart.

References

[1]

{1} A. Barak and A. Shiloh, "A distributed load balancing policy for a multicomputer," Software - Practice and Experience, vol. 15, pp. 901-913, Sept. 1985.

Digital Library

[2]

{2} T. Casavant and J. Kuhl, "A taxonomy of scheduling in general-purpose distributed computing systems," IEEE Trans. Software Eng., vol. 14, no. 2, pp. 141-154, Feb. 1988.

Digital Library

[3]

{3} M. Devarakonda and R. K. Iyer, "Predictability of process resource usage: A measurement-based study of UNIX," IEEE Trans. Software Eng., vol. 15, no. 12, Dec. 1989.

Digital Library

[4]

{4} D. Eager, E. Lazowska, and J. Zahorjan, "A dynamic load sharing in homogeneous distributed systems," IEEE Trans. Software Eng., vol. SE-12, no. 5, pp. 662-675, May 1986.

Digital Library

[5]

{5} K. Efe and B. Groselj, "Minimizing control overheads in adaptive load sharing," in Proc. 9th Int. Conf. Distributed Comput. Syst., June 1989, pp. 307-315.

[6]

{6} D. Ferrari and S. Zhou, "A load index for dynamic load balancing," in Proc. IEEE-ACM Fall Joint Comput. Conf., Nov. 1986, pp. 684-690.

Digital Library

[7]

{7} K. Goswami, R. Iyer, and M. Devarakonda, "Load sharing based on task resource prediction," in Proc. 22nd Annu. Hawaii Int. Conf. Syst. Sci., vol. 2, Jan. 1989, pp. 921-927.

[8]

{8} K. Hwang, W. Croft, G. Goble, B. Wah, F. Briggs, W. Simmons, and C. Coates, "A UNIX-based local computer network with load balancing," IEEE Comput. Mag., vol. 15, no. 4, Apr. 1982.

[9]

{9} P. Krueger and R. Finkel, "An adaptive load balancing algorithm for a multicomputer," Univ. Wisconsin, Tech. Rep. 539, Apr. 1984.

[10]

{10} P. Krueger and R. Chawla, "The Stealth distributed scheduler," in Proc. 11th Int. Conf. Distributed Comput. Syst., May 1991, pp. 336-343.

[11]

{11} E. Lazowska, J. Zahorjan, D. Cheriton, and W. Zwaenepoel, "File access performance of diskless workstations," Univ. Washington, Tech. Rep. 840-06-01, June 1984.

[12]

{12} W. Leland and T. Ott, "Load balancing heuristics and process behavior," ACM, pp. 54-69, Sept. 1986.

Digital Library

[13]

{13} M. Livny, "The study of load balancing algorithms for decentralized distributed processing systems," Ph.D. dissertation, Weizmann Institute of Science, Aug. 1983.

[14]

{14} M. L. Ni, "A distributed load balancing algorithm for point-to-point local computer networks," in Proc. CompCon, Comput. Networks, Sept. 1983, pp. 116-123.

[15]

{15} M. L. Powell and B. P. Miller, "Process migration in DEMOS/MP," Oper. Syst. Rev., vol. 17, no. 5, 1983.

Digital Library

[16]

{16} M. Schaar, K. Efe, L. Delcambre, and L. N. Bhuyan, "Load balancing with network cooperation," in Proc. 11th Int. Conf. Distributed Comput. Syst., May 1991, pp. 328-335.

[17]

{17} H. Schwetman, "CSIM: A C-based, process-oriented simulation language," in Proc. Winter Simulation Conf., Jan. 1986, pp. 387-396.

Digital Library

[18]

{18} J. Stankovic, "Stability and distributed scheduling algorithms," IEEE Trans. Software Eng., vol. SE-11, no. 10, pp. 1141-1152, Oct. 1985.

Digital Library

[19]

{19} A. Svensson, "History, an intelligent load sharing filter," in Proc. 10th Int. Conf. Distributed Comput. Syst., May 1990, pp. 546-553.

[20]

{20} A. Thomasian, "A performance study of dynamic load balancing in distributed systems," in Proc. 7th Int. Conf. Distributed Comput. Syst., Sept. 1987, pp. 178-184.

[21]

{21} R. B. Wallace and S. Zhou, "Network performance in a workstation environment," in Proc. 22nd Annu. Hawaii Int. Conf. Syst. Sci., vol. 2, Jan. 1989, pp. 914-920.

[22]

{22} Y. Wang and R. Morris, "Load sharing in distributed systems," IEEE Trans. Comput., vol. C-34, no. 3, pp. 204-217, Mar. 1985.

[23]

{23} W. Zhao, K. Ramamritham, and J. A. Stankovic, "Scheduling tasks with resource requirements in hard real-time systems," IEEE Trans. Software Eng., vol. SE-13, no. 5, May 1987.

Digital Library

[24]

{24} S. Zhou, "A trace-driven simulation study of dynamic load balancing," IEEE Trans. Software Eng., vol. 14, no. 9, pp. 1327-1341, Sept. 1988.

Digital Library

[25]

{25} S. Zhou, "An experimental assessment of resource queue length as load indices," Univ. California Berkeley, Tech. Rep. #UCB/CSD 86/2986, Apr. 1986.

Digital Library

Cited By

(2018)Image optimisation using dynamic load balancingInternational Journal of Knowledge Engineering and Data Mining10.5555/3272143.32721475:1-2(68-89)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3272143.3272147
Trivedi RChandra AWeissman J(2006)Heterogeneity-Aware Workload Distribution in Donation-Based GridsInternational Journal of High Performance Computing Applications10.1177/109434200606840820:4(455-466)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1177/1094342006068408
Park HKim B(2005)Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2004.04.00765:3(261-274)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2004.04.007
Show More Cited By

Prediction-Based Dynamic Load-Sharing Heuristics
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Adaptive Load Balancing Dashboard in Dynamic Distributed Systems

Considering the dynamic nature of new generation scientific problems, load balancing is a necessity to manage the load in an efficient manner. Load balancing systems are used to optimize the resource consumption, maximize the throughput, minimize ...
A game-theoretic model for dynamic load balancing in distributed systems
ICAC3 '09: Proceedings of the International Conference on Advances in Computing, Communication and Control

Process of improving the performance of a parallel and distributed system through a redistribution of load among the processors is called load balancing. If it is being done at run time then it treats as dynamic load balancing. In this paper we present ...
Dynamic load balancing on a distributed system
SPDP '94: Proceedings of the 1994 6th IEEE Symposium on Parallel and Distributed Processing

We consider the problem of load balancing on loosely coupled multiprocessor systems. During run time, a task may create subtasks, which are dynamically distributed by the load balancer. Different load-balancing strategies (receiver-initiated, sender-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 4, Issue 6

June 1993

120 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1993 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 June 1993

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

(2018)Image optimisation using dynamic load balancingInternational Journal of Knowledge Engineering and Data Mining10.5555/3272143.32721475:1-2(68-89)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3272143.3272147
Trivedi RChandra AWeissman J(2006)Heterogeneity-Aware Workload Distribution in Donation-Based GridsInternational Journal of High Performance Computing Applications10.1177/109434200606840820:4(455-466)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1177/1094342006068408
Park HKim B(2005)Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2004.04.00765:3(261-274)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2004.04.007
Kwok YCheung L(2004)A new fuzzy-decision based load balancing system for distributed object computingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.11.00264:2(238-253)Online publication date: 1-Feb-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.11.002
Antonis KGarofalakis JMourtos ISpirakis P(2004)A hierarchical adaptive distributed algorithm for load balancingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.07.00264:1(151-162)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.07.002
Shen KYang TChu L(2002)Cluster Load Balancing for Fine-Grain Network ServicesProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.661892Online publication date: 15-Apr-2002
https://dl.acm.org/doi/10.5555/645610.661892
Shaout AMcAuliffe P(2000)Fuzzy load balancing in an industrial distributed system for job schedulingJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.5555/1314447.13144508:3(191-199)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.5555/1314447.1314450
Stefano ABello L(1999)Exploiting the Knowledge of Task Structure for Distributed AllocationJournal of Parallel and Distributed Computing10.1006/jpdc.1999.156359:1(54-67)Online publication date: 1-Oct-1999
https://dl.acm.org/doi/10.1006/jpdc.1999.1563
Rigoutsos IDelis A(1998)Managing Statistical Behavior of Large Data Sets in Shared-Nothing ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/71.7359559:11(1073-1087)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1109/71.735955
Sohn JRobertazzi TLuryi S(1998)Optimizing Computing Costs Using Divisible Load AnalysisIEEE Transactions on Parallel and Distributed Systems10.1109/71.6743159:3(225-234)Online publication date: 1-Mar-1998
https://dl.acm.org/doi/10.1109/71.674315
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents