Task assignment with unknown duration

ABSTRACT

We consider a distributed server system and ask which policy should be used for assigning jobs (tasks) to hosts. In our server, jobs are not preemptible. Also, the job's service demand is not known a priori. We are particularly concerned with the case where the workload is heavy-tailed, as is characteristic of many empirically measured computer workloads. We analyze several natural task assignment policies and propose a new one TAGS (Task Assignment based on Guessing Size). The TAGS algorithm is counterintuitive in many respects, including load unbalancing, non-work-conserving, and fairness. We find that under heavy-tailed workloads, TAGS can outperform all task assignment policies known to us by several orders of magnitude with respect to both mean response time and mean slowdown, provided the system load is not too high. We also introduce a new practical performance metric for distributed servers called server expansion. Under the server expansion metric, TAGS significantly outperforms all other task assignment policies, regardless of system load.

REFERENCES

• 1: A. Bestavros, Load profiling: a methodology for scheduling real-time tasks in a distributed system, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.449, May 27-30, 1997
• 2: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 3: Mark E. Crovella , Mor Harchol-Balter , Cristina D. Murta, Task assignment in a distributed system (extended abstract): improving performance by unbalancing load, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.268-269, June 22-26, 1998, Madison, Wisconsin, United States
• 4: Mark E. Crovella , Murad S. Taqqu , Azer Bestavros, Heavy-tailed probability distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 5: A. B. Downey, A parallel workload model and its implications for processor allocation, Proceedings of the 6th International Symposium on High Performance Distributed Computing (HPDC '97), p.112, August 05-08, 1997
• 6: Ephremides, A., Varaiya, P., and Walrand, J. 1980. A simple dynamic routing problem. IEEE Trans. Automat. Cont. AC-25, 4, 690--693.
• 7: Dror G. Feitelson , Morris A. Jette, Improved Utilization and Responsiveness with Gang Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.238-261, April 05, 1997
• 8: Dror G. Feitelson , Larry Rudolph , Uwe Schwiegelshohn , Kenneth C. Sevcik , Parkson Wong, Theory and Practice in Parallel Job Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-34, April 05, 1997
• 9: Mor Harchol-Balter , Mark E. Crovella , Cristina D. Murta, On choosing a task assignment policy for a distributed server system, Journal of Parallel and Distributed Computing, v.59 n.2, p.204-228, Nov. 1999 [doi>10.1006/jpdc.1999.1577]
• 10: Mor Harchol-Balter , Allen B. Downey, Exploiting process lifetime distributions for dynamic load balancing, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.253-285, Aug. 1997 [doi>10.1145/263326.263344]
• 11: Irlam, G. 1994. Unix file size survey---1993. Available at http://www.base.com/gordoni/ ufs93.html.
• 12: Khinchin, A. Y. 1932. Mathematical theory of stationary queues. Mat. Sbornik 39, 73--84.
• 13: Koole, G., Sparaggis, P., and Towsley, D. 1999. Minimizing response times and queue lengths in systems of parallel queues. J. Appl. Prob. 36, 1185--1193.
• 14: Leiserson, C. 1998a. The Pleiades alpha cluster at M.I.T. Documentation at: http://bonanza.lcs. mit.edu.
• 15: Leiserson, C. 1998b. The Xolas supercomputing project at M.I.T. Documentation available at: http://xolas.lcs.mit.edu.
• 16: Will Leland , Teunis J. Ott, Load-balancing heuristics and process behavior, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.54-69, May 1986, Raleigh, North Carolina, United States
• 17: R. D. Nelson , T. K. Philips, An approximation to the response time for shortest queue routing, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.181-189, May 1989
• 18: Randolph D. Nelson , Thomas K. Philips, An approximation for the mean response time for shortest queue routing with general interarrival and service times, Performance Evaluation, v.17 n.2, p.123-139, March 1993 [doi>10.1016/0166-5316(93)90004-E]
• 19: Eric W. Parsons , Kenneth C. Sevcik, Implementing Multiprocessor Scheduling Disciplines, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.166-192, April 05, 1997
• 20: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 21: Peterson, D. L., and Adams, D. R. 1996. Fractal patterns in DASD I/O traffic. In CMG Proc.
• 22: Pollaczek, F. 1930. Uber eine aufgabe dev wahrscheinlichkeitstheorie. I-II Math. Zeitschrift. 32, 64--100.
• 23: The PSC's Cray J90's. 1998. http://www.psc.edu/machine/cray/j90/j90.html.
• 24: . Supercomputing at the NAS facility. 1998. http://www.nas.nasa.gov/Technology/Supercomputing/.
• 25: Larry Rudolph , Paul H. Smith, Valuation of Ultra-scale Computing Systems, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.39-55, May 01, 2000
• 26: Bianca Schroeder , Mor Harchol-Balter, Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness, Proceedings of the Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), p.211, August 01-04, 2000
• 27: Anees Shaikh , Jennifer Rexford , Kang G. Shin, Load-sensitive routing of long-lived IP flows, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.215-226, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 28: Sozaki, S., and Ross, R. 1978. Approximations in finite capacity multiserver queues with poisson arrivals. J. Appl. Prob. 13, 826--834.
• 29: Ward Whitt, Deciding which queue to join: Some counterexamples, Operations Research, v.34 n.1, p.55-62, Jan./Feb. 1986 [doi>10.1287/opre.34.1.55]
• 30: Winston, W. 1977. Optimality of the shortest line discipline. J. Appl. Prob. 14, 181--189.
• 31: Wolff, R. W. 1989. Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs, N.J.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory; Modeling and prediction

General Terms:
Design, Performance

Keywords:
Clusters, contrary behavior, distributed servers, fairness, heavy-tailed workloads, high variance, job scheduling, load balancing, load sharing, supercomputing, task assignment