Online adaptive utilization control for real-time embedded multiprocessor systems

ABSTRACT

To provide Quality of Service (QoS) guarantees in open and unpredictable environments, the utilization control problem is defined to keep the processor utilization at the schedulable utilization bound, even in the face of unpredictable and/or varying task execution times. To handle the end-to-end task model where each task is comprised of a chain of subtasks distributed on multiprocessors, researchers have used Model Predictive Control (MPC) to address the Multiple-Input, Multiple-Output (MIMO) control problem. Although MPC can handle a limited range of model uncertainties due to execution time estimation errors, the system may suffer performance deterioration or even become unstable if the actual task execution times are much larger than their estimated values. In this paper, we present an online adaptive optimal control approach using Recursive Least Squares (RLS) based model estimator plus Linear Quadratic (LQ) optimal controller. We use simulation experiments to demonstrate the effectiveness of our controller compared with the MPC-based controller.

References

1. L. Sha and J.B. Goodenough, "Real-Time Scheduling Theory and Ada," Computer, vol. 23, no. 4, pp. 53--62, 1990.
2. A.J. Garvey and V.R. Lesser, "Design-to-time real-time scheduling," IEEE Transactions on Systems, Man and Cybernetics, vol. 23, no. 6, pp. 1491--1502, 1993.
3. A. Goel, Walpole, and M. Shor. "Real-rate scheduling," in proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 434--441, 2004.
4. S. Lin and G. Manimaran. "Double-Loop Feedback-Based Scheduling Approach for Distributed Real-Time Systems," in proceedings of the High Performance Computing (HiPC), pp. 268--278, 2003.
5. J.A. Stankovic, T. He, T.F. Abdelzaher, M. Marley, G. Tao, S.H. Son, and C. Lu. "Feedback Control Real-Time Scheduling in Distributed Real-Time Systems," in proceedings of the IEEE Real-Time Systems Symp, 2001.
6. J. Liu, Real-Time Systems: Prentice Hall PTR 2000.
7. C. Lu, J.A. Stankovic, S.H. Son, and G. Tao, "Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms," Real-Time Systems, vol. 23, no. 1, pp. 85--126, 2002.
8. F. Yong, W. Hongan, L. Chenyang, and A.R.S.C. Ramu Sharat Chandra. "Distributed Utilization Control for Real-Time Clusters with Load Balancing," in proceedings of the 27th IEEE International Real-Time Systems Symposium,, pp. 137--146, 2006.
9. C. Lu, X. Wang, and K. X., "Feedback utilization control in distributed real-time systems with end-to-end tasks," Parallel and Distributed Systems, IEEE Transactions on, vol. 16, no. 6, pp. 550--561, 2005.
10. X. Wang, Y. Chen, C. Lu, and X. Koutsoukos, "FC-ORB: A robust distributed real-time embedded middleware with end-to-end utilization control," Journal of Systems and Software, vol. 80, no. 7, pp. 938--950, 2007.
11. X. Wang, D. Jia, C. Lu, and .X. Koutsoukos, "DEUCON: Decentralized End-to-End Utilization Control for Distributed Real-Time Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 7, pp. 996--1009, 2007.
12. Y. Chen, C. Lu, and X. Koutsoukos. "Optimal Discrete Rate Adaptation for Distributed Real-Time Systems," in proceedings of the 28th IEEE International Real-Time Systems Symposium, pp. 181--192, 2007.
13. G. Lipsa, A. Herkersdorf, W. Rosenstiel, O.A.B.O. Bringmann, and W.A.S.W. Stechele. "Towards a Framework and a Design Methodology for Autonomic SoC," in proceedings of the Second International Conference on Autonomic Computing, pp. 391--392, 2005.
14. A. Lankes, T. Wild, and J. Zeppenfeld, "System Level Simulation of Autonomic SoCs with TAPES," ARCS vol. 4934/2008, pp. 9--22, 2008.
15. T. Wild, A. Herkersdorf, and G.-Y. Lee, "TAPES - Trace-based architecture performance evaluation with SystemC," Design Automation for Embedded Systems, vol. 10, pp. 157--179, 2006.
16. C. Salvatore, A. Andrea, P. Alessandro, A. Andrea, and B. Luca, "A control theoretic approach to energy-efficient pipelined computation in MPSoCs," ACM Transactions on Embedded Computing Sys., vol. 6, no. 4, pp. 27, 2007.
17. X. Liu, X. Zhu, P. Pradeep, Z. Wang, and S. Sharad. "Optimal multivariate control for differentiated services on a shared hosting platform," in proceedings of the 2007 46th IEEE Conference on Decision and Control, pp. 3792--3799, 2007.
18. M. Karlsson, X. Zhu, and C. Karamanolis. "An adaptive optimal controller for non-intrusive performance differentiation in computing services," in proceedings of the International Conference on Control and Automation, vol. 2, pp. 709--714, 2005.
19. The MathWorks, MATLAB Function Reference, 2007.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance