Analysis of cycle stealing with switching cost

ABSTRACT

We consider the scenario of two processors, each serving its own workload, where one of the processors (known as the "donor") can help the other processor (known as the "beneficiary") with its jobs, during times when the donor processor is idle. That is the beneficiary processor "steals idle cycles" from the donor processor. We assume that both donor jobs and beneficiary jobs may have generally-distributed service requirements. We assume that there is a switching cost required for the donor processor to start working on the beneficiary jobs, as well as a switching cost required for the donor processor to return to working on its own jobs. We also allow for threshold constraints, whereby the donor processor only initiates helping the beneficiary if both the donor is idle and the number of jobs at the beneficiary exceeds a certain threshold.We analyze the mean response time for the donor and beneficiary processors. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate several interesting principles with respect to the general benefits of cycle stealing and the design of cycle stealing policies.

REFERENCES

• 1: Sem Borst , Onno Boxma , Predrag Jelenković, Reduced-Load Equivalence and Induced Burstiness in GPS Queues with Long-Tailed Traffic Flows, Queueing Systems: Theory and Applications, v.43 n.4, p.273-306, April 2003 [doi>10.1023/A:1023237129453]
• 2: Sem Borst , Onno Boxma , Miranda Van Uitert, The Asymptotic Workload Behavior of Two Coupled Queues, Queueing Systems: Theory and Applications, v.43 n.1-2, p.81-102, January-February 2003
• 3: J. Cohen and O. Boxma. Boundary Value Problems in Queueing System Analysis. North-Holland Publ. Cy., 1983.
• 4: G. Fayolle and R. Iasnogorodski. Two coupled processors: the reduction to a Riemann-Hilbert problem. Zeitschrift fur Wahrscheinlichkeitstheorie und vervandte Gebiete, 47:325--351, 1979.
• 5: Mor Harchol-Balter , Cuihong Li , Takayuki Osogami , Alan Scheller-Wolf , Mark S. Squillante, Cycle stealing under immediate dispatch task assignment, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777462]
• 6: A. Konheim, I. Meilijson, and A. Melkman. Processor-sharing of two parallel lines. Journal of Applied Probability, 18:952--956, 1981.
• 7: G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM, Philadelphia, 1999.
• 8: M. F. Neuts. Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, 1981.
• 9: T. Osogami and M. Harchol-Balter. Necessary and sufficient conditions for representing general distributions by Coxians. Technical Report CMU-CS-02-178, School of Computer Science, Carnegie Mellon University, September 2002.
• 10: T. Osogami, M. Harchol-Balter, and A. Sheller-Wolf. Analysis of cycle stealing with switching cost. Technical Report CMU-CS-02-192, School of Computer Science, Carnegie Mellon University, October 2002.
• 11: Mark S. Squillante , Randolph D. Nelson, Analysis of task migration in shared-memory multiprocessor scheduling, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.143-155, May 21-24, 1991, San Diego, California, United States
• 12: H. Takagi. Queueing Analysis -- A Foundation of Performance Evaluation, volume 1: Vacation and Priority Systems, Part 1. North Holland, 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Performance

Keywords:
cycle stealing, distributed system, load sharing, matrix analytic, server farm, starvation, supercomputing, task assignment, unfairness