Bruno Gaujal
Abstract
We present an algorithm for scheduling a set of nonrecurrent tasks (or jobs) with FIFO real-time constraints so as to minimize the total energy consumed when the tasks are performed on a dynamically variable voltage processor. Our algorithm runs in linear time and thus, in this case, is an improvement over the classical algorithm of Yao et al. It was inspired by considering the problem as a shortest-path problem. We also propose an algorithm to deal with the case where the processor has only a limited number of clock frequencies. This algorithm gives the optimum schedule with the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and otherwise need O(N log N) time. These complexities are shown to be the best possible. Finally, we extend our results to fluid tasks and to nonconvex cost functions.
- Aydin, H., R., M., Mossè, D., and P., M.-A. 2001. Dynamic and agressive scheduling techniques for power aware real-time systems. In Real-Time Systems Symposium. 95--105. Google Scholar
Digital Library
- Boissonnat, J. and Yvinec, M. 1995. Géométrie Algorithmique. Ediscience International.Google Scholar
- Es Salhiene, M., Fesquet, L., and Renaudin, M. 2003. Adaptation dynamique de la puissance des systèmes embarqués: les systèmes asynchrones surclassent les systèmes synchrones. In journées d'études Faible Tension---Faible Consommation (FTFC'03). 51--58.Google Scholar
- Gruian, F. 2001. On energy reduction in hard real-time systems containing tasks with stochastic execution times. In IEEE Workshop on Power Management for Real-Time and Embedded Systems. 11--16.Google Scholar
- Gruian, F. 2002. Energy-centric scheduling for real-time systems. Ph.D. thesis, Lund Institute of Technology, Sweden.Google Scholar
- Hong, I., Potkonjak, M., and Srivastava, M. 1998. On-line scheduling of hard real-time tasks on variable voltage processor. In International Conference on Computer Design. 653--656. Google ScholarDigital Library
- Ishihara, T. and Yasuura, H. 1998. Voltage scheduling problem for dynamically variable voltage processors. In International Symposium on Low Power Electronics and Design. 197--202. Google ScholarDigital Library
- Jackson, J. 1955. Scheduling a production line to minimize maximum tardiness. Tech. Rept., University of California. Report 43.Google Scholar
- Lorch, J. and Smith, A. 2001. Improving dynamic voltage scaling algorithms with pace. In ACM SIGMETRICS 2001 Conference. 50--61. Google ScholarDigital Library
- Mossè, D., Aydin, H., Childers, B., and Melhem, R. 2000. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compiler and Operating Systems for Low-Power.Google Scholar
- Quan, G. and Hu, X. 2001. Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors. In Design Automation Conference. 828--833. Google ScholarDigital Library
- Shin, D., Kim, J., and Lee, S. 2001. Intra-task voltage scheduling for low-energy hard real-time applications. IEEE Design & Test of Computers 18, 2, 20--30. Google ScholarDigital Library
- Shin, Y. and Choi, K. 1999. Power conscious fixed priority scheduling for hard real-time systems. In Design Automation Conference. 134--139. Google ScholarDigital Library
- Stankovic, J., Spuri, M., Ramamritham, K., and Buttazo, G. 1998. Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publ. Boston, MA. Google ScholarDigital Library
- Yao, F. 2003. Complexity of the Yao Demers Shenker algorithm. Private communication.Google Scholar
- Yao, F., Demers, A., and Shenker, S. 1995. A scheduling model for reduced CPU energy. In Proceedings of lEEE Annual Foundations of Computer Science. 374--382. Google ScholarDigital Library
- Yun, H.-S. and Kim, J. 2003. On energy-optimal voltage scheduling for fixed-priority hard real-time systems. ACM Transactions on Embedded Computing Systems 2, 3 (Aug.), 393--430. Google ScholarDigital Library
- Zhang, F. and Chanson, S. 2002. Processor voltage scheduling for real-time tasks with non-preemptible sections. In Real-Time Systems Symposium. 235--245. Google ScholarDigital Library
Index Terms
- Shortest-path algorithms for real-time scheduling of FIFO tasks with minimal energy use
Recommendations
Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems
Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an ...
Preference-oriented fixed-priority scheduling for periodic real-time tasks
A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...
Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms
In this paper, we study the global scheduling of periodic task systems on unrelated multiprocessor platforms. We first show two general properties which are well known for uniprocessor platforms and which are also true for unrelated multiprocessor ...
Comments