태스크 동기화가 필요한 임베디드 실시간 시스템에 대한 효율적인 전압 스케쥴링 = An Efficient Voltage Scheduling for Embedded Real-Time Systems with Task Synchronization

다국어 초록 (Multilingual 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.

국문 초록 (Abstract)

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

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 시스템 모델 및 슬로우다운 계산 알고리즘
• 3. 휴리스틱 알고리즘
• 4. 성능평가
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 Transmeta Crusoe Processor, "http://www. transmeta.com/crusoe/specs/html"

2 Intel StrongARM Processor, "http://www. intel.com/design/strong/specupdt/278259.htm"

3 Intel XScale Processor, "http://developer. intel.com/design/intelxscale/xscale_datasheet4.htm"

4 T. P. Baker, "Stack-Based Scheduling of Real-Time Processes" 3 (3): 67-99, 1991

5 J. W. S. Liu, "Real-Time Systems. Upper Saddle River" NJ: PrenticeHall 2000

6 P. Pillai, "Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems" 89-102, 2001

7 F. Zhang, "Processor Voltage Scheduling for Real-Time Tasks with Non-preemptible Sections" 235-245, 2002

8 L. Sha, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" 39 (39): 1175-1185, 1990

9 Y. Shin, "Power Optimization of Real-Time Embedded Systems on Variable Speed Processors" 365-368, 2000

10 W. Kwon, "Optimal Voltage Allocation Techniques for Dynamically Variable Voltage Processors" 125-130, 2003

11 H. Yun, "On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-Time Systems" 2 (2): 393-430, 2003

12 G. Quan, "Minimum Energy Fixed-Priority Scheduling for Variable Voltage Processors" 782-787, 2002

13 J. A. Stankovic, "Implications of Classical Scheduling Results for Real-Time Systems" 28 (28): 16-25, 1994

14 F. Gruian, "Hard Real-Time Scheduling for Low- Energy using Stochastic Data and DVS Processors" 46-51, 2001

15 G. C. Buttazzo, "Hard Real-Time Computing Systems. Boston" MA: Kluwer 1995

16 A. K. Mok, "Fundamental Design Problems of Distributed Systems for Hard Real-Time Environment" Massachusetts Inst. Technol 1983

17 Y. Chen, "FL-PCP: Frequency locking for Energy-Efficient Real-Time Task Synchronization" 2007

18 J. Chen, "Energy-Efficient Scheduling for Real-time Systems on Dynamic Voltage Scaling(DVS) Platforms" 2007

19 R. Jejurikar, "Energy-Aware Task Scheduling With Task Synchronization for Embedded Real-Time Systems" 25 (25): 1024-1037, 2006

20 G. Quan, "Energy Efficient Fixed-Priority Scheduling for Real-Time Systems on Variable Voltage Processors" 828-833, 2001

21 R. Jejurikar, "Energy Aware Task Scheduling with Task Synchronization for Embedded Real Time Systems" 164-169, 2002

22 R. Jejurikar, "Energy Aware EDF Scheduling with Task Synchronization for Embedded Real Time Operating Systems" 7.1-7.6, 2002

23 H. Aydin, "Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems" 95-105, 2001

24 N. Bansal, "Dynamic Speed Scaling to Manage Energy and Temperature" 520-529, 2004

25 R. Jejurikar, "Dynamic Slack Reclamation with Procrastination Scheduling in Real-Time Embedded Systems" in DAC 111-116, 2005

26 M. Chen, "Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems" 2 (2): 325-346, 1990

27 H. Aydin, "Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics" 225-232, 2001

28 M. R. Garey, "Computers and Intractability: A Guide to the Theory of Np-Completeness" CA: Freeman 1979

29 M. Li, "An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules" 35 (35): 658-671, 2005

30 F. Yao, "A Scheduling Model for Reduced CPU Energy" 374-382, 1995

31 W. Kim, "A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real- Time Systems using Slack Time Analysis" 788-794, 2002