ILP representation for Limited Preemption in Energy-Neutral Single-Core Systems
Pages 1 - 11
Abstract
In this work, we present an Integer Linear Programming (ILP) based approach that optimally selects preemption points for a set of real-time tasks. Beyond to meeting real-time constraints, the system must also consider energy availability constraints to ensure energy neutrality. This enables the design of autonomous low-end IoT devices with real-time constraints, minimizing maintenance operations to battery replacements.
We demonstrate that our system, despite being modeled using ILP, achieves strong temporal performance, even for large-scale problems. We evaluated its performance using the Gurobi solver across a wide range of synthetic experiments.
References
[1]
Yasmina Abdeddaïm, Younès Chandarli, and Damien Masson. 2013. The optimality of PFPasap algorithm for fixed-priority energy-harvesting real-time systems. In Proc. of the IEEE 25th Euromicro Conference on Real-Time Systems (ECRTS). 47–56.
[2]
Kunal Agrawal, Sanjoy Baruah, and Pontus Ekberg. 2023. Rethinking Tractability for Schedulability Analysis. In 2023 IEEE Real-Time Systems Symposium (RTSS). IEEE, 1–12.
[3]
Ahmad Al Sheikh, Olivier Brun, Maxime Chéramy, and Pierre-Emmanuel Hladik. 2013. Optimal design of virtual links in AFDX networks. Real-Time Systems 49, 3 (2013), 308–336.
[4]
Andre Allavena and Daniel Mosse. 2001. Scheduling of frame-based embedded systems with rechargeable batteries. In Workshop on Power Management for Real-time and Embedded systems.
[5]
Mohammad Asghari, Amir M. Fathollahi-Fard, S.M.J. Mirzapour Al-e hashem, and Maxim A. Dulebenets. 2022. Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey. Mathematics 10, 183 (2022).
[6]
Sanjoy Baruah. 2005. The limited-preemption uniprocessor scheduling of sporadic task systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS). 137–144.
[7]
Sanjoy Baruah. 2005. The limited-preemption uniprocessor scheduling of sporadic task systems. In Proc. of the 17th Euromicro Conference on Real-Time Systems (ECRTS). 137–144.
[8]
Sanjoy K Baruah, Vincenzo Bonifaci, Renato Bruni, and Alberto Marchetti-Spaccamela. 2019. ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. Journal of Scheduling 22 (2019), 195–209.
[9]
Marko Bertogna, Orges Xhani, Mauro Marinoni, Francesco Esposito, and Giorgio Buttazzo. 2011. Optimal selection of preemption points to minimize preemption overhead. In Proc. of the 23rd Euromicro Conference on Real-Time Systems (ECRTS). 217–227.
[10]
Enrico Bini, Giorgio Buttazzo, and Giuseppe Lipari. 2005. Speed modulation in energy-aware real-time systems. In Proc. of the 17th Euromicro Conference on Real-Time Systems (ECRTS). 3–10.
[11]
Enrico Bini and Giorgio C. Buttazzo. 2005. Measuring the Performance of Schedulability Tests. Real-Time Systems 30, 1 (2005), 129–154.
[12]
Giorgio C Buttazzo, Marko Bertogna, and Gang Yao. 2012. Limited preemptive scheduling for real-time systems. a survey. IEEE transactions on Industrial Informatics 9, 1 (2012), 3–15.
[13]
Bipasa Chattopadhyay and Sanjoy Baruah. 2014. Limited-preemption scheduling on multiprocessors. In Proc. of the 22nd International Conference on Real-Time Networks and Systems (RTNS). 225–234.
[14]
Jian-Jia Chen and Chin-Fu Kuo. 2007. Energy-Efficient Scheduling for Real-Time Systems on Dynamic Voltage Scaling (DVS) Platforms. In Proc. of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 28–38.
[15]
Maryline Chetto. 2014. Optimal scheduling for real-time jobs in energy harvesting computing systems. IEEE Transactions on Emerging Topics in Computing 2, 2 (2014), 122–133.
[16]
Robert I Davis, Alan Burns, Jose Marinho, Vincent Nelis, Stefan M Petters, and Marko Bertogna. 2015. Global and partitioned multiprocessor fixed priority scheduling with deferred preemption. ACM Transactions on Embedded Computing Systems (TECS) 14, 3 (2015), 1–28.
[17]
Carmen Delgado and Jeroen Famaey. 2021. Optimal energy-aware task scheduling for batteryless IoT devices. IEEE Transactions on Emerging Topics in Computing 10, 3 (2021), 1374–1387.
[18]
Bashima Islam and Shahriar Nirjon. 2020. Scheduling Computational and Energy Harvesting Tasks in Deadline-Aware Intermittent Systems. In 2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). 95–109.
[19]
Ravindra Jejurikar, Cristiano Pereira, and Rajesh Gupta. 2004. Leakage aware dynamic voltage scaling for real-time embedded systems. In Proc. of the 41st ACM annual Design Automation Conference. 275–280.
[20]
Mohsen Karimi, Hyunjong Choi, Yidi Wang, Yecheng Xiang, and Hyoseung Kim. 2021. Real-Time Task Scheduling on Intermittently Powered Batteryless Devices. IEEE Internet of Things Journal 8, 17 (2021), 13328–13342.
[21]
Ying Li, Jianwei Niu, Meikang Qiu, and Xiang Long. 2015. Optimizing Tasks Assignment on Heterogeneous Multi-core Real-Time Systems with Minimum Energy. In Proc. of the IEEE 17th International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security, and IEEE 12th International Conference on Embedded Software and Systems. 577–582.
[22]
Haining Liu, Ijaz Haider Naqvi, Fajia Li, Chengliang Liu, Neda Shafiei, Yulong Li, and Michael Pecht. 2020. An analytical model for the CC-CV charge of Li-ion batteries with application to degradation analysis. Journal of Energy Storage 29 (2020), 101342.
[23]
Shaobo Liu, Qing Wu, and Qinru Qiu. 2009. An adaptive scheduling and voltage/frequency selection algorithm for real-time energy harvesting systems. In Proceedings of the 46th Annual Design Automation Conference. 782–787.
[24]
Clemens Moser, Davide Brunelli, Lothar Thiele, and Luca Benini. 2007. Real-time scheduling for energy harvesting sensor nodes. Real-Time Systems 37 (2007), 233–260.
[25]
Eduardo Valentin, Mario Salvatierra, Rosiane de Freitas, and Raimundo Barreto. 2015. Response time schedulability analysis for hard real-time systems accounting DVFS latency on heterogeneous cluster-based platform. In Proc. of the 25th IEEE International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS). 1–8.
[26]
Yun Wang and Manas Saksena. 1999. Scheduling fixed-priority tasks with preemption threshold. In Proc. of the 6th IEEE International Conference on Real-Time Computing Systems and Applications (RTCSA). 328–335.
[27]
Gang Yao, Giorgio Buttazzo, and Marko Bertogna. 2009. Bounding the maximum length of non-preemptive regions under fixed priority scheduling. In Proc. of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 351–360.
[28]
Houssam-Eddine Zahaf, Abou El Hassen Benyamina, Richard Olejnik, and Giuseppe Lipari. 2017. Energy-efficient scheduling for moldable real-time tasks on heterogeneous computing platforms. Journal of Systems Architecture 74 (2017), 46–60.
[29]
Houssam-Eddine Zahaf, Giuseppe Lipari, Marko Bertogna, and Pierre Boulet. 2019. The Parallel Multi-Mode Digraph Task Model for Energy-Aware Real-Time Heterogeneous Multi-Core Systems. IEEE Trans. Comput. 68, 10 (2019), 1511–1524.
[30]
Houssam-Eddine ZAHAF, Giuseppe Lipari, Smail Niar, and Abou El Hassan Benyamina. 2020. Preemption-Aware Allocation, Deadline Assignment for Conditional DAGs on Partitioned EDF. In 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 1–10.
Index Terms
- ILP representation for Limited Preemption in Energy-Neutral Single-Core Systems
Recommendations
Operating Energy-Neutral Real-Time Systems
Special Issue on Autonomous Battery-Free Sensing and Communication, Special Issue on ESWEEK 2016 and Regular PapersEnergy-neutral real-time systems harvest the entire energy they use from their environment. In such systems, energy must be treated as an equally important resource as time, which creates the need to solve a number of problems that so far have not been ...
An ILP framework for energy optimized scheduling for weakly-hard real-time systems: work-in-progress
EMSOFT '19: Proceedings of the International Conference on Embedded Software CompanionIn this work, we propose an integer linear programming (ILP) model to schedule a set of weakly-hard real-time tasks on a heterogeneous multiprocessor system to minimize energy consumption with the predictable performance. The ILP model provides an ...
Generic ILP versus specialized 0-1 ILP: an update
ICCAD '02: Proceedings of the 2002 IEEE/ACM international conference on Computer-aided designOptimized solvers for the Boolean Satisfiability (SAT) problem have many applications in areas such as hardware and software verification, FPGA routing, planning, etc. Further uses are complicated by the need to express "counting constraints" in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2024
326 pages
ISBN:9798400717246
DOI:10.1145/3696355
Copyright © 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. Request permissions from owner/author(s).
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 03 January 2025
Check for updates
Qualifiers
- Research-article
Conference
RTNS 2024
RTNS 2024: The 32nd International Conference on Real-Time Networks and Systems
November 6 - 8, 2024
Porto, Portugal
Acceptance Rates
Overall Acceptance Rate 119 of 255 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 5Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)5
Reflects downloads up to 15 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in