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

access icon free HEALERS: a heterogeneous energy-aware low-overhead real-time scheduler

© The Institution of Engineering and Technology
Received 31/01/2019, Accepted 11/06/2019, Revised 20/05/2019, Published 12/06/2019

Devising energy-efficient scheduling strategies for real-time periodic tasks on heterogeneous platforms is a challenging as well as a computationally demanding problem. This study proposes a low-overhead heuristic strategy called, HEALERS, for dynamic voltage and frequency scaling (DVFS)-cum-dynamic power management (DPM) enabled energy-aware scheduling of a set of periodic tasks executing on a heterogeneous multi-core system. The presented strategy first applies deadline-partitioning to acquire a set of distinct time-slices. At any time-slice boundary, the following three-phase operations are applied to obtain a schedule for the next time-slice: first, it computes the fragments of the execution demands of all tasks onto each of the different processing cores in the platform. Next, it generates a schedule for each task on one or more processing cores such that the total execution demand of all tasks is satisfied. Finally, HEALERS applies DVFS and DPM on all processing cores so that energy consumption within the time-slice may be minimized while not jeopardising execution requirements of the scheduled tasks. Experimental results show that the proposed scheme is not only able to achieve appreciable energy savings with respect to state-of-the-art (5–42% on average) but also enables a significant improvement in resource utilisation (as high as 58%).

Inspec keywords: multiprocessing systems; processor scheduling; power consumption; power aware computing; real-time systems

Other keywords: heterogeneous multicore system; total execution demand; low-overhead heuristic strategy; HEALERS; execution requirements; real-time periodic tasks; dynamic voltage and frequency scaling; DPM; heterogeneous platforms; scheduled tasks; time-slice boundary; real-time energy-aware scheduling techniques; energy consumption; energy-efficient scheduling strategies; energy savings; heterogeneous energy-aware real-time scheduler; DVFS; execution demands

Subjects: Performance evaluation and testing; Multiprocessing systems

References

    1. 1)
      • 2. Davis, R.I., Burns, A.: ‘A survey of hard real-time scheduling for multiprocessor systems’, ACM Comput. Surv., 2011, 43, (4), pp. 1–44.
    2. 2)
      • 36. Moulik, S., Devaraj, R., Sarkar, A.: ‘Heart: a heterogeneous energy-aware real-time scheduler’. 2019 32nd Int. Conf. on VLSI Design and 2019 18th Int. Conf. on Embedded Systems (VLSID), New Delhi, India, 2019.
    3. 3)
      • 25. Ejlali, A., Al Hashimi, B.M., Eles, P.: ‘A standby-sparing technique with low energy-overhead for fault-tolerant hard real-time systems’. Proc. of the 7th IEEE/ACM int. Conf. on Hardware/software codesign and system synthesis, Grenoble, France, ACM, 2009, pp. 193–202.
    4. 4)
      • 11. Shin, Y., Choi, K., Sakurai, T.: ‘Power optimization of real-time embedded systems on variable speed processors’. Proc. of the 2000 IEEE/ACM Int. Conf. on Computer-aided Design. ICCAD'00, IEEE Press, Piscataway, NJ, USA, 2000, pp. 365–368.
    5. 5)
      • 28. wen Zhang, Y.: ‘Energy-aware mixed partitioning scheduling in standby-sparing systems’, Comput. Stand. Interfaces, 2019, 61, pp. 129–136.
    6. 6)
      • 7. Lawler, E.L., Labetoulle, J.: ‘On preemptive scheduling of unrelated parallel processors by linear programming’, J. ACM, 1978, 25, (4), pp. 612–619.
    7. 7)
      • 15. University, P.: ‘Princeton application repository for shared-memory computers (PARSEC)’, http://parseccsprincetonedu.
    8. 8)
      • 32. Li, K., Tang, X., Yin, Q.: ‘Energy aware scheduling algorithm for task execution cycles with normal distribution on heterogeneous computing systems’. 2012 41st Int. Conf. on Parallel Processing, Pittsburgh, PA, USA, 2012, pp. 40–47.
    9. 9)
      • 40. Binkert, N., Sardashti, S., Sen, R., et al: ‘The gem5 simulator’, ACM SIGARCH Comput. Archit. News, 2011, 39, (2), pp. 1–7.
    10. 10)
      • 24. Chen, G., Huang, K., Knoll, A.: ‘Abstract: energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination’. The 11th IEEE Symp. on Embedded Systems for Real-time Multimedia, Montreal, QC, Canada, 2013, p. 40.
    11. 11)
      • 12. Moulik, S., Sarkar, A., Kapoor, H.K.: ‘Energy aware frame based fair scheduling’, Sust. Comput., Inf. Syst., 2018, 18, pp. 66–77.
    12. 12)
      • 16. Gustafsson, J., Betts, A., Ermedahl, A., et al: ‘The Mälardalen WCET benchmarks – past, present and future’ (Brussels, Belgium: OCG, 2010), pp. 137–147.
    13. 13)
      • 41. Bastoni, A., Brandenburg, B.B., Anderson, J.H.: ‘Cache-related preemption and migration delays: empirical approximation and impact on schedulability’. 6th Int. Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Brussels, Belgium, 2010.
    14. 14)
      • 19. Baruah, S.K., Bonifaci, V., Bruni, R., et al: ‘ILP-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors’. 28th Euromicro Conf. on Real- Time Systems (ECRTS), IEEE, Toulouse, France, 2016, pp. 215–225.
    15. 15)
      • 14. Awan, M.A., Yomsi, P.M., Nelissen, G., et al: ‘Energy-aware task mapping onto heterogeneous platforms using DVFS and sleep states’, Real-Time Syst., 2016, 52, (4), pp. 450–485.
    16. 16)
      • 27. Guo, Y., Zhu, D., Aydin, H.: ‘Generalized standby-sparing techniques for energy-efficient fault tolerance in multiprocessor real-time systems’, 2013 IEEE 19th Int. Conf. on Embedded and Real-Time Computing Systems and Applications (RTCSA), IEEE, Taipei, Taiwan, 2013, pp. 62–71.
    17. 17)
      • 5. Anderson, J.H., Srinivasan, A.: ‘Early-release fair scheduling’. 12th Euromicro Conf. on Real-Time Systems, IEEE, Stockholm, Sweden, 2000, pp. 35–43.
    18. 18)
      • 9. Jha, N.K.: ‘Low power system scheduling and synthesis’. Proc. of the 2001 IEEE/ACM Int. Conf. on Computer-aided Design. ICCAD'01, IEEE Press, Piscataway, NJ, USA, 2001, pp. 259–263.
    19. 19)
      • 18. Raravi, G., Andersson, B., Nélis, V., et al: ‘Task assignment algorithms for two-type heterogeneous multiprocessors’, Real-Time Syst., 2014, 50, (1), pp. 87–141.
    20. 20)
      • 26. Haque, M.A., Aydin, H., Zhu, D.: ‘Energy-aware standby-sparing technique for periodic real-time applications’. Computer Design (ICCD), 2011 IEEE 29th Int. Conf. on., IEEE, Amherst, MA, USA, 2011, pp. 190–197.
    21. 21)
      • 8. Chwa, H.S., Seo, J., Lee, J., et al: ‘Optimal real-time scheduling on two-type heterogeneous multicore platforms’. Real-Time Systems Symp., San Antonio, TX, USA, 2015, pp. 119–129.
    22. 22)
      • 29. Moghaddas, V., Fazeli, M., Patooghy, A.: ‘Reliability-oriented scheduling for static-priority real-time tasks in standby-sparing systems’, Microprocess. Microsyst., 2016, 45, pp. 208–215.
    23. 23)
      • 23. Bhatti, M.K., Belleudy, C., Auguin, M.: ‘An inter-task real time DVFS scheme for multiprocessor embedded systems’. 2010 Conf. on Design and Architectures for Signal and Image Processing (DASIP), Edinburgh, UK, 2010, pp. 136–143.
    24. 24)
      • 20. Moulik, S., Devaraj, R., Sarkar, A.: ‘HETERO-SCHED: a low-overhead heterogeneous multi-core scheduler for real-time periodic tasks’. 2018 IEEE 20th Int. Conf. on High Performance Computing and Communications; IEEE 16th Int. Conf. on Smart City; IEEE 4th Int. Conf. on Data Science and Systems (HPCC/SmartCity/DSS), Exeter, UK, 2018, pp. 659–666.
    25. 25)
      • 38. Malkevitch, J.: ‘Bin packing and machine scheduling’ (American Mathematical Society Providence, RI, USA, 2004).
    26. 26)
      • 1. Buttazzo, G.: ‘Hard real-time computing systems: predictable scheduling algorithms and applications’ (Springer, Basel, Switzerland, 2011).
    27. 27)
      • 21. Sheikh, S.Z., Pasha, M.A.: ‘Energy-efficient multicore scheduling for hard real-time systems: a survey’, ACM Trans. Embedded Comput. Syst., 2019, 17, (6), pp. 1–26.
    28. 28)
      • 34. Martin, S.M., Flautner, K., Mudge, T., et al: ‘Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads’. Proc. of the 2002 IEEE/ACM Int. Conf. on Computer-aided Design. ICCAD ‘02, ACM, New York, NY, USA, 2002, pp. 721–725.
    29. 29)
      • 4. Baruah, S.K., Cohen, N.K., Plaxton, C.G., et al: ‘Proportionate progress: a notion of fairness in resource allocation’, Algorithmica, 1996, 15, (6), pp. 600–625.
    30. 30)
      • 22. Bambagini, M., Marinoni, M., Aydin, H., Buttazzo, G.: ‘Energy-aware scheduling for real-time systems: a survey’, ACM Trans. Embedded Comput. Syst. (TECS), 2016, 15, (1), p. 7.
    31. 31)
      • 31. Awan, M.A., Petters, S.M.: ‘Energy-aware partitioning of tasks onto a heterogeneous multi-core platform’. 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symp. (RTAS), Philadelphia, PA, USA, 2013, pp. 205–214.
    32. 32)
      • 33. Wang, W., Mishra, P.: ‘Leakage-aware energy minimization using dynamic voltage scaling and cache reconfiguration in real-time systems’. 2010 23rd Int. Conf. on VLSI Design, Bangalore, India, 2010. pp. 357–362.
    33. 33)
      • 37. Baruah, S., Carpenter, J.: ‘Multiprocessor fixed-priority scheduling with restricted interprocessor migrations’. Proc. of the 15th Euromicro Conf. on Real-Time Systems, Porto, Portugal, 2003, pp. 195–202.
    34. 34)
      • 13. Moulik, S., Sarkar, A., Kapoor, H.K.: ‘DPFair scheduling with slowdown and suspension’. 2018 31st Int. Conf. on VLSI Design and 2018 17th Int. Conf. on Embedded Systems (VLSID), Pune, India, 2018, pp. 43–48.
    35. 35)
      • 3. Baruah, S., Bertogna, M., Buttazzo, G.: ‘Multiprocessor scheduling for real-time systems’ (Springer Nature, Switzerland2015).
    36. 36)
      • 10. Augustine, J., Irani, S., Swamy, C.: ‘Optimal power-down strategies’, SIAM J. Comput., 2008, 37, (5), pp. 1499–1516.
    37. 37)
      • 35. Jejurikar, R., Pereira, C., Gupta, R.: ‘Leakage aware dynamic voltage scaling for real-time embedded systems’. Proc. of the 41st. Design Automation Conf., 2004., San Diego, CA, USA, 2004, pp. 275–280.
    38. 38)
      • 39. Bygde, S., Ermedahl, A., Lisper, B.: ‘An efficient algorithm for parametric WCET calculation’. 2009 15th IEEE Int. Conf. on Embedded and Real-Time Computing Systems and Applications, Beijing, China, 2009, pp. 13–21.
    39. 39)
      • 6. Funk, S., Levin, G., Sadowski, C., et al: ‘DP-fair: a unifying theory for optimal hard real-time multiprocessor scheduling’, Real-Time Syst., 2011, 47, (5), pp. 389–429.
    40. 40)
      • 30. Tosun, S.: ‘Energy- and reliability-aware task scheduling onto heterogeneous MPSoC architectures’, J. Supercomput., 2012, 62, (1), pp. 265–289.
    41. 41)
      • 17. Anderson, J.H., Srinivasan, A.: ‘Mixed Pfair/ERfair scheduling of asynchronous periodic tasks’. Proc. 13th Euromicro Conf. on Real-Time Systems, Delft, The Netherlands, 2001, pp. 76–85.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2019.0023
Loading

Related content

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