research-article

Resilience analysis: tightening the CRPD bound for set-associative caches

Authors:

Sebastian Altmeyer,

Jan ReinekeAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 4

Pages 153 - 162

https://doi.org/10.1145/1755951.1755911

Published: 13 April 2010 Publication History

Abstract

In preemptive real-time systems, scheduling analyses need - in addition to the worst-case execution time - the context-switch cost. In case of preemption, the preempted and the preempting task may interfere on the cache memory.

This interference leads to additional cache misses in the preempted task. The delay due to these cache misses is referred to as the cache-related preemption delay~(CRPD), which constitutes the major part of the context-switch cost.

In this paper, we present a new approach to compute tight bounds on the CRPD for LRU set-associative caches, based on analyses of both the preempted and the preempting task. Previous approaches analyzing both the preempted and the preempting task were either imprecise or unsound.

As the basis of our approach we introduce the notion of resilience: The resilience of a memory block of the preempted task is the maximal number of memory accesses a preempting task could perform without causing an additional miss to this block. By computing lower bounds on the resilience of blocks and an upper bound on the number of accesses by a preempting task, one can guarantee that some blocks may not contribute to the CRPD. The CRPD analysis based on resilience considerably outperforms previous approaches.

References

[1]

Mälardalen WCET benchmark suite. http://www.mrtc.mdh.se/projects/wcet/benchmarks.html.

[2]

Papabench: a free real-time benchmark. http://www.irit.fr/recherches/ARCHI/MARCH/rubrique.php3?id_rubrique=97.

[3]

B. Ackland, D. Anesko, D. Brinthaupt, S. J. Daubert, A. Kalavade, J. Knoblock, E. Micca, M. Moturi, C. J. Nicol, J. H. O'Neill, J. Othmer, E. Sackinger, K. J. Singh, J. Sweet, C. J. Terman, and J.Williams. A single-chip, 1.6 billion, 16-b mac/s multiprocessor dsp,. IEEE Journal of Solid-state circuits, 35(3):412--423, 2000.

[4]

S. Altmeyer and C. Burguiere. A new notion of useful cache block to improve the bounds of cache-related preemption delay. In ECRTS '09, pages 109--118. IEEE Computer Society, 2009.

Digital Library

[5]

C. Ballabriga, H. Casse, and P. Sainrat. An improved approach for set-associative instruction cache partial analysis. In SAC '08, pages 360--367, 2008.

Digital Library

[6]

C. Burguiere, J. Reineke, and S. Altmeyer. Cache-related preemption delay computation for set-associative caches: Pitfalls and solutions. In WCET '09, 2009.

[7]

C. Ferdinand and R. Wilhelm. Fast and efficient cache behavior prediction for real-time systems. Real-Time Systems, 17(2/3):131--181, 1999.

Digital Library

[8]

C.-G. Lee, J. Hahn, S. L. Min, R. Ha, S. Hong, C. Y. Park, M. Lee, and C. S. Kim. Analysis of cache-related preemption delay in fixedpriority preemptive scheduling. In RTSS'96, page 264. IEEE Computer Society, 1996.

Digital Library

[9]

T. Lundqvist and P. Stenstrom. Timing anomalies in dynamically scheduled microprocessors. In RTSS '99, page 12, Washington, DC, USA, 1999. IEEE Computer Society.

Digital Library

[10]

H. S. Negi, T. Mitra, and A. Roychoudhury. Accurate estimation of cache-related preemption delay. In CODES+ISSS'03. ACM, 2003.

Digital Library

[11]

F. Nemer, H. Casse, P. Sainrat, J. P. Bahsoun, and M. D. Michiel. Papabench: a free real-time benchmark. In WCET '06, Dagstuhl, Germany, 2006.

[12]

F. Nemer, H. Casse, P. Sainrat, and J. P. Bahsoun. Inter-task WCET computation for a-way instruction caches. In SIES '08, pages 169--176, 2008.

[13]

A. Rakib, O. Parshin, S. Thesing, and R. Wilhelm. Component-wise i-cache behavior prediction. In ATVA '04, pages 211--229, 2004.

[14]

J. Reineke and D. Grund. Relative competitive analysis of cache replacement policies. In LCTES'08, pages 51--60. ACM, June 2008.

Digital Library

[15]

J. Reineke, B. Wachter, S. Thesing, R. Wilhelm, I. Polian, J. Eisinger, and B. Becker. A definition and classification of timing anomalies. In WCET '06, Dagstuhl, Germany, 2006.

[16]

J. Staschulat and R. Ernst. Multiple process execution in cache related preemption delay analysis. In EMSOFT '04, pages 278--286. ACM, 2004.

Digital Library

[17]

J. Staschulat and R. Ernst. Scalable precision cache analysis for realtime software. ACM TECS, 6(4):25, 2007. ISSN 1539-9087.

Digital Library

[18]

Y. Tan and V. Mooney. Integrated intra- and inter-task cache analysis for preemptive multi-tasking real-time systems. In SCOPES'04, pages 182--199, 2004.

[19]

H. Tomiyama and N. D. Dutt. Program path analysis to bound cacherelated preemption delay in preemptive real-time systems. In CODES'00. ACM, 2000.

Digital Library

Cited By

Rashid SAwan MSouto PBletsas KTovar EBolchini CO'Connor IVerbauwhede IWille R(2022)Cache-aware schedulability analysis of PREM compliant tasksProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540145(1269-1274)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540145
Rashid SAwan MSouto PBletsas KTovar E(2022)Cache-aware Schedulability Analysis of PREM Compliant Tasks2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774670(1269-1274)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774670
Bouquillon FLipari GNiar SHong JBures MPark JCerny T(2022)Improving CRPD analysis for EDF schedulingProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507027(481-490)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507027
Show More Cited By

Index Terms

Resilience analysis: tightening the CRPD bound for set-associative caches
1. Hardware
  1. Hardware validation
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

Cache-Related Preemption Delay Analysis for Multilevel Noninclusive Caches
Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES)

With the rapid growth of complex hardware features, timing analysis has become an increasingly difficult problem. The key to solving this problem lies in the precise and scalable modeling of performance-enhancing processor features (e.g., cache). ...
Resilience analysis: tightening the CRPD bound for set-associative caches
LCTES '10: Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems

In preemptive real-time systems, scheduling analyses need - in addition to the worst-case execution time - the context-switch cost. In case of preemption, the preempted and the preempting task may interfere on the cache memory.

This interference leads ...
Tightening the bounds on feasible preemptions

Data caches are an increasingly important architectural feature in most modern computer systems. They help bridge the gap between processor speeds and memory access times. One inherent difficulty of using data caches in a real-time system is the ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 45, Issue 4

LCTES '10

April 2010

170 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1755951

Issue’s Table of Contents

LCTES '10: Proceedings of the ACM SIGPLAN/SIGBED 2010 conference on Languages, compilers, and tools for embedded systems
April 2010
184 pages
ISBN:9781605589534
DOI:10.1145/1755888
General Chair:
Jaejin Lee
Seoul National University, Korea
,
Program Chair:
Bruce B. Childers
University of Pittsburgh, USA

Copyright © 2010 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

Publication History

Published: 13 April 2010

Published in SIGPLAN Volume 45, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
318
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rashid SAwan MSouto PBletsas KTovar EBolchini CO'Connor IVerbauwhede IWille R(2022)Cache-aware schedulability analysis of PREM compliant tasksProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540145(1269-1274)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540145
Rashid SAwan MSouto PBletsas KTovar E(2022)Cache-aware Schedulability Analysis of PREM Compliant Tasks2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774670(1269-1274)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774670
Bouquillon FLipari GNiar SHong JBures MPark JCerny T(2022)Improving CRPD analysis for EDF schedulingProceedings of the 37th ACM/SIGAPP Symposium on Applied Computing10.1145/3477314.3507027(481-490)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3477314.3507027
Sohal PTabish RDrepper UMancuso R(2022)Profile-driven memory bandwidth management for accelerators and CPUs in QoS-enabled platformsReal-Time Systems10.1007/s11241-022-09382-x58:3(235-274)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11241-022-09382-x
Montasari RTait BJahankhani HCarroll F(2022)An Investigation of Microarchitectural Cache-Based Side-Channel Attacks from a Digital Forensic Perspective: Methods of Exploits and CountermeasuresArtificial Intelligence in Cyber Security: Impact and Implications10.1007/978-3-030-88040-8_11(281-306)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-88040-8_11
Zhang WGuan NJu LTang YLiu WJia Z(2020)Scope-Aware Useful Cache Block Calculation for Cache-Related Pre-Emption Delay Analysis With Set-Associative Data CachesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.293780739:10(2333-2346)Online publication date: Oct-2020
https://doi.org/10.1109/TCAD.2019.2937807
Sohal PTabish RDrepper UMancuso R(2020)E-WarP: A System-wide Framework for Memory Bandwidth Profiling and Management2020 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS49844.2020.00039(345-357)Online publication date: Dec-2020
https://doi.org/10.1109/RTSS49844.2020.00039
Markovic FCarlson JDobrin R(2020)Cache-aware response time analysis for real-time tasks with fixed preemption points2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS48715.2020.00-19(30-42)Online publication date: Apr-2020
https://doi.org/10.1109/RTAS48715.2020.00-19
Li ZHuang CDong XRen C(2020)Resource-efficient cyber-physical systems design: A surveyMicroprocessors and Microsystems10.1016/j.micpro.2020.10318377(103183)Online publication date: Sep-2020
https://doi.org/10.1016/j.micpro.2020.103183
Hahn SReineke JWilhelm R(2015)Towards compositionality in execution time analysisACM SIGBED Review10.1145/2752801.275280512:1(28-36)Online publication date: 27-Mar-2015
https://dl.acm.org/doi/10.1145/2752801.2752805
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents