research-article

Performance-Driven Post-Processing of Control Loop Execution Schedules

Authors:

Pallab DasguptaAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 26, Issue 2

Article No.: 13, Pages 1 - 27

https://doi.org/10.1145/3421505

Published: 19 October 2020 Publication History

Abstract

The increasing demand for mapping diverse embedded features onto shared electronic control units has brought about novel ways to co-design control tasks and their schedules. These techniques replace traditional implementations of control with new methods, such as pattern-based scheduling of control tasks and adaptive sharing of bandwidth among control loops through orchestration of their execution patterns. In the current practice of control design, once the static execution schedule is prepared for control tasks, no further control-related optimization is attempted for improving the control performance. We introduce, for the first time, an algorithmic mechanism that re-engineers a recurrent control task by enforcing switching between multiple control laws, which are designed for compensating the non-uniform gaps between successive executions of the control task. We establish that such post-processing of control task schedules may potentially help in improving the combined control performance of the co-scheduled control loops that are executing on a shared platform.

References

[1]

[n.d.]. http://www.ibm.com/software/integration/optimization/cplex/.

[2]

R. Alur, A. D’Innocenzo, K. H. Johansson, G. J. Pappas, and G. Weiss. 2011. Compositional modeling and analysis of multi-hop control networks. IEEE Trans. Automat. Control 56, 10 (Oct 2011), 2345--2357.

[3]

Rajeev Alur and Gera Weiss. 2008. Regular specifications of resource requirements for embedded control software. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 159--168.

Digital Library

[4]

Karl J. Åström and Björn Wittenmark. 1997. Computer-Controlled Systems. Prentice-Hall, Inc.

[5]

G. Bernat, A. Burns, and A. Liamosi. 2001. Weakly hard real-time systems. IEEE Trans. Comput. 50, 4 (Apr. 2001), 308--321.

Digital Library

[6]

R. Blind and F. Allgöwer. 2015. Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process. In Proceedings of the Conference on Decision and Control. 7510--7515.

[7]

S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. 1994. Linear Matrix Inequalities in System and Control Theory. Society for Industrial and Applied Mathematics.

[8]

Rosa Castané et al. 2006. Resource management for control tasks based on the transient dynamics of closed-loop systems. In Proceedings of the Euromicro Conference on Real-Time Systems. 10--pp.

[9]

Anton Cervin, Johan Eker, Bo Bernhardsson, and Karl-Erik Årzén. 2002. Feedback feedforward scheduling of control tasks. Real-Time Systems 23, 1–2 (2002), 25--53.

Digital Library

[10]

Anton Cervin, Manel Velasco, Pau Marté, and Antonio Camacho. 2009. Optimal on-line sampling period assignment. Department of Automatic Control, Technical University of Catalonia, Barcelona, Spain, Technical Report ESAII-RR-09-04 (2009).

[11]

Anton Cervin, Manel Velasco, Pau Marté, and Antonio Camacho. 2011. Optimal online sampling period assignment: Theory and experiments. IEEE Transactions on Control Systems Technology 19, 4 (2011), 902--910.

[12]

Wanli Chang, Dip Goswami, Samarjit Chakraborty, and Arne Hamann. 2018. OS-aware automotive controller design using non-uniform sampling. ACM Transactions on Cyberphysical Systems 2, 4 (July 2018), 26:1--26:22.

[13]

A. D’Innocenzo, M. D. Di Benedetto, and E. Serra. 2011. Link failure detection in multi-hop control networks. In Proceedings of the Conference on Decision and Control and European Control Conference. 5248--5253.

[14]

Johan Eker, Per Hagander, and Karl-Erik Årzén. 2000. A feedback scheduler for real-time controller tasks. Control Engineering Practice 8, 12 (2000), 1369--1378.

[15]

Felicioni Flavia et al. 2008. Optimal on-line (m, k)-firm constraint assignment for real-time control tasks based on plant state information. In Proceedings of the Conference on Emerging Technologies and Factory Automation. 908--915.

[16]

Simon Fürst. 2015. Autosar the next generation--the adaptive platform. CARS@ EDCC2015 (2015).

[17]

Michael Garey and David S. Johnson. 1979. Computers and Intractability. W. H. Freeman and Company, New York.

Digital Library

[18]

Maximilian Gaukler, Tim Rheinfels, Peter Ulbrich, and Günter Roppenecker. 2019. Convergence Rate Abstractions for Weakly-Hard Real-Time Control. arxiv:1912.09871

[19]

S. Ghosh, S. Dey, and P. Dasgupta. 2018. Co-synthesis of loop execution patterns for multihop control networks. IEEE Embedded System Letters 10, 4 (Dec. 2018), 111--114.

Digital Library

[20]

Sumana Ghosh, Soumyajit Dey, and Pallab Dasgupta. 2019. Performance and energy aware robust specification of control execution patterns under dropped samples. IET Computers 8 Digital Techniques (June 2019).

[21]

Sumana Ghosh, Souradeep Dutta, Soumyajit Dey, and Pallab Dasgupta. 2017. A structured methodology for pattern based adaptive scheduling in embedded control. ACM Transactions on Embedded Computing Systems 16, 5s (Sept. 2017), 189:1--189:22.

Digital Library

[22]

Dip Goswami, Alejandro Masrur, Reinhard Schneider, Chun J. Xue, and Samarjit Chakraborty. 2013. Multirate controller design for resource-and schedule-constrained automotive ECUs. In Proceedings of the Design, Automation and Test in Europe Conference. 1123--1126.

[23]

Dan Henriksson and Anton Cervin. 2005. Optimal on-line sampling period assignment for real-time control tasks based on plant state information. In Proceedings of the Conference on Decision and Control. 4469--4474.

[24]

Dan Henriksson, Anton Cervin, and Karl-Erik Årzén. 2002. TRUETIME: Simulation of control loops under shared computer resources. IFAC Proceedings, Volume 35, 1 (2002), 417--422.

[25]

Chao Huang, Wenchao Li, and Qi Zhu. 2019. Formal verification of weakly-hard systems. In Proceedings of the Hybrid Systems: Computation and Control. 197--207.

Digital Library

[26]

Ning Jia, Ye-Qiong Song, and Rui-Zhong Lin. 2006. Analysis of networked control system with packet drops governed by (m,k)-firm constraint^*. In Fieldbus Systems and Their Applications 2005. 63--70.

[27]

Florian Kluge, Markus Neuerburg, and Theo Ungerer. 2015. Utility-based scheduling of (m, k)-firm real-time task sets. In Architecture of Computing Systems (ARCS'15). 201--211.

[28]

Jin Ho Kwak and Sungpyo Hong. 2004. Linear Algebra. Springer.

[29]

Daniel Liberzon. 2003. Switching in Systems and Control. Springer.

[30]

S. Linsenmayer and F. Allgower. 2017. Stabilization of networked control systems with weakly hard real-time dropout description. In Proceedings of the Conference on Decision and Control. 4765--4770.

[31]

Chung Laung Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1 (1973), 46--61.

Digital Library

[32]

Rupak Majumdar, Indranil Saha, and Majid Zamani. 2011. Performance-aware scheduler synthesis for control systems. In Proceedings of the Conference on Embedded Software. 299--308.

Digital Library

[33]

Patrizia Marti et al. 2009. Draco: Efficient resource management for resource-constrained control tasks. IEEE Trans. Comput. 58, 1 (2009), 90--105.

Digital Library

[34]

M. Mizuochi, T. Tsuji, and K. Ohnishi. 2007. Multirate sampling method for acceleration control system. IEEE Transactions on Industrial Electronics 54, 3 (June 2007), 1462--1471.

[35]

Miad Moarref and Luis Rodrigues. 2013. Exponential stability and stabilization of linear multi-rate sampled-data systems. In Proceedings of the American Control Conference, 158--163.

[36]

Jia Ning, Song YeQiong, and Simonot-Lion Francoise. 2007. Graceful degradation of the quality of control through data drop policy. In Proceedings of the European Control Conference. 4324--4331.

[37]

Paolo Pazzaglia, Luigi Pannocchi, Alessandro Biondi, and Marco Di Natale. 2018. Beyond the weakly hard model: Measuring the performance cost of deadline misses. In Proceedings of the Euromicro Conference on Real-Time Systems, Vol. 106. 10:1--10:22.

[38]

Parameswaran Ramanathan. 1999. Overload management in real-time control applications using (m,k)-firm guarantee. IEEE Transactions on Parallel and Distributed Systems 10, 6 (1999), 549--559.

Digital Library

[39]

Debayan Roy, Licong Zhang, Wanli Chang, Dip Goswami, and Samarjit Chakraborty. 2016. Multi-objective co-optimization of FlexRay-based distributed control systems. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. 1--12.

[40]

Indranil Saha, Sanjoy Baruah, and Rupak Majumdar. 2015. Dynamic scheduling for networked control systems. In Hybrid Systems: Computation and Control. ACM, 98--107.

[41]

Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki. 2003. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics 126, 2 (2003), 313--322.

Digital Library

[42]

Michael Schinkel, Wen-Hua Chen, and Anders Rantzer. 2002. Optimal control for systems with varying sampling rate. In Proceedings of the American Control Conference, Vol. 4. 2979--2984.

[43]

Danbing Seto, John P. Lehoczky, Lui Sha, and Kang G. Shin. 1996. On task schedulability in real-time control systems. In Proceedings of the Real-Time Systems Symposium. 13--21.

[44]

Damoon Soudbakhsh et al. 2013. Co-design of control and platform with dropped signals. In Proceedings of the International Conference on Cyber-Physical Systems. 129--140.

[45]

Gera Weiss and Rajeev Alur. 2007. Automata based interfaces for control and scheduling. In Proceedings of the Conference on Hybrid Systems: Computation and Control. 601--613.

[46]

Majid Zamani, Soumyajit Dey, Sajid Mohamed, Pallab Dasgupta, and Manuel Mazo. 2016. Scheduling of controllers update-rates for residual bandwidth utilization. In Proceedings of the Conference on Formal Modeling and Analysis of Timed Systems. 85--101.

Cited By

Adhikary SKoley IGhosh SGhosh SDey S(2024)Revisiting Dynamic Scheduling of Control Tasks: A Performance-Aware Fine-Grained ApproachIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344300743:11(3662-3673)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3443007

Index Terms

Performance-Driven Post-Processing of Control Loop Execution Schedules
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
2. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Correctness
        Real-time schedulability

Recommendations

Performance-aware scheduler synthesis for control systems
EMSOFT '11: Proceedings of the ninth ACM international conference on Embedded software

We consider the problem of designing a cyber-physical system where several control loops share the same architectural resources. Typically, the design of such systems proceeds in two steps. In the platform independent step, for each control loop in the ...
Analyzing Asynchronous Pipeline Schedules

Asynchronous pipelining is a form of parallelism that is useful in both distributed and shared memory systems. We show that asynchronous pipeline schedules are a generalization of both noniterative DAG (directed acyclic graph) schedules as well as ...
Hardware Accelerated Scheduling in Real-Time Systems
ECBS-EERC '15: Proceedings of the 2015 4th Eastern European Regional Conference on the Engineering of Computer Based Systems

There are two groups of task scheduling algorithms in real-time systems. The first group contains algorithms that have constant asymptotic time complexity and thus these algorithms lead to deterministic task switch duration but smaller theoretical CPU ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 26, Issue 2

March 2021

220 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3430836

Editor:
X. Sharon Hu
University of Notre Dame, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 19 October 2020

Accepted: 01 August 2020

Revised: 01 July 2020

Received: 01 March 2020

Published in TODAES Volume 26, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
137
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Adhikary SKoley IGhosh SGhosh SDey S(2024)Revisiting Dynamic Scheduling of Control Tasks: A Performance-Aware Fine-Grained ApproachIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.344300743:11(3662-3673)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3443007

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents