Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

An Efficient Voltage Scheduling for Embedded Real-Time Systems with Task Synchronization

태스크 동기화가 필요한 임베디드 실시간 시스템에 대한 효율적인 전압 스케쥴링

  • 이재동 (경남대학교 컴퓨터공학부) ;
  • 허정연 (경남대학교 컴퓨터공학부)
  • Published : 2008.06.15
Download PDF
⟨ Previous Next ⟩

Abstract

Many embedded real-time systems have adopted processors supported with dynamic voltage scaling(DVS) recently. Power is one of the important metrics for optimization in the design and operation of embedded real-time systems. We can save considerable energy by using slowdown of processor supported with DVS. In this paper, we propose heuristic algorithms to calculate task slowdown factors for an efficient energy consumption in embedded real-time systems with task synchronization. The previous algorithm has a following constraint : given the tasks are ordered in a nondecreasing order of their relative deadline, the task slowdown factors computed are in a nonincreasing order. In this paper, we relax the constraint and propose heuristic algorithms which have the same time complexity that previous algorithm has and can save more energy. Experimental results show that the proposed algorithms are energy efficient.

최근 많은 임베디드 실시간 시스템에 동적 전압 조절(Dynamic Voltage Scaling: DVS)을 지원하는 프로세서를 사용하고 있다. 이런 시스템의 설계 및 동작의 최적화를 위한 중요한 요소 중 하나가 전력(power)이다. 동적 전압 조절을 지원하는 프로세서의 슬로우다운을 이용하므로서 많은 소비 전력을 절약할 수 있다. 본 논문에서는 태스크의 동기화가 필요한 임베디드 실시간 시스템에서 효율적인 전력 소비를 위해 태스크들의 슬로우다운 값을 구하는 휴리스틱 알고리즘들을 제안한다. 기존 알고리즘에서는 상대 마감시간이 작은 태스크의 슬로우다운 값은 상대 마감시간이 크거나 같은 태스크의 슬로우다운 값보다 크거나 같아야 한다는 제약조건을 가지고 있다. 본 논문에서는 이 제약조건을 완화하여 기존 알고리즘과 같은 시간복잡도를 가지면서 전력을 더 작게 소비하는 휴리스틱 알고리즘들을 제시한다. 실험을 통해 소비전력 면에서 효율적임을 보였다.

Keywords

References

  1. J. W. S. Liu, Real-Time Systems. Upper Saddle River, NJ: PrenticeHall, 2000
  2. G. C. Buttazzo, Hard Real-Time Computing Systems. Boston, MA: Kluwer, 1995
  3. J. Chen and C. Kuo, "Energy-Efficient Scheduling for Real-time Systems on Dynamic Voltage Scaling(DVS) Platforms," in the 13th IEEE International Conf. on Embedded and Real-Time Computing Systems and Applications, 2007
  4. F. Yao, A. J. Demers, and S. Shenker, "A Scheduling Model for Reduced CPU Energy," in Proc. IEEE Symposium Foundations Computer Science, pp. 374- 382, 1995
  5. N. Bansal, T. Kimbrel, and K. Pruhs, "Dynamic Speed Scaling to Manage Energy and Temperature," in Proc. the Symposium on Foundation of Computer Science, pp. 520-529, 2004
  6. W. Kwon and T. Kim, "Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors," in Proc. Design Automation Conference, pp. 125-130, 2003
  7. M. Li and F. Yao, "An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules," SIAM J. Computer, Vol.35, No.3, pp 658-671, 2005 https://doi.org/10.1137/050629434
  8. G. Quan and X. Hu, "Energy Efficient Fixed-Priority Scheduling for Real-Time Systems on Variable Voltage Processors," in Proc. Design Automation Conference, pp. 828-833, 2001
  9. G. Quan and X. Hu, "Minimum Energy Fixed-Priority Scheduling for Variable Voltage Processors," in Proc. Design Automation and Test Europe, pp. 782-787, 2002
  10. H. Yun and J. Kim, "On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-Time Systems," ACM Trans. on Embeddded Computing Systems, Vol.2, No.3, pp. 393-430, 2003 https://doi.org/10.1145/860176.860183
  11. Y. Shin, K. Choi, and T. Sakurai, "Power Optimization of Real-Time Embedded Systems on Variable Speed Processors," in Proc. Int. Conf. Computer Aided Design, pp. 365-368, 2000
  12. F. Gruian, "Hard Real-Time Scheduling for Low- Energy using Stochastic Data and DVS Processors," in Proc. Int. Symposium Low Power Electronics and Design, pp. 46-51, 2001
  13. H. Aydin, R. Melhem, D. Mosse, and P. M. Alvarez, "Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems," in Proc. IEEE Real-Time Systems Symposium, pp. 95-105, 2001
  14. H. Aydin, R. Melhem, D. Mosse, and P. M. Alvarez, "Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics," in Proc. EuroMicro Conference Real-Time Systems, pp. 225-232, 2001
  15. P. Pillai and K. G. Shin, "Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems," in Proc. 18th Symposium Operating Systems Principles, pp. 89-102, 2001
  16. W. Kim, J, Kim, and S. L. Min, "A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real- Time Systems using Slack Time Analysis," in Proc. Design Automation and Test Europe, pp. 788-794, 2002
  17. R. Jejurikar and R. Gupta, "Dynamic Slack Reclamation with Procrastination Scheduling in Real-Time Embedded Systems," in DAC, pp 111-116, 2005
  18. A. K. Mok, "Fundamental Design Problems of Distributed Systems for Hard Real-Time Environment," Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., Massachusetts Inst. Technol., 1983
  19. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of Np-Completeness. San Francisco, CA: Freeman, 1979
  20. J. A. Stankovic, M. Spuri, M. D. Natale, and G. Buttazzo, "Implications of Classical Scheduling Results for Real-Time Systems," IEEE Trans. on Computer, Vol.28, No.6, pp. 16-25, 1994 https://doi.org/10.1109/TC.1979.1675218
  21. T. P. Baker, "Stack-Based Scheduling of Real-Time Processes," J. Real-Time Syst., Vol.3, No.1, pp. 67-99, 1991 https://doi.org/10.1007/BF00365393
  22. L. Sha, R. Rajkumar, and J. P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE Trans. on Compututer, Vol.39, No.9, pp. 1175-1185, 1990 https://doi.org/10.1109/12.57058
  23. R. Jejurikar and R. Gupta, "Energy Aware Task Scheduling with Task Synchronization for Embedded Real Time Systems," in Proc. Int. Conf. Compilers, Architecture and Synthesis Embedded Systems, pp. 164-169, 2002
  24. R. Jejurikar and R. Gupta, "Energy Aware EDF Scheduling with Task Synchronization for Embedded Real Time Operating Systems," in Workshop Compilers and Operating System Low Power, pp. 7.1-7.6, 2002
  25. R. Jejurikar and R. Gupta, "Energy-Aware Task Scheduling With Task Synchronization for Embedded Real-Time Systems," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.25, No.6, pp 1024-1037, 2006 https://doi.org/10.1109/TCAD.2005.855964
  26. F. Zhang and S. T. Chanson, "Processor Voltage Scheduling for Real-Time Tasks with Non-preemptible Sections," in Proc. IEEE Real-Time Systems Symposium, pp. 235-245, 2002
  27. Y. Chen, C. Yang, and T. Kuo, "FL-PCP: Frequency locking for Energy-Efficient Real-Time Task Synchronization," the 13th IEEE International Conf. on Embedded and Real-Time Computing Systems and Applications, 2007
  28. M. Chen and K. Lin, "Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems," Real Time Systems Journel, Vol.2, No.1, pp. 325-346, 1990 https://doi.org/10.1007/BF01995676
  29. Intel StrongARM Processor, Intel Inc., http://www. intel.com/design/strong/specupdt/278259.htm
  30. Intel XScale Processor, Intel Inc., http://developer. intel.com/design/intelxscale/xscale_datasheet4.htm
  31. Transmeta Crusoe Processor, Transmeta Inc., http://www. transmeta.com/crusoe/specs/html