An Efficient DVS Algorithm for Pinwheel Task Schedules
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we focus on the pinwheel task model with a variable voltage processor with d discrete voltage/speed levels. We propose an intra-task DVS algorithm, which constructs a minimum energy schedule for k tasks in O(d+k log k) time. We also give an inter-task DVS algorithm with O(d+n log n) time, where n denotes the number of jobs. Previous approaches solve this problem by generating a canonical schedule beforehand and adjusting the tasks’ speed in O(dn log n) or O(n^3) time. However, the length of a canonical schedule depends on the hyper period of those task periods and is of exponential length in general. In our approach, the tasks with arbitrary periods are first transformed into harmonic periods and then profile their key features. Afterward, an optimal discrete voltage schedule can be computed directly from those features.
Abstract
In this paper, we focus on the pinwheel task model with a variable voltage processor with d discrete voltage/speed levels. We propose an intra-task DVS algorithm, which constructs a minimum energy schedule for k tasks in O(d+k log k) time. We also give an inter-task DVS algorithm with O(d+n log n) time, where n denotes the number of jobs. Previous approaches solve this problem by generating a canonical schedule beforehand and adjusting the tasks’ speed in O(dn log n) or O(n^3) time. However, the length of a canonical schedule depends on the hyper period of those task periods and is of exponential length in general. In our approach, the tasks with arbitrary periods are first transformed into harmonic periods and then profile their key features. Afterward, an optimal discrete voltage schedule can be computed directly from those features.
참고문헌 (29)
- H. Aydin, "Power-Aware Scheduling for Periodic Real-Time Tasks", IEEE Trans. Comput, 53(5), pp.584~600 (2004)
- Sanjoy K. Baruah, "Pinwheel Scheduling for Fault-Tolerant Broadcast Disks in Real-time Database Systems", Proceedings of the IEEE International Conference on Data Engineering ICDE, pp.543~551 (1997)
- G. Brassard, "Fundamentals of Algorithmics" (1996), Prentice Hall International
- D.-R. Chen, "Scheduling Methods for Periodic Tasks in Real-Time Systems", 박사, National Taiwan University of Science and Technology, pp.2005
- F. Gruian, "Hard Real-Time Scheduling Using Stochastic Data and DVS Processors", Proceedings of the International Symposium on Low Power Electronics and Design, pp.46~51 (2001)
- C.-C. Han, "Distance-Constrained Scheduling and Its Applications to Real-Time Systems", IEEE Trans. Comput, 45(7), pp.814~826 (1996)
- C.-W. Hsueh, "Scheduling Real-Time Systems with End-to-End Timing Constraints Using the Distributed Pinwheel Model", IEEE Trans. Computers, 50(1), pp.51~66 (2001)
- C.-W. Hsueh, "Distance-Constrained Scheduling and Its Applications to Real-Time Systems", IEEE Trans. Computers, 45(7), pp.814~826 (1996)
- T. Ishihara, "Voltage scheduling problem for dynamically variable voltage processor", Proceedings of International Symposium on Low Power Electronics and Design, pp.197~202 (1998)
- M. Kang, "An energy-efficient real-time scheduling scheme on dual-channel networks", Information Sciences, 178(12), pp.2553~2563 (2008)
- 민상렬, "A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real-Time Systems Using Slack Time Analysis", 2002 Design, Automation and Test in Europe, pp.788~794 (2002)
- W. Kim, "Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems", IEEE RTAS, pp.219~228 (2002)
- S. Kim, "An Adaptive Bandwidth Reservation Algorithm for QoS Sensitive Multimedia Cellular Network", Proceedings of the IEEE VTC2002-Fall, Sept. 2002, Vancouver, Canada, pp.1475~1479 (2002)
- W.-C. Kwon, "Optimal voltage allocation techniques for dynamically variable voltage processors", ACM Trans. Embedded Comput. Sys, 4(1), pp.211~230 (2005)
- M. Li, "An efficient algorithm for computing optimal discrete voltage schedules", SIAM J. Comput, 35(3), pp.658~671 (2006)
- Jane W.S. Liu, "Real-Time Systems" (2000), Prentice Hall
- S.-A. Li, "Hardware", software co-design for particle swarm optimization algorithm, 2010, ~
- L. –L. Lu, "The study of handoff prediction schemes for resource reservation in mobile multimedia wireless networks", Proceedings of the of AINA 2004, March 2004. Fukuoka, Japan, 통권 : 2, pp.379~384 (2004)
- M. Marsan, "Performance analysis of cellular mobile communication networks supporting multimedia services", Mobile Network and Applications, 5(3), pp.167~177 (2000)
- S.-J. Park, "Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems", INFORMATION SCIENCES, 178(17), pp.3393~3401 (2008), ELSEVIER SCIENCE INC
- P. Pillai, "Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems", Proceedings of 18th ACM Symposium on Operating Systems Principles (SOSP’01), pp.89~102 (2001)
- M. Saleem, "Intelligence based routing protocol for wireless sensor networks: Survey and future directions", Information Sciences (2010)
- P. S. Sausen, "Routing in wireless sensor networks with dynamic power management and multi-coverage backbones", Information Sciences, 180(5), pp.653~663 (2010)
- 신영수, "Power Optimization of Real-Time Embedded Systems on Variable Speed Processors", IEEE, 2000, 365~368[DOI]
- D. Shin, "Intra-Task Voltage Scheduling for Low-Energy Hard Real- Time Applications", IEEE Design and Test of Computers, 18(2), pp.20~30 (2001)
- F. Yao, "A Scheduling Model for Reduced CPU energy", Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp.374~382 (1995)
- D. Zhu, "Power-Aware scheduling for and", or graphs in Realtime systems, 2004, pp.15(9), 849~864
- "Wireless Intel SpeedStep Power Manager – Optimizing power consumption for the intel PXA27x processor family, Wireless Intel SpeedStep® Power Manager White paper" (2004)[URL]
- "AMD Athlon 64 Processor Power and Thermal Datasheet" (2006)[URL]