A Model for Reconfiguration of Multi-Modal Real-Time Systems under Energy Constraints
Resumo
The problem of maximizing quality of service (QoS) of real-time systems subject to both schedulability and energy constraints is addressed. A discrete system consisting of tasks with multiple operating modes, and which can be executed by the processor at different frequency/voltage levels, is considered. Although the system reconfiguration scheme assumes the earliest deadline first (EDF) policy and soft real-time tasks, it can be extended to other scheduling policies and handle hard real-time tasks. The described solution is suitable for adaptive real-time embedded systems which require energy savings associated to QoS. Despite being NP-Hard, the reconfiguration problem can be solved with a mixed-integer linear-programing solver sufficiently fast.
Referências
C. A. Rusu R. Melhem and D. Mossé "Maximizing the system value while satisfying time and energy constraints " IBM Journal of Research and Development vol. 47 no. 5-6 pp. 689-702 Sept 2003.
C. Rusu R. Melhem and D. Mossé "Multi-version scheduling in rechargeable energy-aware real-time systems " Journal of Embedded Computing vol. 1 no. 2 pp. 271-283 2005.
G. Buttazzo "Research trends in real-time computing for embedded systems " ACM SIGBED Review vol. 3 no. 3 pp. 1-10 2006.
A. B. Oliveira E. Camponogara and G. Lima "Dynamic reconfiguration in reservation-based scheduling: An optimization approach " in Proceedings of the 15th IEEE Symposium on Real-Time and Embedded Technology and Applications Apr 2009 pp. 173-182.
E. Camponogara A. B. Oliveira and G. Lima "Optimizationbased dynamic reconfiguration of real-time schedulers with support for stochastic processor consumption " IEEE Transactions on Industrial Informatics vol. 6 no. 4 pp. 594-609 Nov 2010.
F. Yao A. Demers and S. Shenker "A scheduling model for reduced CPU energy " in Proceedings of the 36th Annual Symposium on Foundations of Computer Science Oct 1995 pp. 374-382.
G. Quan and X. Hu "Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors " in Proceedings of the Design Automation Conference 2001 pp. 828-833. (Pubitemid 32841063)
R. Jejurikar C. Pereira and R. Gupta "Leakage aware dynamic voltage scaling for real-time embedded systems " in Proceedings of the 41st Annual Design Automation Conference 2004 pp. 275-280.
C. Xian Y.-H. Lu and Z. Li "Dynamic voltage scaling for multitasking real-time systems with uncertain execution time " IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. 27 no. 8 pp. 1467-1478 Aug 2008.
Y. Shin K. Choi and T. Sakurai "Power optimization of real-time embedded systems on variable speed processors " in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design 2000 pp. 365-368. (Pubitemid 32188433)
W. Kim J. Kim and S. Min "A dynamic voltage scaling algorithm for dynamic-priority hard real-time systems using slack time analysis " in Proceedings of the Conference on Design Automation and Test in Europe 2002.
X. Zhong and C.-Z. Xu "Energy-aware modeling and scheduling for dynamic voltage scaling with statistical realtime guarantee " IEEE Transactions on Computers vol. 56 no. 3 pp. 358-372 March 2007. (Pubitemid 46443332)
Y. Zhu and F. Mueller "Feedback EDF scheduling of realtime tasks exploiting dynamic voltage scaling " Real-time Systems vol. 31 no. 1-3 pp. 33-63 2005. (Pubitemid 43127505)
P. Pillai and K. G. Shin "Real-time dynamic voltage scaling for low-power embedded operating systems " Proceedings of the eighteenth ACM symposium on Operating systems principles pp. 89-102 Oct 2001. (Pubitemid 33612607)
D. Zhu R. Melhem and D. Mossé "The effects of energy management on reliability in real-time embedded systems " in Proceedings of the International Conference on Computer-Aided Design 2004 pp. 35-40. (Pubitemid 40449211)
H. Yu B. Veeravalli and Y. Ha "Dynamic scheduling of imprecise-computation tasks in maximizing QoS under energy constraints for embedded systems " in Proceedings of the Asia and South Pacific Design Automation Conference March 2008 pp. 452-455.
G. Lima E. Camponogara and A. C. Sokolonski "Dynamic reconfiguration for adaptive multiversion real-time systems " in Proceedings of the 20th IEEE Euromicro Conference on Real-Time Systems 2008 pp. 115-124.
J. Jehuda and A. Israeli "Automated meta-control for adaptable real-time software " Real-Time Systems pp. 107-134 1998. (Pubitemid 128513579)
C. Lee J. P. Lehoczky R. Rajkumar and D. Siewiorek "On quality of service optimization with discrete QoS options " in Proceedings of the 5th IEEE Real-time Technology and Applications Symposium 1999 pp. 276-286.
C. Lee J. P. Lehoczky D. S. R. Rajkumar and J. Hansen "A scalable solution to the multi-resource QoS problem " in Proceedings of the 20th IEEE Real-Time Systems Symposium 1999 pp. 315-326. (Pubitemid 30560571)
A. Burns D. Prasad A. Bondavalli F. D. Giandomenico K. Ramamritham J. Stankovic and L. Strigini "The meaning and role of value in scheduling flexible real-time systems " Journal of Systems Architecture vol. 46 no. 4 pp. 305-325 2000.
D. Prasad and A. Burns "A value-based scheduling approach for real-time autonomous vehicle control " Robotica vol. 18 no. 3 pp. 273-279 2000.
C. W. Mercer S. Savage and H. Tokuda "Processor capacity reserves for multimedia operating systems " Carnegie Mellon University Tech. Rep. CMU-CS-93-157 1993.
L. Abeni and G. Buttazzo "Resource reservation in dynamic real-time systems " Real-Time Systems vol. 27 no. 2 pp. 123-167 2004.
ARM. (2011 Jun) Application notes and tutorials. http://infocenter.arm. com/help/index.jsp. Online; accessed July-2011.
E. Bini and G. Buttazzo "Measuring the performance of schedulability tests " Real-Time Systems vol. 30 no. 1 pp. 129-154 2005. (Pubitemid 41310221)
Intel. (2010 oct) Intel Technical Documents - Intel core 2 duo mobile processor. http://www.intel.com/. Online; accessed October-2010.
Micron. (2010 oct) Technical Notes. http://www.micron.com. Online; accessed October-2010.
N. Pinckney T. Barr M. Dayringer M. McKnett N. Jiang C. Nygaard D. M. Harris J. Stanley and B. Phillips "A mips r2000 implementation " in Proceedings of the 45th annual Design Automation Conference 2008 pp. 102-107.
Pintool. (2011 Jul) A dynamic binary instrumentation tool. http://www.pintool.org/. Online; accessed July-2011.
S. Martello and P. Toth "An exact algorithm for the twoconstraint 0-1 knapsack problem " Operations Research vol. 51 no. 5 pp. 826-835 2003.
A. M. Frieze and M. R. B. Clarke "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses " European Journal of Operational Research vol. 15 no. 1 pp. 100-109 1984. (Pubitemid 14505490)
C. Rusu R. Melhem and D. Mossé "Multi-version scheduling in rechargeable energy-aware real-time systems " Journal of Embedded Computing vol. 1 no. 2 pp. 271-283 2005.
G. Buttazzo "Research trends in real-time computing for embedded systems " ACM SIGBED Review vol. 3 no. 3 pp. 1-10 2006.
A. B. Oliveira E. Camponogara and G. Lima "Dynamic reconfiguration in reservation-based scheduling: An optimization approach " in Proceedings of the 15th IEEE Symposium on Real-Time and Embedded Technology and Applications Apr 2009 pp. 173-182.
E. Camponogara A. B. Oliveira and G. Lima "Optimizationbased dynamic reconfiguration of real-time schedulers with support for stochastic processor consumption " IEEE Transactions on Industrial Informatics vol. 6 no. 4 pp. 594-609 Nov 2010.
F. Yao A. Demers and S. Shenker "A scheduling model for reduced CPU energy " in Proceedings of the 36th Annual Symposium on Foundations of Computer Science Oct 1995 pp. 374-382.
G. Quan and X. Hu "Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors " in Proceedings of the Design Automation Conference 2001 pp. 828-833. (Pubitemid 32841063)
R. Jejurikar C. Pereira and R. Gupta "Leakage aware dynamic voltage scaling for real-time embedded systems " in Proceedings of the 41st Annual Design Automation Conference 2004 pp. 275-280.
C. Xian Y.-H. Lu and Z. Li "Dynamic voltage scaling for multitasking real-time systems with uncertain execution time " IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. 27 no. 8 pp. 1467-1478 Aug 2008.
Y. Shin K. Choi and T. Sakurai "Power optimization of real-time embedded systems on variable speed processors " in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design 2000 pp. 365-368. (Pubitemid 32188433)
W. Kim J. Kim and S. Min "A dynamic voltage scaling algorithm for dynamic-priority hard real-time systems using slack time analysis " in Proceedings of the Conference on Design Automation and Test in Europe 2002.
X. Zhong and C.-Z. Xu "Energy-aware modeling and scheduling for dynamic voltage scaling with statistical realtime guarantee " IEEE Transactions on Computers vol. 56 no. 3 pp. 358-372 March 2007. (Pubitemid 46443332)
Y. Zhu and F. Mueller "Feedback EDF scheduling of realtime tasks exploiting dynamic voltage scaling " Real-time Systems vol. 31 no. 1-3 pp. 33-63 2005. (Pubitemid 43127505)
P. Pillai and K. G. Shin "Real-time dynamic voltage scaling for low-power embedded operating systems " Proceedings of the eighteenth ACM symposium on Operating systems principles pp. 89-102 Oct 2001. (Pubitemid 33612607)
D. Zhu R. Melhem and D. Mossé "The effects of energy management on reliability in real-time embedded systems " in Proceedings of the International Conference on Computer-Aided Design 2004 pp. 35-40. (Pubitemid 40449211)
H. Yu B. Veeravalli and Y. Ha "Dynamic scheduling of imprecise-computation tasks in maximizing QoS under energy constraints for embedded systems " in Proceedings of the Asia and South Pacific Design Automation Conference March 2008 pp. 452-455.
G. Lima E. Camponogara and A. C. Sokolonski "Dynamic reconfiguration for adaptive multiversion real-time systems " in Proceedings of the 20th IEEE Euromicro Conference on Real-Time Systems 2008 pp. 115-124.
J. Jehuda and A. Israeli "Automated meta-control for adaptable real-time software " Real-Time Systems pp. 107-134 1998. (Pubitemid 128513579)
C. Lee J. P. Lehoczky R. Rajkumar and D. Siewiorek "On quality of service optimization with discrete QoS options " in Proceedings of the 5th IEEE Real-time Technology and Applications Symposium 1999 pp. 276-286.
C. Lee J. P. Lehoczky D. S. R. Rajkumar and J. Hansen "A scalable solution to the multi-resource QoS problem " in Proceedings of the 20th IEEE Real-Time Systems Symposium 1999 pp. 315-326. (Pubitemid 30560571)
A. Burns D. Prasad A. Bondavalli F. D. Giandomenico K. Ramamritham J. Stankovic and L. Strigini "The meaning and role of value in scheduling flexible real-time systems " Journal of Systems Architecture vol. 46 no. 4 pp. 305-325 2000.
D. Prasad and A. Burns "A value-based scheduling approach for real-time autonomous vehicle control " Robotica vol. 18 no. 3 pp. 273-279 2000.
C. W. Mercer S. Savage and H. Tokuda "Processor capacity reserves for multimedia operating systems " Carnegie Mellon University Tech. Rep. CMU-CS-93-157 1993.
L. Abeni and G. Buttazzo "Resource reservation in dynamic real-time systems " Real-Time Systems vol. 27 no. 2 pp. 123-167 2004.
ARM. (2011 Jun) Application notes and tutorials. http://infocenter.arm. com/help/index.jsp. Online; accessed July-2011.
E. Bini and G. Buttazzo "Measuring the performance of schedulability tests " Real-Time Systems vol. 30 no. 1 pp. 129-154 2005. (Pubitemid 41310221)
Intel. (2010 oct) Intel Technical Documents - Intel core 2 duo mobile processor. http://www.intel.com/. Online; accessed October-2010.
Micron. (2010 oct) Technical Notes. http://www.micron.com. Online; accessed October-2010.
N. Pinckney T. Barr M. Dayringer M. McKnett N. Jiang C. Nygaard D. M. Harris J. Stanley and B. Phillips "A mips r2000 implementation " in Proceedings of the 45th annual Design Automation Conference 2008 pp. 102-107.
Pintool. (2011 Jul) A dynamic binary instrumentation tool. http://www.pintool.org/. Online; accessed July-2011.
S. Martello and P. Toth "An exact algorithm for the twoconstraint 0-1 knapsack problem " Operations Research vol. 51 no. 5 pp. 826-835 2003.
A. M. Frieze and M. R. B. Clarke "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses " European Journal of Operational Research vol. 15 no. 1 pp. 100-109 1984. (Pubitemid 14505490)
Publicado
07/11/2011
Como Citar
NASSIFE, Riad; CAMPONOGARA, Eduardo; LIMA, George.
A Model for Reconfiguration of Multi-Modal Real-Time Systems under Energy Constraints. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 1. , 2011, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 127-132.
ISSN 2237-5430.
