Scheduling algorithms to reduce the static energy consumption of real-time systems

详细信息    查看全文

• 作者：Vincent Legout (1) (2)
  Mathieu Jan (2)
  Laurent Pautet (3)
  
  1. Department of Electrical and Computer Engineering ; Virginia Tech ; Virginia ; USA
  2. CEA ; LIST ; Embedded Real Time Systems Laboratory ; 91191 ; Gif-sur-Yvette ; France
  3. Institut TELECOM ParisTech ; LTCI-UMR 5141 ; Paris ; France
  
• 关键词：Multiprocessor scheduling ; Static consumption ; Hard real ; time ; Mixed ; criticality
• 刊名：Real-Time Systems
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：51
• 期：2
• 页码：153-191
• 全文大小：1,025 KB
• 参考文献：1. Andersson B, Baruah S, Jonsson J (2001) Static-priority scheduling on multiprocessors. In: Proceedings of the 22nd IEEE real-time systems symposium (RTSS), London, UK, pp 193鈥?02
  2. ARM Cortex-A (2013) ARM Cortex-A7/A9/A15 MPCore Technical Reference Manual
  3. ARM Cortex-R (2013) ARM Cortex-R4/R5 Technical Reference Manual
  4. Austin, T, Blaauw, D, Mahlke, S, Mudge, T, Chakrabarti, C, Wolf, W (2004) Mobile supercomputers. Computer 37: pp. 81-83 CrossRef
  5. Awan M, Petters S (2011) Enhanced race-to-halt: a leakage-aware energy management approach for dynamic priority systems. In: Proceedings of the 23rd Euromicro conference on real-time systems (ECRTS), Porto, Portugal, pp 92鈥?01
  6. Awan MA, Petters SM (2013) Energy-aware partitioning of tasks onto a heterogeneous multi-core platform. In: Proceedings of the 19th IEEE real-time and embedded technology and applications symposium (RTAS), Philadelphia, USA, pp 205鈥?14
  7. Awan MA, Yomsi PM, Petters SM (2013) Optimal procrastination interval for constrained deadline sporadic tasks upon uniprocessors. In: Proceedings of the 21st international conference on real-time networks and systems (RTNS), Sophia Antipolis, France, pp 129鈥?38
  8. Aydin H, Yang Q (2003) Energy-aware partitioning for multiprocessor real-time systems. In: Proceedings of the workshop on parallel and distributed real-time systems (WPDRTS), Nice, France, p 113
  9. Aydin H, Mej铆a-Alvarez P, Moss茅 D, Melhem R (2001) Dynamic and aggressive scheduling techniques for power-aware real-time systems. In: Proceedings of the 22nd IEEE real-time systems symposium (RTSS), London, UK, pp 95鈥?05
  10. Baati K, Auguin M (2013) Temperature-aware DVFS-DPM for real-time applications under variable ambient temperature. In: Proceedings of the 8th IEEE international symposium on industrial embedded systems (SIES), Porto, Portugal, pp 13鈥?0
  11. Bambagini M, Bertogna M, Marinoni M, Buattazzo G (2012) On the impact of runtime overhead on energy-aware scheduling. In: Proceedings of the 1st international workshop on power, energy and temperature aware real-time systems (PERTARS), San Juan, Puerto Rico
  12. Bambagini M, Buttazzo G, Bertogna M (2013) Energy-aware scheduling for tasks with mixed energy requirements. In: Proceedings of the 4th international real-time scheduling open problems seminar (RTSOPS), Paris, France
  13. Baruah, SK, Rosier, LE, Howell, RR (1990) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. J Real Time Syst 2: pp. 301-324 CrossRef
  14. Baruah SK, Burns A, Davis RI (2011) Response-time analysis for mixed criticality systems. In: Proceedings of the IEEE 32nd real-time systems symposium (RTSS), Vienna, Austria, pp 34鈥?3
  15. Bhatti M, Farooq M, Belleudy C, Auguin M (2009) Controlling energy profile of rt multiprocessor systems by anticipating workload at runtime. In: Symposium en Architectures nouvelles de machines (SympA)
  16. Bhatti M, Belleudy C, Auguin M (2010) An inter-task real time DVFS scheme for multiprocessor embedded systems. In: Proceedings of the international conference on design and architectures for signal and image processing (DASIP), Edinburgh, UK, pp 136鈥?43
  17. Bini E, Buttazzo GC (2004) Biasing effects in schedulability measures. In: Proceedings of the 16th Euromicro conference on real-time systems (ECRTS), Catania, Italy, pp 196鈥?03
  18. Burns A, Davis R (2013) Mixed criticality systems鈥攁 review. http://www-users.cs.york.ac.uk/
  19. Carroll A, Heiser G (2010) An analysis of power consumption in a smartphone. In: Proceedings of the USENIX annual technical conference (ATC), Boston, USA, pp 21鈥?1
  20. Chabrol D, Roux D, David V, Jan M, Hmid MA, Oudin P, Zeppa G (2013) Time- and angle-triggered real-time kernel for powertrain applications. In: Proceedings of the design, automation test in Europe conference exhibition (DATE), Grenoble, France, pp 1060鈥?063
  21. Chen, JJ, Kuo, TW (2006) Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor. SIGPLAN Not 41: pp. 153-162 CrossRef
  22. Chen JJ, Kuo CF (2007) Energy-efficient scheduling for real-time systems on dynamic voltage scaling (DVS) platforms. In: Proceedings of the 13th IEEE international conference on embedded and real-time computing systems and applications (RTCSA), Daegu, Korea, pp 28鈥?8
  23. Chen JJ, Hsu HR, Kuo TW (2006) Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In: Proceedings of the 12th IEEE real-time and embedded technology and applications symposium (RTAS), San Jose, USA, pp 408鈥?17
  24. Cucu-Grosjean L, Santinelli L, Houston M, Lo C, Vardanega T, Kosmidis L, Abella J, Mezzetti E, Quinones E, Cazorla F (2012) Measurement-based probabilistic timing analysis for multi-path programs. In: Proceedings of the 24th Euromicro conference on real-time systems (ECRTS), Pisa, Italy, pp 91鈥?01
  25. David V, Aussagu猫s C, Louise S, Hilsenkopf P, Ortolo B, Hessler C (2004) The OASIS based qualified display system. In: 4th American Nuclear Society international topical meeting on nuclear plant instrumentation, controls and human鈥搈achine interface technologies (NPIC & HMIT), Columbus, USA
  26. Davis R, Burns A (2011a) FPZL schedulability analysis. In: Proceedings of the 17th IEEE real-time and embedded technology and applications symposium (RTAS), Chicago, USA, pp 245鈥?56
  27. Davis, R, Burns, A (2011) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real Time Syst 47: pp. 1-40 CrossRef
  28. Deng Q, Meisner D, Bhattacharjee A, Wenisch TF, Bianchini R (2012) CoScale: coordinating CPU and memory system DVFS in server systems. In: Proceedings of the 45th annual IEEE/ACM international symposium on microarchitecture (MICRO), Vancouver, Canada, pp 143鈥?54
  29. Evidence (2012) ERIKA enterprise manual, real-time made easy. http://erika.tuxfamily.org/drupal/
  30. FreeScale Semiconductor (2012) FreeScale MPC5510 Microcontroller Family Reference Manual
  31. Huang W, Stan MR, Skadron K, Sankaranarayanan K, Ghosh S, Velusam S (2004) Compact thermal modeling for temperature-aware design. In: Proceedings of the 41th design automation conference (DAC), San Diego, USA, pp 878鈥?83
  32. Huang K, Santinelli L, Chen JJ, Thiele L, Buttazzo G (2009a) Adaptive dynamic power management for hard real-time systems. In: Proceedings of the 30th real-time systems symposium (RTSS), Washington, USA, pp 23鈥?2
  33. Huang K, Santinelli L, Chen JJ, Thiele L, Buttazzo G (2009b) Periodic power management schemes for real-time event streams. In: Proceedings of the 48th conference on decision and control (CDC), Shanghai, China, pp 6224鈥?231
  34. Huang H, Xia F, Wang J, Lei S, Wu G (2010) Leakage-aware reallocation for periodic real-time tasks on multicore processors. In: Proceedings of the 5th international conference on frontier of computer science and technology (FCST), Changchun, China, pp 85鈥?1
  35. Huang, K, Santinelli, L, Chen, JJ, Thiele, L, Buttazzo, GC (2011) Applying real-time interface and calculus for dynamic power management in hard real-time systems. Real Time Syst 47: pp. 163-193 CrossRef
  36. International Sematech Reliability Technology Advisory Board (2000) Semiconductor device reliability failure models
  37. Jan M, David V, Lalande J, Pitel M (2010) Usage of the safety-oriented real-time OASIS approach to build deterministic protection relays. In: Proceedings of the 5th international symposium on industrial embedded systems (SIES), Trento, Italy, pp 128鈥?35
  38. Jejurikar, R, Gupta, R (2004) Procrastination scheduling in fixed priority real-time systems. SIGPLAN Not 39: pp. 57-66 CrossRef
  39. Jejurikar R, Gupta R (2005) Dynamic slack reclamation with procrastination scheduling in real-time embedded systems. In: Proceedings of the 42nd design automation conference (DAC), San Diego, USA, pp 111鈥?16
  40. Jejurikar R, Pereira C, Gupta R (2004) Leakage aware dynamic voltage scaling for real-time embedded systems. In: Proceedings of the 41st annual design automation conference (DAC), San Diego, USA, pp 275鈥?80
  41. Kim, N, Austin, T, Baauw, D, Mudge, T, Flautner, K, Hu, J, Irwin, M, Kandemir, M, Narayanan, V (2003) Leakage current: Moore鈥檚 law meets static power. Computer 36: pp. 68-75 CrossRef
  42. Kopetz H (1998) The time-triggered model of computation. In: Proceedings of the IEEE real-time systems symposium (RTSS), Madrid, Spain, pp 168鈥?77
  43. Kreith, F (2000) The CRC handbook of thermal engineering. CRC Press, Boca Raton
  44. Le Sueur E, Heiser G (2010) Dynamic voltage and frequency scaling: the laws of diminishing returns. In: Proceedings of the workshop on power aware computing and system (HotPower), Farmington, USA, pp 1鈥?
  45. Le Sueur E, Heiser G (2011) Slow down or sleep, that is the question. In: Proceedings of the USENIX annual technical conference (ATC), Portland, OR, pp 16鈥?6
  46. Lee YH, Reddy K, Krishna C (2003) Scheduling techniques for reducing leakage power in hard real-time systems. In: Proceedings of the 15th Euromicro conference on real-time systems (ECRTS), Porto, Portugal, pp 105鈥?12
  47. Legout V, Jan M, Pautet L (2013a) Mixed-criticality multiprocessor real-time systems: energy consumption vs deadline misses. In: 1st workshop on real-time mixed criticality system (ReTiMiCS), Taipei, Taiwan
  48. Legout V, Jan M, Pautet L (2013b) An off-line multiprocessor real-time scheduling algorithm to reduce static energy consumption. In: 1st Workshop on highly-reliable power-efficient embedded designs (HARSH), Shenzhen, China
  49. Legout V, Jan M, Pautet L (2013c) A scheduling algorithm to reduce the static energy consumption of multiprocessor real-time systems. In: Proceedings of the 21st international conference on real-time networks and systems (RTNS), Sophia Antipolis, France, pp 99鈥?08
  50. Lemerre M, David V, Aussagu猫s C, Vidal-Naquet G (2008) Equivalence between schedule representations: theory and applications. In: Proceedings of the IEEE real-time and embedded technology and applications symposium (RTAS), St. Louis, USA, pp 237鈥?47
  51. Lemerre M, Ohayon E, Chabrol D, Jan M, Jacques MB (2011) Method and tools for mixed-criticality real-time applications within PharOS. In: Proceedings of the 14th IEEE international symposium on object/component/service-oriented real-time distributed computing workshops (ISORCW11), Newport Beach, USA
  52. Liao W, He L, Lepak K (2004) Temperature-aware performance and power modeling. Technical report, UCLA Engineering
  53. Mahesri A, Vardhan V (2004) Power consumption breakdown on a modern laptop. In: Proceedings of the 4th international conference on power-aware computer systems (PACS), Portland, USA, pp 165鈥?80
  54. Megel T, Sirdey R, David V (2010) Minimizing task preemptions and migrations in multiprocessor optimal real-time schedules. In: Proceedings of the 31st IEEE real-time systems symposium (RTSS), San Diego, USA, pp 37鈥?6
  55. Minas L, Ellison B (2009) The problem of power consumption in servers. Intel Press, Hillsboro
  56. N茅lis V, Goossens J (2009) MORA: an energy-aware slack reclamation scheme for scheduling sporadic real-time tasks upon multiprocessor platforms. In: Proceedings of the 15th IEEE international conference on embedded and real-time computing systems and applications (RTCSA), Beijing, China, pp 210鈥?15
  57. Nelissen G, Berten V, Goossens J, Milojevic D (2011) Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness. In: Proceedings of the 17th international conference on embedded and real-time computing systems and applications (RTCSA), Toyama, Japan, pp 15鈥?4
  58. Niu L, Quan G (2004) Reducing both dynamic and leakage energy consumption for hard real-time systems. In: Proceedings of the 2004 international conference on compilers, architecture, and synthesis for embedded systems (CASES), Washington, USA, pp 140鈥?48
  59. Parkinson P (2011) Safety, security and multicore. In: Dale C, Anderson T (eds) Advances in systems safety. Springer, London, pp 215鈥?32
  60. Regnier P, Lima G, Massa E, Levin G, Brandt S (2011) RUN: optimal multiprocessor real-time scheduling via reduction to uniprocessor. In: Proceedings of the IEEE 32nd real-time systems symposium (RTSS), Vienna, Austria, pp 104鈥?15
  61. Rosing, T, Mihic, K, Micheli, G (2007) Power and reliability management of SoCs. IEEE Trans Very Large Scale Integr Syst 15: pp. 391-403 CrossRef
  62. Rowe, A, Lakshmanan, K, Zhu, H, Rajkumar, R (2010) Rate-harmonized scheduling and its applicability to energy management. IEEE Trans Ind Inform 6: pp. 265-275 CrossRef
  63. Seo, E, Jeong, J, Park, S, Lee, J (2008) Energy efficient scheduling of real-time tasks on multicore processors. IEEE Trans Parallel Distrib Syst 19: pp. 1540-1552 CrossRef
  64. ST Microelectronics (2013) ST microelectronics STM32L151xx and STM32L152xx advanced ARM-based 32-bit MCUs Reference Manual
  65. Tudor, BM, Teo, YM (2013) On understanding the energy consumption of arm-based multicore servers. Sigmetrics Perform Eval Rev 41: pp. 267-278 CrossRef
  66. Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proceedings of the 28th IEEE international real-time systems symposium (RTSS), Tucson, USA, pp 239鈥?43
  67. Wei HW, Chao YH, Lin SS, Lin KJ, Shih WK (2007) Current results on EDZL scheduling for multiprocessor real-time systems. In: Proceedings of the 13th IEEE international conference on embedded and real-time computing systems and applications (RTCSA), Daegu, Korea, pp 120鈥?30
  68. Weicker, RP (1984) Dhrystone: a synthetic systems programming benchmark. Commun ACM 27: pp. 1013-1030 CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Computer Systems Organization and Communication Networks
  Communications Engineering and Networks
  Special Purpose and Application-Based Systems
  Performance and Reliability
  Control Engineering
  
• 出版者：Springer Netherlands
• ISSN：1573-1383

文摘

Energy consumption is an important concern when designing embedded systems. Static consumption now dominates dynamic consumption as the semiconductor technology moves to deep sub-micron scale. This has lead to the availability of energy efficient low-power states for processors. However, integrating their use at the scheduling level to reduce the energy consumption of real-time systems requires to appropriately optimize the length of the idle periods, while still ensuring real-time constraints. This problem has not been well studied when some or all the tasks are hard real-time and are executed over a multiprocessor architecture. In this paper, we propose the first optimal multiprocessor scheduling algorithms to efficiently use the low-power states of multiprocessor architectures. We target both hard real-time systems and mixed-criticality (MC) systems, in which some tasks have a lower criticality and can therefore tolerate some deadline misses. We use a similar off-line approach for both type of systems, where the idle time is modeled using an additional task. A mixed integer linear program is then used to compute schedules that optimize the length of the idle periods, such that the most efficient low-power states can be used. On-line, we extend an existing scheduling algorithm to increase the length of the existing idle periods. Simulations show that while processors are idle, we reduce the energy consumption up to ten times while keeping the number of preemptions similar to state-of-the-art optimal multiprocessor real-time schedulers. For MC systems, a trade-off between consumption reduction and deadline misses of the low-criticality tasks can be explored.