Real-Time Energy Efficient Scheduling for Power-Mode-Switching Systems

本論文提出了即時系統上新的最佳化問題，名為動態電源模式轉換（DPMS）。為了降低系統中最低限度的能源消耗（static power）,我們藉由某些特定的電源模式將系統閒置中的元件關閉，而這些特定的電源模式即是代表著各系統元件開關狀態的組合。電源模式最佳化問題點出了一個處理器省電技術上新的研究方向。 針對電源模式轉換最佳化問題，我們在基於為人所深知的期限最早優先（earliest deadline first）排程演算法的概念上提了一個新的演算法。此演算法描述了如何利用多餘的系統效能去減低能源消耗並且能夠同時保證各個系統任務（task）能夠在期限內完成。實驗結果證明了我們提出的演算法是成效良好並且有效率。The thesis introduces a new optimization problem called dynamic power mode switching (DPMS) in real-time system. In order to reduce the static power of system, we shutdown the system components in idle by means of some particular power modes which represent combinations of system components on/off states. The DPMS optimization problem indicates a new research direction of the energy-saving techniques on processor. Aiming at the DPMS optimization problem, we propose an algorithm based on the well-known earliest deadline first (EDF) scheduling. It describes how to exploit the spare system utilization to reduce energy consumption during the operation of power mode switching and guarantee all tasks meet their deadlines at the same time. The results show that our algorithm is energy efficient and effective.誌謝 i 摘要 iii Abstract v Contents vii List of Tables ix List of Figures xi Chapter 1 Introduction 1 1.1 Background 1 1.2 Related Works 3 1.2.1 Dynamic Voltage Scaling (DVS) 3 1.2.2 Clock Gating 4 1.3 Our Contributions 5 1.4 Organization of this Thesis 6 Chapter 2 Preliminaries 9 2.1 Models 9 2.1.1 Task and Real-Time Models 9 2.1.2 Power Mode Model 11 2.1.3 Power Consumption Model 12 2.2 Problem Formulations 13 2.2.1 The Simple Version 13 2.2.2 Proof for NP-Complete 14 2.2.3 The real-time version 19 Chapter 3 Dynamic Time Overhead Insertion Algorithm 21 3.1 Algorithm Overview 21 3.2 Real-time System Environment 23 3.3 Dynamic Time overhead Insertion Algorithm 24 3.3.1 Spare system utilization Calculating 24 3.3.2 Feasible Number of PMS Calculating 25 3.3.3 Greedy power mode selection 27 3.4 Summary 29 Chapter 4 Experimental Results 31 4.1 Experiment Environment 31 4.2 Experimental Results 31 Chapter 5 Conclusion 35 Reference 3