More Web Proxy on the site http://driver.im/

research-article

Public Access

Handling write backs in multi-level cache analysis for WCET estimation

Authors:

Xenofon KoutsoukosAuthors Info & Claims

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

Pages 208 - 217

https://doi.org/10.1145/3139258.3139269

Published: 04 October 2017 Publication History

Abstract

In this paper, we investigate how to soundly analyze multi-level caches that employ write-back policy at each level for worst-case execution time (WCET) estimation. To the best of our knowledge, there is only one existing approach for dealing with write backs in multi-level cache analysis. However, as shown in the paper, this existing approach is not sound. In order to soundly handle write backs, at a cache level, we need to consider whether a memory block is potentially dirty and when such a potentially dirty block may be evicted from the cache. To this end, we introduce a dirty attribute into persistence analysis for tracking dirty blocks, and over-approximate a write back window for each possible write back. Based on the overestimated write back occurring times, we propose an approach that can soundly deal with write backs in analysis of multi-level (unified) caches for WCET estimation. Possible write back costs are also integrated into path analysis. We evaluate the proposed approach on a set of benchmarks to demonstrate its effectiveness.

References

[1]

Martin Alt, Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. 1996. Cache Behavior Prediction by Abstract Interpretation. In SAS '96. 52--66.

Digital Library

[2]

Sudipta Chattopadhyay, Chong Lee Kee, Abhik Roychoudhury, Timon Kelter, Peter Marwedel, and Heiko Falk. 2012. A Unified WCET Analysis Framework for Multi-core Platforms. In RTAS '12. 99--108.

Digital Library

[3]

Sudipta Chattopadhyay and Abhik Roychoudhury. 2009. Unified Cache Modeling for WCET Analysis and Layout Optimizations. In RTSS '09. 47--56.

Digital Library

[4]

Christoph Cullmann. 2013. Cache Persistence Analysis: Theory and Practice. ACM Transactions on Embedded Computing Systems 12, 1s, Article 40 (March 2013), 25 pages.

Digital Library

[5]

Christian Ferdinand and Reinhard Wilhelm. 1998. On Predicting Data Cache Behavior for Real-Time Systems. In LCTES '98. 16--30.

Digital Library

[6]

Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. 2010. The Mälardalen WCET Benchmarks: Past, Present And Future. In WCET '10. 136--146.

[7]

Damien Hardy, Thomas Piquet, and Isabelle Puaut. 2009. Using Bypass to Tighten WCET Estimates for Multi-Core Processors with Shared Instruction Caches. In RTSS '09. 68--77.

Digital Library

[8]

Damien Hardy and Isabelle Puaut. 2008. WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction Caches. In RTSS '08. 456--466.

Digital Library

[9]

Damien Hardy and Isabelle Puaut. 2011. WCET Analysis of Instruction Cache Hierarchies. Journal of Systems Architecture 57, 7 (Aug. 2011), 677--694.

Digital Library

[10]

Bach Khoa Huynh, Lei Ju, and Abhik Roychoudhury. 2011. Scope-Aware Data Cache Analysis for WCET Estimation. In RTAS '11. 203--212.

Digital Library

[11]

Leonidas Kosmidis, Jaume Abella, Eduardo Quiñones, and Francisco J. Cazorla. 2013. Multi-level Unified Caches for Probabilistically Time Analysable Real-Time Systems. In RTSS '13. 360--371.

Digital Library

[12]

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. 2009. WCET Analysis of Multi-Level Set-Associative Data Caches. In WCET '09. 1--12.

[13]

Benjamin Lesage, Damien Hardy, and Isabelle Puaut. 2010. Shared Data Caches Conflicts Reduction for WCET Computation in Multi-Core Architectures. In RTNS '10. 2283.

[14]

Yan Li, Vivy Suhendra, Yun Liang, Tulika Mitra, and Abhik Roychoudhury. 2009. Timing Analysis of Concurrent Programs Running on Shared Cache Multi-Cores. In RTSS '09. 57--67.

Digital Library

[15]

Yau-Tsun Steven Li and Sharad Malik. 1995. Performance Analysis of Embedded Software Using Implicit Path Enumeration. In DAC '95. 456--461.

Digital Library

[16]

Thomas Lundqvist and Per Stenström. 1999. Timing Anomalies in Dynamically Scheduled Microprocessors. In RTSS '99. 12--.

Digital Library

[17]

Mingsong Lv, Wang Yi, Nan Guan, and Ge Yu. 2010. Combining Abstract Interpretation with Model Checking for Timing Analysis of Multicore Software. In RTSS '10. 339--349.

Digital Library

[18]

Frank Mueller. 1997. Timing Predictions for Multi-Level Caches. In LCTRTS '97. 29--36.

[19]

Frank Mueller. 2000. Timing Analysis for Instruction Caches. Real-Time Systems 18, 2/3 (May 2000), 217--247.

Digital Library

[20]

Harini Ramaprasad and Frank Mueller. 2005. Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns. In RTAS '05. 148--157.

Digital Library

[21]

Rathijit Sen and Y. N. Srikant. 2007. WCET Estimation for Executables in the Presence of Data Caches. In EMSOFT '07. 203--212.

Digital Library

[22]

Tyler Sondag and Hridesh Rajan. 2010. A More Precise Abstract Domain for Multi-level Caches for Tighter WCET Analysis. In RTSS '10. 395--404.

Digital Library

[23]

Jan Staschulat and Rolf Ernst. 2006. Worst Case Timing Analysis of Input Dependent Data Cache Behavior. In ECRTS '06. 227--236.

Digital Library

[24]

Henrik Theiling, Christian Ferdinand, and Reinhard Wilhelm. 2000. Fast and Precise WCET Prediction by Separated Cache and Path Analyses. Real-Time Systems 18, 2/3 (May 2000), 157--179.

Digital Library

[25]

Randall T. White, Frank Mueller, Chris Healy, David Whalley, and Marion Harmon. 1999. Timing Analysis for Data and Wrap-Around Fill Caches. Real-Time Systems 17, 2--3 (Dec. 1999), 209--233.

Digital Library

[26]

Jun Yan and Wei Zhang. 2008. WCET Analysis for Multi-Core Processors with Shared L2 Instruction Caches. In RTAS '08. 80--89.

Digital Library

[27]

Zhenkai Zhang and Xenofon Koutsoukos. 2015. Improving the Precision of Abstract Interpretation Based Cache Persistence Analysis. In LCTES'15. Article 10, 10 pages.

Digital Library

[28]

Zhenkai Zhang and Xenofon Koutsoukos. 2015. Precise Multi-level Inclusive Cache Analysis for WCET Estimation. In RTSS '15. 350--360.

Digital Library

[29]

Zhenkai Zhang and Xenofon Koutsoukos. 2015. Top-Down and Bottom-Up Multi-Level Cache Analysis for WCET Estimation. In RTAS '15. 24--35.

[30]

Zhenkai Zhang and Xenofon Koutsoukos. 2016. Cache-related Preemption Delay Analysis for Multi-level Inclusive Caches. In EMSOFT '16. Article 16, 10 pages.

Digital Library

Cited By

Wu ZKaushik APatel H(2024)High Performance and Predictable Shared Last-level Cache for Safety-Critical SystemsACM Transactions on Embedded Computing Systems10.1145/368730823:6(1-30)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3687308
Wu ZKaushik APatel H(2023)ZeroCost-LLC: Shared LLCs at No Cost to WCL2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00027(249-261)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00027
Rashid SNelissen GTovar E(2021)Tightening the CRPD bound for multilevel non-inclusive cachesJournal of Systems Architecture10.1016/j.sysarc.2021.102340(102340)Online publication date: Dec-2021
https://doi.org/10.1016/j.sysarc.2021.102340
Show More Cited By

Index Terms

Handling write backs in multi-level cache analysis for WCET estimation
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
  2. Real-time systems

Recommendations

WCET analysis of instruction cache hierarchies

With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, caches, multiple cores), most embedded processors use a hierarchy of caches. While much research has been ...
Precise Multi-level Inclusive Cache Analysis for WCET Estimation
RTSS '15: Proceedings of the 2015 IEEE Real-Time Systems Symposium (RTSS)

Multi-level inclusive caches are often used in multi-core processors to simplify the design of cache coherence protocol. However, the use of such cache hierarchies poses great challenges to tight worst-case execution time (WCET) estimation due to the ...
Cache write policies and performance
Special Issue: Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93)

This paper investigates issues involving writes and caches. First, tradeoffs on writes that miss in the cache are investigated. In particular, whether the missed cache block is fetched on a write miss, whether the missed cache block is allocated in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

October 2017

318 pages

ISBN:9781450352864

DOI:10.1145/3139258

Program Chairs:
Enrico Bini
University of Turin, Italy
,
Claire Pagetti
ONERA/ENSEEIHT/TUHH, Toulouse, France

Copyright © 2017 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: 04 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Missouri University of Science and Technology

Conference

RTNS '17

RTNS '17: 25th International Conference on Real-Time Networks and Systems

October 4 - 6, 2017

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
266
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)9

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu ZKaushik APatel H(2024)High Performance and Predictable Shared Last-level Cache for Safety-Critical SystemsACM Transactions on Embedded Computing Systems10.1145/368730823:6(1-30)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3687308
Wu ZKaushik APatel H(2023)ZeroCost-LLC: Shared LLCs at No Cost to WCL2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00027(249-261)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00027
Rashid SNelissen GTovar E(2021)Tightening the CRPD bound for multilevel non-inclusive cachesJournal of Systems Architecture10.1016/j.sysarc.2021.102340(102340)Online publication date: Dec-2021
https://doi.org/10.1016/j.sysarc.2021.102340
Segarra JGran Tejero RViñals V(2021)A generic framework to integrate data caches in the WCET analysis of real-time systemsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2021.102304120:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.sysarc.2021.102304
Kloda TSolieri MMancuso RCapodieci NValente PBertogna M(2019)Deterministic Memory Hierarchy and Virtualization for Modern Multi-Core Embedded Systems2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00009(1-14)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00009
Davis RAltmeyer SReineke J(2018)Response-time analysis for fixed-priority systems with a write-back cacheReal-Time Systems10.1007/s11241-018-9305-z54:4(912-963)Online publication date: 11-Apr-2018
https://doi.org/10.1007/s11241-018-9305-z

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Table of Contents