[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal–dual formulation of the problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. A non-trivial schedule is one that never runs at speed 0 when there is work remaining.

  2. For the finite number of preemptions, note that any schedule can be transformed to a highest density first (HDF) schedule (see also next paragraph), in which the number of preemptions is bounded by the number of release times. For the finite number of speed switches, consider the average speed s in any maximal execution interval of some job j (where it runs at possible different speeds). If s lies between discrete speeds \(s_i\) and \(s_{i+1}\), the schedule can be changed to run first for some time at speed \(s_{i+1}\) and then for some time at speed \(s_i\) without increasing the energy cost or the flow time.

  3. Given any non-HDF schedule, one can swap two (arbitrarily small) portions of jobs that violate HDF. By definition of the cost function, this results in a strictly better schedule.

References

  1. Albers, S.: Energy-efficient algorithms. Commun. ACM 53(5), 86–96 (2010)

    Article  Google Scholar 

  2. Albers, S., Fujiwara, H.: Energy-efficient algorithms for flow time minimization. ACM Trans. Algorithms 3(4), Art. No. 49 (2007)

  3. Andrew, L.L.H., Wierman, A., Tang, A.: Optimal speed scaling under arbitrary power functions. SIGMETRICS Perform. Eval. Rev. 37(2), 39–41 (2009)

    Article  Google Scholar 

  4. Antoniadis, A., Barcelo, N., Consuegra, M., Kling, P., Nugent, M., Pruhs, K., Scquizzato, M.: Efficient computation of optimal energy and fractional weighted flow trade-off schedules. In: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), pp. 63–74 (2014)

  5. Bansal, N., Chan, H.-L., Lam, T.W., Lee, L.-K.: Scheduling for speed bounded processors. In: Proceedings of the 35th International Conference on Automata, Languages, and Programming (ICALP), pp. 409–420 (2008)

  6. Bansal, N., Pruhs, K., Stein, C.: Speed scaling for weighted flow time. SIAM J. Comput. 39(4), 1294–1308 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bansal, N., Chan, H.-L., Pruhs, K.: Speed scaling with an arbitrary power function. ACM Trans. Algorithms 9(2), Art No. 18 (2013)

  8. Barcelo, N., Cole, D., Letsios, D., Nugent, M., Pruhs, K.: Optimal energy trade-off schedules. Sustain. Comput. Inf. Syst. 3, 207–217 (2013)

    Google Scholar 

  9. Barcelo, N., Kling, P., Nugent, M., Pruhs, K., Scquizzato, M.: On the complexity of speed scaling. In: Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 75–89 (2015)

  10. Chan, S.-H., Lam, T.W., Lee, L.-K.: Non-clairvoyant speed scaling for weighted flow time. In: Proceedings of the 18th Annual European Symposium On Algorithms (ESA), Part I, pp. 23–35 (2010)

  11. Devanur, N.R., Huang, Z.: Primal dual gives almost optimal energy efficient online algorithms. In: Proceedings of the 25th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 1123–1140 (2014)

  12. Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank, H.R. (eds.) Progress in Combinatorial Optimization, pp. 245–261. Academic Press, London (1984)

  13. Lam, T.W., Lee, L.-K., To, I.K.-K., Wong, P.W.H.: Speed scaling functions for flow time scheduling based on active job count. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pp. 647–659 (2008)

  14. Megow, N., Verschae, J.: Dual techniques for scheduling on a machine with varying speed. In: Proceedings of the 40th International Conference on Automata, Languages, and Programming (ICALP)—Volume Part I, pp. 745–756 (2013)

  15. Pruhs, K., Uthaisombut, P., Woeginger, G.J.: Getting the best response for your erg. ACM Trans. Algorithms 4(3), Art. No. 38 (2008)

Download references

Acknowledgments

The different authors (and thereby this work) were supported by: A fellowship within the Postdoc-Programme of the German Academic Exchange Service (A. Antoniadis); the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1247842 (N. Barcelo); the NSF Graduate Research Fellowship DGE-1038321 (M. Consuegra); the German Research Foundation (DFG) within the Collaborative Research Center On-The-Fly Computing (SFB 901) and by the Graduate School on Applied Network Science (P. Kling); by NSF Grants CCF-1115575, CNS-1253218, CCF-1421508, and an IBM Faculty Award (K. Pruhs); by a fellowship of Fondazione Ing. Aldo Gini, University of Padova, Italy (M. Scquizzato).

Author information

Authors and Affiliations

  1. Max-Planck Institut für Informatik, Saarbrücken, Germany

    Antonios Antoniadis

  2. Department of Computer Science, University of Pittsburgh, Pittsburgh, PA, USA

    Neal Barcelo, Michael Nugent & Kirk Pruhs

  3. Google, Seattle, WA, USA

    Mario Consuegra

  4. School of Computing Science, Simon Fraser University, Burnaby, BC, Canada

    Peter Kling

  5. Department of Computer Science, University of Houston, Houston, TX, USA

    Michele Scquizzato

Authors
  1. Antonios Antoniadis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Neal Barcelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mario Consuegra
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Peter Kling
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Michael Nugent
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Kirk Pruhs
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Michele Scquizzato
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peter Kling.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

A preliminary version of this work appeared in the Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), 2014 (see [4]).

M. Consuegra: Work done while at Florida International University.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Antoniadis, A., Barcelo, N., Consuegra, M. et al. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules. Algorithmica 79, 568–597 (2017). https://doi.org/10.1007/s00453-016-0208-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0208-x

Keywords

Search

Navigation