Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines

Published: 01 May 2015 Publication History

Abstract

In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of $$s^\alpha $$ s when running at speed $$s$$ s , where $$\alpha \ge 2$$ 2 . The problem is to dispatch jobs to processors and determine the speed and jobs to run for each processor so as to complete all jobs by their deadlines using the minimum energy. The problem has been well studied for the single processor case. For the multiprocessor setting, constant competitive online algorithms for special cases of unit size jobs or arbitrary size jobs with agreeable deadlines have been proposed by Albers et al. ( 2007 ). A randomized algorithm has been proposed for jobs of arbitrary sizes and arbitrary deadlines by Greiner et al. ( 2009 ). We propose a deterministic online algorithm for the general setting and show that it is $$O(\log ^\alpha P)$$ O ( log P ) -competitive, where $$P$$ P is the ratio of the maximum and minimum job size.

References

[1]
Albers S (2009) Algorithms for energy saving. In: Albers S, Alt H, Näher S (eds.) Efficient algorithms, lecture notes in computer science. vol. 5760, pp. 173-186. Springer, Berlin.
[2]
Albers S (2010) Energy-efficient algorithms. Commun ACM 53(5):86-96.
[3]
Albers S, Antoniadis A (2012) Race to idle: new algorithms for speed scaling with a sleep state. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1266-1285.
[4]
Albers S, Antoniadis A, Greiner G (2011) On multi-processor speed scaling with migration: extended abstract. In: Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 279-288.
[5]
Albers S, Fujiwara H (2007) Energy-efficient algorithms for flow time minimization. ACM Trans Algorithms 3(4):49.
[6]
Albers S, Müller F, Schmelzer S (2007) Speed scaling on parallel processors. In: Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 289-298.
[7]
Angel E, Bampis E, Kacem F, Letsios D (2012) Speed scaling on parallel processors with migration. In: Proceedings of International Conference Euro-Par 2012 Parallel Processing, pp. 128-140.
[8]
Antoniadis A, Huang CC (2012) Non-preemptive speed scaling. In: Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 249-260.
[9]
Bampis E, Letsios D, Milis I, Zois G (2012) Speed scaling for maximum lateness. In: Proceedings of Annual International Computing and Combinatorics Conference (COCOON). To appear.
[10]
Bansal N, Chan HL, Lam TW, Lee LK (2008) Scheduling for speed bounded processors. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pp. 409-420.
[11]
Bansal N, Chan HL, Pruhs K (2009a) Speed scaling with an arbitrary power function. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 693-701.
[12]
Bansal N, Chan HL, Pruhs K, Rogozhnikov-Katz D (2009b) Improved bounds for speed scaling in devices obeying the cube-root rule. In: Proceedings of International Colloquium on Automata, Languages and-Programming (ICALP), pp. 114-155.
[13]
Bansal N, Kimbrel T, Pruhs K (2007) Speed scaling to manage energy and temperature. J ACM 54(1):3.
[14]
Bansal N, Pruhs K, Stein C (2009c) Speed scaling for weighted flow time. SIAM J Comput 39(4), 1294-1308. Preliminary version appeared in Proceedings of Symposium on Discrete Algorithms (SODA), pages 805-813, 2007.
[15]
Becker HW, Riordan J (1948) The arithmetic of Bell and Stirling numbers. Am J Math 70:385-394.
[16]
Bingham BD, Greenstreet MR (2008) Energy optimal scheduling on multiprocessors with migration. In: Proceedings of IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA), pp. 153-161.
[17]
Brooks DM, Bose P, Schuster SE, Jacobson H, Kudva PN, Buyuktosunoglu A, Wellman JD, Zyuban V, Gupta M, Cook PW (2000) Power-aware microarchitecture: design and modeling challenges for next-generation microprocessors. IEEE Micro 20(6):26-44.
[18]
Chan HL, Chan WT, Lam TW, Lee LK, Mak KS, Wong PWH (2009) Optimizing throughput and energy in online deadline scheduling. ACM Trans Algorithms 6(1), 10. Preliminary version appeared in Proceedings of Symposium on Discrete Algorithms (SODA), pages 795-804, 2007.
[19]
Chan SH, Lam TW, Lee LK (2011) Scheduling for weighted flow time and energy with rejection penalty. In: Proceedings of International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 392-403.
[20]
Chan SH, Lam TW, Lee LK, Liu CM, Ting HF (2011) Sleep management on multiple machines for energy and flow time. In: Proceedings of International Colloquium on Automata, Lanaguages and Programming (ICALP), pp. 219-231.
[21]
Cole D, Im S, Moseley B, Pruhs K (2012) Speed scaling for stretch plus energy. Oper Res Lett 40(3):180-184.
[22]
Greiner G, Nonner T, Souza A (2009) The bell is ringing in speed-scaled multiprocessor scheduling. In: Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 11-18.
[23]
Gupta A, Krishnaswamy R, Pruhs K (2010) Scalably scheduling power-heterogeneous processors. In: Proceedings of International Colloquium on Automata, Lanaguages and Programming (ICALP), pp. 312-323.
[24]
Han X, Lam TW, Lee LK, To IKK, Wong PWH (2010) Deadline scheduling and power management for speed bounded processors. Theor Comput Sci 411(40-42):3587-3600.
[25]
Irani S, Pruhs K (2005) Algorithmic problems in power management. ACM SIGACT News 32(2):63-76.
[26]
Irani S, Shukla S, Gupta RK (2007) Algorithms for power savings. ACM Trans Algorithms 3(4):41.
[27]
Lam TW, Lee LK, Ting HF, To IKK, Wong PWH (2009) Sleep with guilt and work faster to minimize flow plus energy. In: Proceedings of International Colloquium on Automata, Lanaguages and Programming (ICALP), pp. 665-676.
[28]
Lam TW, Lee LK, To IKK, Wong PWH (2007) Energy efficient deadline scheduling in two processor systems. In: Proceedings of the International Symposium of Algorithms and Computation (ISAAC), pp. 476-487.
[29]
Lam TW, Lee LK, To IKK, Wong PWH (2008) Speed scaling functions for flow time scheduling based on active job count. In: Proceedings of European Symposium on Algorithms (ESA), pp. 647-659.
[30]
Lam TW, Lee LK, To IKK, Wong PWH (2012) Improved multi-processor scheduling for flow time and energy. J Sched 15(1), 105-116. Preliminary version appeared in Proceedings of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 256-264, 2008.
[31]
Mudge T (2001) Power: a first-class architectural design constraint. Computer 34(4):52-58.
[32]
Pruhs K, van Stee R, Uthaisombut P (2005) Speed scaling of tasks with precedence constraints. In: Proceedings of International Workshop on Approximation and Online Algorithms (WAOA), pp. 307-319.
[33]
Yao F, Demers A, Shenker S (1995) A scheduling model for reduced CPU energy. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 374-382.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization
Journal of Combinatorial Optimization  Volume 29, Issue 4
May 2015
199 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 2015

Author Tags

  1. Competitive analysis
  2. Deadline scheduling
  3. Dynamic speed scaling
  4. Multiprocessor scheduling
  5. Online algorithms

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 04 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Competitive algorithms for demand response management in a smart gridJournal of Scheduling10.1007/s10951-021-00690-x26:6(535-542)Online publication date: 1-Dec-2023
  • (2020)Non-preemptive Scheduling in a Smart Grid Model and Its Implications on Machine MinimizationAlgorithmica10.1007/s00453-020-00733-382:12(3415-3457)Online publication date: 1-Dec-2020
  • (2017)Executed-time Round RobinJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2016.03.00229:1(74-84)Online publication date: 1-Jan-2017
  • (2017)Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous ProcessorsCombinatorial Optimization and Applications10.1007/978-3-319-71147-8_32(457-465)Online publication date: 16-Dec-2017
  • (2016)Scheduling for electricity cost in a smart gridJournal of Scheduling10.1007/s10951-015-0447-819:6(687-699)Online publication date: 1-Dec-2016

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media