Speed scaling of processes with arbitrary speedup curves on a multiprocessor

ABSTRACT

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the jobs to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. For jobs that may have side effects or that are not checkpointable, we show an Ω(m(α--1)/α2) bound on the competitive ratio of any deterministic algorithm. Here m is the number of processors and α is the exponent of the power function. For checkpointable jobs without side effects, we give an O(log m)-competitive algorithm. Thus for jobs that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable jobs without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/α m) on the competitive ratio of any algorithm for checkpointable jobs without side effects. Finally we slightly improve the upper bound on the competitive ratio for the single processor case, which is equivalent to the case that all jobs are fully parallelizable, by giving an improved analysis of a previously proposed algorithm.

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: Nikhil Bansal , Ho-Leung Chan , Tak-Wah Lam , Lap-Kei Lee, Scheduling for Speed Bounded Processors, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_34]
• 3: Nikhil Bansal , Ho-Leung Chan , Kirk Pruhs , Dmitriy Katz, Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule, Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, July 05-12, 2009, Rhodes, Greece [doi>10.1007/978-3-642-02927-1_14]
• 4: 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
• 5: 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]
• 6: 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
• 7: 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
• 8: Luca Becchetti , Stefano Leonardi, Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines, Journal of the ACM (JACM), v.51 n.4, p.517-539, July 2004 [doi>10.1145/1008731.1008732]
• 9: Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Online weighted flow time and deadline scheduling. J. Discrete Algorithms, 4(3):339--352, 2006.
• 10: Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marcheti-Spaccamela, and Kirk Pruhs. Nonclairvoyant speed scaling for flow and energy. In STACS, pages 255--264, 2009.
• 11: Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
• 12: Jeff Edmonds. On the competitiveness of AIMD-TCP within a general network. In LATIN, pages 577--588, 2004.
• 13: Jeff Edmonds , Suprakash Datta , Patrick Dymond, TCP is competitive against a limited adversary, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777440]
• 14: Jeff Edmonds , Kirk Pruhs, Scalably scheduling processes with arbitrary speedup curves, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.685-692, January 04-06, 2009, New York, New York
• 15: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 16: Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July 2003 [doi>10.1145/792538.792545]
• 17: 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]
• 18: Rick Merritt. Cpu designers debate multi-core future. EE Times, June 2008.
• 19: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 20: Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007 [doi>10.1145/1243401.1243411]
• 21: Kirk Pruhs, Jiri Sgall, and Eric Torng. Online scheduling. In Handbook on Scheduling. CRC Press, 2004.
• 22: 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]
• 23: Julien Robert and Nicolas Schabanel. Non-clairvoyant batch sets scheduling: Fairness is fair enough. In European Symposium on Algorithms, pages 741--753, 2007.
• 24: Julien Robert , Nicolas Schabanel, Non-clairvoyant scheduling with precedence constraints, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.491-500, January 20-22, 2008, San Francisco, California

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance, Theory

Keywords:
scheduling, speed scaling