The bell is ringing in speed-scaled multiprocessor scheduling

ABSTRACT

This paper investigates the problem of scheduling jobs on multiple speed-scaled processors without migration, i.e., we have constant α > 1 such that running a processor at speed s results in energy consumption s^#945; per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines and flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βB_α-approximation algorithm for multiple processors, where B_α is the αth Bell number, that is, the number of partitions of a set of size α. Analogously, we show that any β-competitive online algorithm for a single processor yields a βB_α-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βB_α-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. All algorithms are based on the surprising fact that we can remove migration with a blowup of B_α in expectation.

REFERENCES

• 1: Susanne Albers. Personal communication. 2008.
• 2: 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]
• 3: 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]
• 4: Nikhil Bansal, David P. Bunde, Ho-Leung Chan, and Kirk Pruhs. Average rate speed scaling. In Proceedings of 84th Latin American Symposium (LATIN'08), pages 240--251, 2008.
• 5: Nikhil Bansal , Ho-Leung Chan , Kirk Pruhs, Speed scaling with an arbitrary power function, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.693-701, January 04-06, 2009, New York, New York
• 6: 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]
• 7: Nikhil Bansal , Tracy Kimbrel , Kirk Pruhs, Speed scaling to manage energy and temperature, Journal of the ACM (JACM), v.54 n.1, p.1-39, March 2007 [doi>10.1145/1206035.1206038]
• 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, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Nonclairvoyant speed scaling for flow and energy. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS'09), pages 255--264, 2009.
• 13: G. Dobinski. Summierung der reihe Σ n^m/n! fuer m = 1, 2, 3, 4, 5, .... Arch. Math. Physik, 61:333--336, 1877.
• 14: H.W.Becker and John Riordan. The arithmetic of bell and stirling numbers. Amer. J. Math., 70:385--394, 1934.
• 15: Sandy Irani , Kirk R. Pruhs, Algorithmic problems in power management, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067324]
• 16: Tak Wah Lam, Lap-Kei Lee, Isaac Kar-Keung To, and Prudence W. H. Wong. Energy efficient deadline scheduling in two processor systems. In Proccedings of Algorithms and Computation, 18th International Symposium (ISAAC'07), pages 476--487, 2007.
• 17: Tak-Wah Lam , Lap-Kei Lee , Isaac K. K. To , Prudence W. H. Wong, Competitive non-migratory scheduling for flow time and energy, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378580]
• 18: Tak-Wah Lam , Lap-Kei Lee , Isaac K. To , Prudence W. Wong, Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_54]
• 19: László Lovász. Combinatorial problems and exercises. North-Holland, Amsterdam, 1964.
• 20: Kirk Pruhs , Patchrawat Uthaisombut , Gerhard Woeginger, Getting the best response for your erg, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008 [doi>10.1145/1367064.1367078]
• 21: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 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:
approximation algorithms, competitive analysis, dynamic speed scaling, energy minimization, online algorithms, randomized algorithms, scheduling algorithms