article

On the effectiveness of cache partitioning in hard real-time systems

Authors:

Sebastian Altmeyer,

Robert I. DavisAuthors Info & Claims

Real-Time Systems, Volume 52, Issue 5

Pages 598 - 643

https://doi.org/10.1007/s11241-015-9246-8

Published: 01 September 2016 Publication History

Abstract

In hard real-time systems, cache partitioning is often suggested as a means of increasing the predictability of caches in pre-emptively scheduled systems: when a task is assigned its own cache partition, inter-task cache eviction is avoided, and timing verification is reduced to the standard worst-case execution time analysis used in non-pre-emptive systems. The downside of cache partitioning is the potential increase in execution times. In this paper, we evaluate cache partitioning for hard real-time systems in terms of overall schedulability. To this end, we examine the sensitivity of (i) task execution times and (ii) pre-emption costs to the size of the cache partition allocated and present a cache partitioning algorithm that is optimal with respect to taskset schedulability. We also devise an alternative algorithm which primarily optimises schedulability but also minimises processor utilization. We evaluate the performance of cache partitioning compared to state-of-the-art pre-emption cost analysis based on benchmark code and on a large number of synthetic tasksets with both fixed priority and EDF scheduling. This allows us to derive general conclusions about the usability of cache partitioning and identify taskset and system parameters that influence the relative effectiveness of cache partitioning. We also examine the improvement in processor utilization obtained using an alternative cache partitioning algorithm, and the tradeoff in terms of increased analysis time.

References

[1]

Altmeyer S, Burguière C (2009) A new notion of useful cache block to improve the bounds of cache-related preemption delay. In: ECRTS, pp 109-118.

[2]

Altmeyer S, Maiza C, Reineke J (2010) Resilience analysis: tightening the crpd bound for set-associative caches. In: LCTES, pp 153-162.

[3]

Altmeyer S, Davis RI, Maiza C (2011) Cache related pre-emption aware response time analysis for fixed priority pre-emptive systems. In: RTSS, pp 261-271.

[4]

Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Syst 48(5):499-526.

Digital Library

[5]

Altmeyer S, Douma R, Lunniss W, Davis RI (2014) Evaluation of cache partitioning for hard real-time systems. In: ECRTS, pp 15-26.

[6]

Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8:284-292.

[7]

Baruah S, Burns A (2006) Sustainable scheduling analysis. In: RTSS, pp 159-168.

[8]

Baruah SK, Mok AK, Rosier LE (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11th real-time systems symposium. IEEE Computer Society Press, Los Alamitos, pp 182-190.

[9]

Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: OSPERT, pp 33-44.

[10]

Bini E, Buttazzo G (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129-154.

Digital Library

[11]

Bril RJ, Altmeyer S, van den Heuvel M, Davis R, Behnam M (2014) Integrating cache-related preemption delays into analysis of fixed priority scheduling with pre-emption thresholds. In: RTSS' 14.

[12]

Bui BD, Caccamo M, Sha L, Martinez J (2008) Impact of cache partitioning on multi-tasking real time embedded systems. In: RTCSA, pp 101-110.

[13]

Burguière C, Reineke J, Altmeyer S (2009) Cache-related preemption delay computation for set-associative caches--pitfalls and solutions. In: WCET.

[14]

Busquets-Mataix JV, Wellings A (1997) Hybrid instruction cache partitioning for preemptive real-time systems. In: RTS.

[15]

Busquets-Mataix JV, Serrano JJ, Ors R, Gil P, Wellings A (1996) Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In: RTAS, pp 204-212.

[16]

Davis R, Zabos A, Burns A (2008) Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans Comput 57:1261-1276.

Digital Library

[17]

Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: IFIP Congress, pp 807-813.

[18]

Ferdinand C, Heckmann R (2004) aiT: worst case execution time prediction by static program analysis. In: IFIP, pp 377-384.

[19]

George L, Voluceau DD, BLCC (France) (1996) Preemptive and non-preemptive real-time uniprocessor scheduling.

[20]

Gustafsson J, Betts A, Ermedahl A, Lisper B (2010) The Mälardalen WCET benchmarks--past, present and future. In: WCET, pp 137-147.

[21]

Higbee L (1990) Quick and easy cache performance analysis. SIGARCH Comput Archit News 18(2):33-44.

Digital Library

[22]

Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390-395.

[23]

Kirk DB, Strosnider JK (1990) Smart (strategic memory allocation for real-time) cache design. In: RTSS, pp 322-330.

[24]

Lee CG, Hahn J, Seo YM, Min S, Ha R, Hong S, Park CY, Lee M, Kim CS (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700-713.

Digital Library

[25]

Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20:46-61.

Digital Library

[26]

Lundqvist T, Stenström P (1999) Timing anomalies in dynamically scheduled microprocessors. In: RTSS, pp 12-21.

[27]

Lunniss W, Altmeyer S, Davis RI (2012) Optimising task layout to increase schedulability via reduced cache related pre-emption delays. In: RTNS, pp 161-170.

[28]

Lunniss W, Altmeyer S, Maiza C, Davis R (2013) Integrating cache related pre-emption delay analysis into edf scheduling. In: RTAS, pp 75-84.

[29]

Lunniss W, Altmeyer S, Lipari G, Davis RI (2014) Accounting for cache related pre-emption delays in hierarchical scheduling. In: RTNS' 14.

[30]

Lunniss W, Altmeyer S, Guiseppe L, Davis RI (2015) Cache related pre-emption delays in hierarchical scheduling. J Real-Time Syst.

[31]

Meumeu Yomsi P, Sorel Y (2007) Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems. In: ECRTS, pp 280-290.

[32]

Mueller F (1995) Compiler support for software-based cache partitioning. SIGPLAN Not 30(11):125-133.

Digital Library

[33]

Nemer F, Cassé H, Sainrat P, Bahsoun JP, Michiel MD (2006) Papabench: a free real-time benchmark. In: WCET. http://drops.dagstuhl.de/opus/volltexte/2006/678

[34]

Petters SM, Farber G (2001) Scheduling analysis with respect to hardware related preemption delay. In: Workshop on real-time embedded systems.

[35]

Plazar S, Lokuciejewski P, Marwedel P (2009) Wcet-aware software based cache partitioning formulti-task real-time systems. In: WCET. http://drops.dagstuhl.de/opus/volltexte/2009/2286

[36]

Puaut I, Decotigny D (2002) Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In: RTSS, pp 114-124. http://dl.acm.org/citation.cfm?id=827272.829141

[37]

Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19-39.

Digital Library

[38]

Saksena M, Wang Y (2000) Scalable real-time system design using preemption thresholds. In: RTSS' 10.

[39]

Staschulat J, Schliecker S, Ernst R (2005) Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In: ECRTS, pp 41-48.

[40]

Tan Y, Mooney V (2007) Timing analysis for preemptive multi-tasking real-time systems with caches. Trans Embed Comput Syst 6(1):7.

Digital Library

[41]

Vera X, Lisper B, Xue J (2007) Data cache locking for tight timing calculations. ACM Trans Embed Comput Syst 7(1):4:1-4:38.

Digital Library

[42]

Wang C, Gu Z, Zeng H (2015) Integration of cache partitioning and preemption threshold scheduling to improve schedulability of hard real-time systems. In: ECRTS.

[43]

Wang Y, Saksena M (1999) Scheduling fixed-priority tasks with pre-emption threshold. In: RTCSA, pp 328-338.

[44]

Wolf JL, Stone HS, Thiébaut D (1992) Synthetic traces for trace-driven simulation of cache memories. IEEE Trans Comput 41(4):388-410.

[45]

Ye Y, West R, Cheng Z, Li Y (2014) Coloris: a dynamic cache partitioning system using page coloring. In: Proceedings of the 23rd international conference on parallel architectures and compilation, PACT '14, pp 381-392.

[46]

Zhang F, Burns A (2009) Schedulability analysis for real-time systems with edf scheduling. IEEE Trans Comput 58(9):1250-1258.

Digital Library

Cited By

Sun BKloda TArribas Garcia SGracioli GCaccamo M(2023)Minimizing Cache Usage for Real-time SystemsProceedings of the 31st International Conference on Real-Time Networks and Systems10.1145/3575757.3593651(200-211)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1145/3575757.3593651
Zhang ZShen YSun BKloda TCaccamo M(2022)Memory allocation for low-power real-time embedded microcontroller: a case study2022 IEEE 27th International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA52439.2022.9921611(1-4)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1109/ETFA52439.2022.9921611
Davis RGriffin DBate I(2022)A framework for multi-core schedulability analysis accounting for resource stress and sensitivityReal-Time Systems10.1007/s11241-022-09377-858:4(456-508)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11241-022-09377-8
Show More Cited By

On the effectiveness of cache partitioning in hard real-time systems
1. General and reference
  1. Cross-computing tools and techniques
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Integration of Cache Partitioning and Preemption Threshold Scheduling to Improve Schedulability of Hard Real-Time Systems
ECRTS '15: Proceedings of the 2015 27th Euromicro Conference on Real-Time Systems

For preemptive scheduling with shared cache, different tasks may cause interference in the shared cache, leading to Cache-Related Preemption Overhead (CRPD). Cache partitioning is a well-known technique for mitigating unpredictable cache interference in ...
Cache-Partitioned Preemption Threshold Scheduling
Special Issue on VIPES, Special Issue on ICESS2015 and Regular Papers

For preemptive scheduling with shared cache, different tasks may cause interference in the shared cache, leading to Cache-Related Preemption Overhead (CRPD). Cache partitioning can be used to reduce or eliminate CRPD. We propose integration of cache ...
Adding instruction cache effect to schedulability analysis of preemptive real-time systems
RTAS '96: Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96)

Cache memories are commonly avoided in real time systems because of their unpredictable behavior. Recently, some research has been done to obtain tighter bounds on the worst case execution time (WCET) of cached programs. These techniques usually assume ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Real-Time Systems

Real-Time Systems Volume 52, Issue 5

September 2016

167 pages

ISSN:0922-6443

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun BKloda TArribas Garcia SGracioli GCaccamo M(2023)Minimizing Cache Usage for Real-time SystemsProceedings of the 31st International Conference on Real-Time Networks and Systems10.1145/3575757.3593651(200-211)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1145/3575757.3593651
Zhang ZShen YSun BKloda TCaccamo M(2022)Memory allocation for low-power real-time embedded microcontroller: a case study2022 IEEE 27th International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA52439.2022.9921611(1-4)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1109/ETFA52439.2022.9921611
Davis RGriffin DBate I(2022)A framework for multi-core schedulability analysis accounting for resource stress and sensitivityReal-Time Systems10.1007/s11241-022-09377-858:4(456-508)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11241-022-09377-8
Ghosh SBhargava LSahula V(2021)SRCP: sharing and reuse-aware replacement policy for the partitioned cache in multicore systemsDesign Automation for Embedded Systems10.1007/s10617-021-09251-z25:3(193-211)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10617-021-09251-z
Guo ZYang KYao FAwad AHung CCerny TShin DBechini A(2020)Inter-task cache interference aware partitioned real-time schedulingProceedings of the 35th Annual ACM Symposium on Applied Computing10.1145/3341105.3374014(218-226)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3341105.3374014
Rashid SNelissen GTovar EOuhammou YRidouard FGrolleau EJan MBehnam M(2018)Trading Between Intra- and Inter-Task Cache Interference to Improve SchedulabilityProceedings of the 26th International Conference on Real-Time Networks and Systems10.1145/3273905.3273924(125-136)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3273905.3273924
Melani ABertogna MDavis RBonifaci VMarchetti-Spaccamela AButtazzo G(2017)Exact Response Time Analysis for Fixed Priority Memory-Processor Co-SchedulingIEEE Transactions on Computers10.1109/TC.2016.261481966:4(631-646)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TC.2016.2614819
Davis RAltmeyer SReineke JPlantec ASinghoff FFaucou SPinho L(2016)Analysis of Write-back Caches under Fixed-priority Preemptive and Non-preemptive SchedulingProceedings of the 24th International Conference on Real-Time Networks and Systems10.1145/2997465.2997476(309-318)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2997465.2997476
Gu ZWang CZeng H(2016)Cache-Partitioned Preemption Threshold SchedulingACM Transactions on Embedded Computing Systems10.1145/295005716:1(1-30)Online publication date: 23-Oct-2016
https://dl.acm.org/doi/10.1145/2950057
Meng FSu XQu Z(2016)Nonlinear approach for estimating WCET during programming phaseCluster Computing10.1007/s10586-016-0606-519:3(1449-1459)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10586-016-0606-5

View Options

View options

Get Access

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents