Transition-aware DVS algorithm for real-time systems using tree structure analysis |
| |
Authors: | Da-Ren Chen Chiun-Chieh Hsu You-Shyang Chen Chi-Jung Kuo Lin-Chih Chen |
| |
Affiliation: | 1. Department of Information Management, Hwa Hsia Institute of Technology 111 Gong Jhuan Rd., Chung Ho, Taipei, Taiwan, ROC;2. Department of Information Management, National Taiwan University of Science and Technology, #43, Sec.4, Keelung Rd., Taipei 106, Taiwan, ROC;3. Department of Information Management at Technology and Science Institute of Northern Taiwan, Taipei, Taiwan, ROC;4. Department of Information Management, National Dong Hwa University, Hualien, Taiwan, ROC |
| |
Abstract: | Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (pmax/pmin)) time complexity, respectively, where n, k, pmax and pmin denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|