Efficient Scheduling for Real-Time Pinwheel Tasks on DVS Processors

Abstract:

In this paper, we focus on the pinwheel task model for 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. Previous approaches solve this problem by generating a canonical schedule beforehand and adjusting the tasks' speed in O(dn log n) or O(n³) time. However, the length of a canonical schedule depends on the hyperperiod 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.

• Periodical: Applied Mechanics and Materials (Volumes 479-480)
• Pages: 901-905
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.479-480.901
• Online since: December 2013
• Authors: Da Ren Chen, You Shyang Chen
• Keywords: Dynamic Voltage Scaling, Hard Real-Time Systems, Pinwheel Tasks, Power-Aware Scheduling

References

[1] H. Aydin, R. Melhem, D. Mosse and P. Mejia-Alvarez. Power-Aware Scheduling for Periodic Real-Time Tasks. IEEE Trans. Comput., 53(5): 584-600, May (2004).

DOI: 10.1109/tc.2004.1275298

[2] Sanjoy K. Baruah, Azer Bestavros, Pinwheel Scheduling for Fault-Tolerant Broadcast Disks in Real-time Database Systems, Proceedings of the IEEE International Conference on Data Engineering ICDE 1997: 543-551.

DOI: 10.1109/icde.1997.582023

[3] D. -R. Chen. Scheduling Methods for Periodic Tasks in Real-Time Systems. Doctoral Dissertation National Taiwan University of Science and Technology, (2005).

[4] F. Gruian. Hard Real-Time Scheduling Using Stochastic Data and DVS Processors. In Proceedings of the International Symposium on Low Power Electronics and Design, 46-51, Aug. (2001).

DOI: 10.1145/383082.383092

[5] C. -C. Han, K. -J. Lin and C. -J. Hou. Distance-Constrained Scheduling and Its Applications to Real-Time Systems. IEEE Trans. Comput. 45(7): 814-826, July (1996).

DOI: 10.1109/12.508320

[6] T. Ishihara and H. Yasuura. Voltage scheduling problem for dynamically variable voltage processor. In Proceedings of International Symposium on Low Power Electronics and Design, 197-202, (1998).

DOI: 10.1145/280756.280894

[7] M. Kang, D. -I. Kang, J. Suh and J. Lee, An energy-efficient real-time scheduling scheme on dual-channel networks, Information Sciences, Vol. 178, Issue 12, 15th June 2008, pp.2553-2563.

DOI: 10.1016/j.ins.2008.02.007

[8] W. Kim, J. Kim, and S. L. Min. A. A Dynamic Voltage Scaling Algorithm for Dynamic-priority Hard Real-Time Systems Using Slack Time Analysis. In Proceedings of Design, Automation and Test in Europe (DATE'02), 788-794, March (2002).

DOI: 10.1109/date.2002.998389

[9] W. -C. Kwon and T. Kim. Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Trans. Embedded Comput. Sys., 4(1): 211-230, Feb. (2005).

DOI: 10.1145/1053271.1053280

[10] M. Li and F. F. Yao. An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput., 35(3): 658-671, (2006).

DOI: 10.1137/050629434

[11] Jane W.S. Liu. Real-Time Systems. Prentice Hall, (2000).

[12] P. Pillai and K. G. Shin. Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems. In Proceedings of 18th ACM Symposium on Operating Systems Principles (SOSP'01), 89-102, Oct. (2001).

DOI: 10.1145/502034.502044

[13] F. Yao, A. Demers, and S. Shenker. A Scheduling Model for Reduced CPU energy. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 374-382, (1995).

DOI: 10.1109/sfcs.1995.492493

[14] D. Zhu, D. Mosse and R. Melhem. Power-Aware scheduling for and/or graphs in Real-time systems. IEEE Trans. Parallel and Distributed Sys., 15(9): 849-864, Sep. (2004).

DOI: 10.1109/tpds.2004.45