Competitive non-migratory scheduling for flow time and energy

ABSTRACT

Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14].

The above result stems from an interesting observation that there always exists some optimal migratory schedule S that can be converted (in an offline sense) to a non-migratory schedule S' with a moderate increase in flow time plus energy. More importantly, this non-migratory schedule always dispatches jobs in the same way as CRR.

REFERENCES

• 1: Susanne Albers , Hiroshi Fujiwara, Energy-efficient algorithms for flow time minimization, ACM Transactions on Algorithms (TALG), v.3 n.4, p.49-es, November 2007 [doi>10.1145/1290672.1290686]
• 2: Susanne Albers , Fabian Müller , Swen Schmelzer, Speed scaling on parallel processors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248424]
• 3: John Augustine , Sandy Irani , Chaitanya Swamy, Optimal Power-Down Strategies, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.530-539, October 17-19, 2004 [doi>10.1109/FOCS.2004.50]
• 4: Nir Avrahami , Yossi Azar, Minimizing total flow time and total completion time with immediate dispatching, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777415]
• 5: Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the Flow Time Without Migration, SIAM Journal on Computing, v.31 n.5, p.1370-1382, 2002 [doi>10.1137/S009753970037446X]
• 6: N. Bansal, H. L. Chan, T. W. Lam, and L. K. Lee. Scheduling for speed bounded processors. To appear in Proc. ICALP, 2008.
• 7: Nikhil Bansal , Tracy Kimbrel , Kirk Pruhs, Dynamic Speed Scaling to Manage Energy and Temperature, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.520-529, October 17-19, 2004 [doi>10.1109/FOCS.2004.24]
• 8: Nikhil Bansal , Kirk Pruhs , Cliff Stein, Speed scaling for weighted flow time, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.805-813, January 07-09, 2007, New Orleans, Louisiana
• 9: David M. Brooks , Pradip Bose , Stanley E. Schuster , Hans Jacobson , Prabhakar N. Kudva , Alper Buyuktosunoglu , John-David Wellman , Victor Zyuban , Manish Gupta , Peter W. Cook, Power-Aware Microarchitecture: Design and Modeling Challenges for Next-Generation Microprocessors, IEEE Micro, v.20 n.6, p.26-44, November 2000 [doi>10.1109/40.888701]
• 10: David P. Bunde, Power-aware scheduling for makespan and flow, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148140]
• 11: Ho-Leung Chan , Wun-Tat Chan , Tak-Wah Lam , Lap-Kei Lee , Kin-Sum Mak , Prudence W. H. Wong, Energy efficient online deadline scheduling, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.795-804, January 07-09, 2007, New Orleans, Louisiana
• 12: Ho-Leung Chan , Tak-Wah Lam , Kar-Keung To, Nonmigratory Online Deadline Scheduling on Multiprocessors, SIAM Journal on Computing, v.34 n.3, p.669-682, 2005 [doi>10.1137/S0097539703435765]
• 13: Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
• 14: Chandra Chekuri , Ashish Goel , Sanjeev Khanna , Amit Kumar, Multi-processor scheduling to minimize flow time with ε resource augmentation, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007411]
• 15: Dirk Grunwald , Charles B. Morrey, III , Philip Levis , Michael Neufeld , Keith I. Farkas, Policies for dynamic clock scheduling, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.6-6, October 22-25, 2000, San Diego, California
• 16: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 18: Bala Kalyanasundaram , Kirk R. Pruhs, Eliminating migration in multi-processor scheduling, Journal of Algorithms, v.38 n.1, p.2-24, Jan. 2001 [doi>10.1006/jagm.2000.1128]
• 19: Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
• 20: M. Li, B. J. Liu, and F. F. Yao. Min-energy voltage allocations for tree-structured tasks. In Proc. COCOON, pages 283--296, 2005.
• 21: Jason McCullough , Eric Torng, SRPT optimally utilizes faster machines to minimize flow time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 22: Trevor Mudge, Power: A First-Class Architectural Design Constraint, Computer, v.34 n.4, p.52-58, April 2001 [doi>10.1109/2.917539]
• 23: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
• 24: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 25: K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In J. Leung, editor, Handbook of Scheduling: Algorithms, Models and Performance Analysis, pages 15--1--15-41. CRC Press, 2004.
• 26: K. Pruhs, R. van Stee, and P. Uthaisombut. Speed scaling of tasks with precedence constraints. In Proc. WAOA, pages 307--319, 2005.
• 27: K. Pruhs, P. Uthaisombut, and G. Woeginger. Getting the best response for your erg. In Proc. SWAT, pages 14--25, 2004.
• 28: Mark Weiser , Brent Welch , Alan Demers , Scott Shenker, Scheduling for reduced CPU energy, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.2-es, November 14-17, 1994, Monterey, California
• 29: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
competitive analysis, dynamic speed scaling, energy minimization, online scheduling algorithms