單一處理器及同質多處理器上之即時省電排程

Energy-Efficient Scheduling for Real-Time Tasks in Uniprocessor and Homogeneous Multiprocessor Systems

陳建佳(Jian-Jia Chen)

指導教授 ： 郭大維

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.01368

摘要

無資料

關鍵字

省電效率排程 ； 即時系統 ； 近似演算法 ； 動態調變電壓系統

並列摘要

With the advanced technology in VLSI circuit designs, many modern processors now provide dynamic voltage scaling (DVS) support. The lower the speed is, the lower the supply voltage requires, and the less the power consumes. This dissertation explores energy-efficient scheduling for hard real-time systems and the maximization of the system reward for real-time systems under a specified energy constraint on DVS processors. Distinct from many previous work, this dissertation aims at the provision of approximated solutions with worst-case guarantees. In addition to the worst-case analysis of the developed algorithms, extensive experiments were done to evaluate the effectiveness of the algorithms, compared to existing algorithms. The experimental results are very encouraging.

When speed switching is not allowed in the middle of a job execution, a polynomial-time $(1+epsilon)$-approximation algorithm is presented to minimize the energy consumption of periodic real-time tasks in uniprocessor systems with a user-specified tolerable error $epsilon$. It provides trade-offs between the user's tolerable error and the runtime complexity, including the time complexity and the space complexity. When leakage power consumption is considered, we develop procrastination scheduling strategies to reduce the energy consumption by turning processors into the dormant mode. Approximation bounds are derived for rate-monotonic and earliest-deadline-first scheduling algorithms. When periodic real-time task executions are considered in homogeneous multiprocessor systems with ideal processors, we develop algorithms with resource augmentation on processor speeds. A $1.13$-approximation algorithm is developed for systems with negligible leakage power consumption, and $2$-approximation algorithms are developed for systems with non-negligible leakage power consumption.

Energy-constrained scheduling is then explored with reward
maximization in uniprocessor systems. When speed switching can be done at any time with an identical power consumption function, a greedy algorithm is proposed with a $0.5$-approximation ratio. A dynamic programming approach is then proposed with a $(1-epsilon)$-approximation ratio, where the running time is polynomial in $frac{1}{epsilon}$ with a user-specified tolerable error $epsilon$ to derived solutions. When tasks have different power consumption functions or voltage scaling could be done only at a task arrival or termination time, a frac{1}{3}$-approximation
algorithm is developed based on linear programming.

並列關鍵字

Energy-Efficient Scheduling ； Real-Time Systems ； Approximation Algorithms ； DVS Systems

參考文獻

[1] ADVANCED CONFIGURATION AND POWER INTERFACE SPECIFICATION 2.0. http://www.acpi.info/.

[2] T. A. AlEnawy and H. Aydin. On energy-constrained real-time scheduling. In Proceedings of of EuroMicro Conference on Real-Time Systems (ECRTS'04), pages 165-174, 2004.

[3] T. A. AlEnawy and H. Aydin. Energy-aware task allocation for rate monotonic scheduling. In Proceedings of the 11th IEEE Real-time and Embedded Technology and Applications Symposium (RTAS'05), pages 213-223, 2005.

[4] J. H. Anderson and S. K. Baruah. Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms. In Proceedings of the 24th International Conference on Distributed Computing Systems, pages 428-435, 2004.

[5] H. Aydin, R. Melhem, D. Moss'e, and P. Mej'ia-Alvarez. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Proceedings of the IEEE EuroMicro Conference on Real-Time Systems, pages 225-232, 2001.