Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Power-aware speed scaling in multiprocessor systems

© The Institution of Engineering and Technology
Received 02/09/2016, Accepted 14/08/2017, Revised 07/08/2017, Published 15/08/2017

A huge consumption of energy in the data centres has become a motivation for improvement in computing capability and energy conservation. The dynamic speed scaling and job scheduling are efficient methods to improve the energy efficiency of processors. In this study, an online non-clairvoyant scheduling algorithm arrival time-algorithm (At-ALG) is proposed with an objective to scale the speed of processors and schedule the jobs in a multiprocessor system to minimise the total magnitude-based/weighted flow time plus energy consumed. The traditional power function is adopted, where is a constant. At-ALG is analysed, against an offline adversary, using the potential function analysis. The magnitude/weight/priority of jobs in At-ALG are generated using their processed time (waiting time plus executed time) and speed of any processor depends on the number of active jobs plus sum of processed time of active jobs. At-ALG is -competitive with no resource augmentation.

Inspec keywords: processor scheduling; energy conservation; multiprocessing systems; power consumption

Other keywords: potential function analysis; power-aware speed scaling; dynamic speed scaling; multiprocessor systems; power function; online nonclairvoyant scheduling algorithm arrival time-algorithm; energy efficiency; job scheduling

Subjects: Parallel programming and algorithm theory; Distributed systems software; Multiprocessing systems

References

    1. 1)
      • 9. Andrew, L., Wierman, A., Tang, A.: ‘Optimal speed scaling under arbitrary power functions’, ACM SIGMETRICS Perform. Eval. Rev., 2009, 37, (2), pp. 39–41.
    2. 2)
      • 20. Singh, P., Hailu, N.: ‘An energy-aware online non-clairvoyant multiprocessor scheduling: multiprocessor priority round robin (MPRR)’, IET Comput. Digit. Tech., 2016, 11, (1), pp. 16–23, doi: 10.1049/iet-cdt.2016.0097.
    3. 3)
      • 13. Chan, S.H., Lam, T.W., Lee, L.K.: ‘Scheduling for weighted flow time and energy with rejection penalty’. Proc. of Symp. on Theoretical Aspects of Computer Science, Dortmund, Germany, 2011, pp. 392–403.
    4. 4)
      • 15. Chan, H.L., Edmonds, J., Lam, T.W., et al: ‘Nonclairvoyant speed scaling for flow and energy’, Algorithmica, 2011, 61, (3), pp. 507–517.
    5. 5)
      • 16. Chan, S.H., Lam, T.W., Lee, L.K., et al: ‘Nonclairvoyant sleep management and flow-time scheduling on multiple processors’. Proc. Annual ACM Symp. on Parallelism in Algorithms and Architectures, Montreal, QC, Canada, 2013, pp. 261–270.
    6. 6)
      • 21. Chan, S.H, Lam, T.W., Lee, K.L.: ‘Non-clairvoyant speed scaling for weighted flow time’. Proc. Annual European Symp., Liverpool, UK, 2010, pp. 23–35.
    7. 7)
      • 12. Chan, H.L., Chan, S.H., Lam, T.W.: ‘Competitive online algorithms for multiple-machine power management and weighted flow time’. Proc. of the Nineteenth Computing: The Australasian Theory Symp., Adelaide, Australia, 2013, pp. 11–20.
    8. 8)
      • 17. Chan, S.H., Lam, T.W., Lee, L.K., et al: ‘Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors’. Proc. of Computing: The Australasian Theory Symposium, Brisbane, Australia, 2010, pp. 3–10.
    9. 9)
      • 19. Singh, P., Wolde-Gabriel, B.: ‘Executed-time round robin: EtRR an online non-clairvoyant scheduling on speed bounded processor with energy management’, J. King Saud. Univ., Comput. Inf. Sci., 2016, 29, (1), pp. 74–84, http://dx.doi.org/10.1016/j.jksuci.2016.03.002.
    10. 10)
      • 8. Bansal, N., Chan, H.L., Lam, T.W., et al: ‘Scheduling for speed bounded processors’. Proc. Int. Colloquium on Automata, Languages and Programming, Reykjavík, Iceland, 2008, pp. 409–420.
    11. 11)
      • 6. Kalyanasundaram, B., Pruhs, K.: ‘Speed is as powerful as clairvoyant’, J. ACM, 2000, 47, (4), pp. 617–643.
    12. 12)
      • 3. Yao, F., Demers, A., Shenker, S.: ‘A scheduling model for reduced CPU energy’. Proc. Annual Symp. on Foundations of Computer Science, Milwaukee, WI, USA, 23–25 October, 1995, pp. 374–382.
    13. 13)
      • 22. Fox, K., Im, S., Moseley, B.: ‘Energy efficient scheduling of parallelizable jobs’. Proc. of the Annual Symp. on Discrete Algorithms, New Orleans, LA, USA, 2013, pp. 948–957.
    14. 14)
      • 2. Gupta, A., Krishnaswamy, R., Pruhs, K.: ‘Scalably scheduling power-heterogeneous processors’. Proc. Int. Colloquium on Automata, Languages and Programming, Bordeaux, France, 2010, pp. 312–323.
    15. 15)
      • 18. Singh, P., Prashast, : ‘Release round robin: R3 an energy-aware non-clairvoyant scheduling on speed bounded processors’, Karbala Int. J. Mod. Sci., 2015, 1, (4), pp. 225–236.
    16. 16)
      • 10. Bansal, N., Pruhs, K., Stein, C.: ‘Speed scaling for weighted flow time’, SIAM J. Comput., 2009, 39, (4), pp. 1294–1308.
    17. 17)
      • 14. Gupta, A., Krishnaswamy, R., Pruhs, K.: ‘Nonclairvoyantly scheduling power-heterogeneous processors’. Proc. of Int. Green Computing Conf., Chicago, IL, USA, 2010, pp. 165–173.
    18. 18)
      • 4. Albers, S., Fujiwara, H.: ‘Energy-efficient algorithms for flow time minimization’, ACM Trans. Algorithms, 2007, 3, (4), pp. 1–17, No. – 49.
    19. 19)
      • 11. Durr, C., Jez, L., Vasquez, O.C.: ‘Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption’, Discrete Appl. Math., 2014, 196, pp. 20–29.
    20. 20)
      • 1. Koomey, J.G.: ‘Worldwide electricity used in data centers’, Environ. Res. Lett., 2008, 3, (3), pp. 1–8, doi: 10.1088/1748-9326/3/3/034008.
    21. 21)
      • 23. Im, S., Kulkarni, J., Munagala, K.: ‘Selfishmigrate: a scalable algorithm for non-clairvoyantly scheduling heterogeneous processors’. Proc. of the IEEE Annual Symp. on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 531–540.
    22. 22)
      • 5. Chan, H.L., Edmonds, J., Lam, T.W., et al: ‘Nonclairvoyant speed scaling for flow and energy’. Proc. Int. Symp. on Theoretical Aspects of Computer Science, Freiburg, Germany, 2009, pp. 255–264.
    23. 23)
      • 7. Lam, T.W., Lee, L.K., To, I.K.K., et al: ‘Online speed scaling based on active job count to minimize flow plus energy’, Algorithmica, 2013, 65, (3), pp. 605–633.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-smt.2016.0365
Loading

Related content

content/journals/10.1049/iet-smt.2016.0365
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address