Energy-Efficient Real-Time Task Scheduling for a DVS System with a Non-DVS Processing Element

現今的嵌入式系統多半採取多重處理單元的設計方式，這樣的架構挑戰了考量能源效益的軟硬體共同設計。本論文探討在此種架構下，具備一個可動態電壓調節處理器與一個不可動態電壓調節處理單元的系統之省電即時程序排程。我們考慮不可動態電壓調節處理單元在不同的耗電模式下的排程，當該處理單元的耗電與其工作量無關時，我們提出一個完全多項式時間近似方案。而當該處理單元的耗電與其工作量成正比時，相較於只使用一個可動態電壓調節處理器，我們提出一個0.5倍的近似演算法，來盡可能增加系統所省下的電量。本論文並以模擬實驗來驗證我們所提出的演算法的效能，結果顯示在考量能源效益上，我們所提出的演算法非常有效。Multiple processing elements are often adopted in the current designs of embedded systems. Such configurations impose challenges on hardware/software co-designs with energy-efficient considerations. This thesis targets energy-efficient real-time task scheduling of such popular configurations, in which systems are equipped with a DVS processor and a non-DVS processing element (PE). We consider task scheduling under different power consumption models of the non-DVS PE. When the power consumption of the non-DVS PE is independent on the assigned workload, a fully polynomial-time approximation scheme is developed for energy-efficient scheduling. When the energy consumption of the non-DVS PE depends on the assigned utilization, a 0.5-approximation algorithm is developed to maximize the energy saving, compared to the executions of tasks on a DVS processor. Extensive simulations were performed to evaluate the capability of our proposed algorithms. The results show that our proposed algorithms are very effective in energy-efficiency.Contents 1 Introduction 1 2 System Models 4 2.1 Task Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Processor Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Problem De nitions and Hardness . . . . . . . . . . . . . . . . . . . . . 9 3 Scheduling Algorithms for Systems with Ideal DVS PEs 13 3.1 Energy-Minimization for Systems with Workload-Independent Non-DVS PEs . . . . . . . . . . . . . . . . . . . 13 3.2 Energy-Saving for Systems with Workload-Dependent Non-DVS PEs . . . . . . . . . . . . . . . . . . . . 20 4 Scheduling Algorithms for Systems with Non-Ideal DVS PEs 30 4.1 Energy-Minimization for Systems with Workload-Independent Non-DVS PEs . . . . . . . . . . . . . . . . . . . 31 4.2 Energy-Saving for Systems with Workload-Dependent Non-DVS PEs . . . . . . . . . . . . . . . . . . . . 32 5 Performance Evaluation 33 5.1 Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Evaluation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6 Conclusions 4