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: Lui Sha , John B. Goodenough, Real-Time Scheduling Theory and Ada, Computer, v.23 n.4, p.53-62, April 1990 [doi>10.1109/2.55469]
• 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: Real-Rate Scheduling, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, p.434, May 25-28, 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: John A. Stankovic , Tian He , Tarek Abdelzaher , Mike Marley , Gang Tao , Sang Son , Cenyan Lu, Feedback Control Scheduling in Distributed Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.59, December 03-06, 2001
• 6: J. Liu, Real-Time Systems: Prentice Hall PTR 2000.
• 7: Chenyang Lu , John A. Stankovic , Sang H. Son , Gang Tao, Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms*, Real-Time Systems, v.23 n.1-2, p.85-126, July-September 2002 [doi>10.1023/A:1015398403337]
• 8: Yong Fu , Hongan Wang , Chenyang Lu , Ramu Sharat Chandra, Distributed Utilization Control for Real-Time Clusters with Load Balancing, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.137-146, December 05-08, 2006 [doi>10.1109/RTSS.2006.20]
• 9: Chenyang Lu , Xiaorui Wang , Xenofon Koutsoukos, Feedback Utilization Control in Distributed Real-Time Systems with End-to-End Tasks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.550-561, June 2005 [doi>10.1109/TPDS.2005.73]
• 10: Xiaorui Wang , Yingming Chen , Chenyang Lu , Xenofon Koutsoukos, FC-ORB: A robust distributed real-time embedded middleware with end-to-end utilization control, Journal of Systems and Software, v.80 n.7, p.938-950, July, 2007 [doi>10.1016/j.jss.2006.09.031]
• 11: Xiaorui Wang , Dong Jia , Chenyang Lu , Xenofon Koutsoukos, DEUCON: Decentralized End-to-End Utilization Control for Distributed Real-Time Systems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.7, p.996-1009, July 2007 [doi>10.1109/TPDS.2007.1051]
• 12: Yingming Chen , Chenyang Lu , Xenofon Koutsoukos, Optimal Discrete Rate Adaptation for Distributed Real-Time Systems, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.181-192, December 03-06, 2007 [doi>10.1109/RTSS.2007.32]
• 13: Gabriel Lipsa , Andreas Herkersdorf, Towards a Framework and a Design Methodology for Autonomic SoC, Proceedings of the Second International Conference on Automatic Computing, p.391-392, June 13-16, 2005 [doi>10.1109/ICAC.2005.61]
• 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: Salvatore Carta , Andrea Alimonda , Alessandro Pisano , Andrea Acquaviva , Luca Benini, A control theoretic approach to energy-efficient pipelined computation in MPSoCs, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.27-es, September 2007 [doi>10.1145/1274858.1274865]
• 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

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Management, Performance

Keywords:
feedback control, multiprocessors, real-time scheduling.