research-article

Time-Analysable Non-Partitioned Shared Caches for Real-Time Multicore Systems

Authors:

Mladen Slijepcevic,

Leonidas Kosmidis,

Eduardo Quiñones,

Francisco J. CazorlaAuthors Info & Claims

DAC '14: Proceedings of the 51st Annual Design Automation Conference

Pages 1 - 6

https://doi.org/10.1145/2593069.2593235

Published: 01 June 2014 Publication History

Abstract

Shared caches in multicores challenge Worst-Case Execution Time (WCET) estimation due to inter-task interferences. Hardware and software cache partitioning address this issue although they complicate data sharing among tasks and the Operating System (OS) task scheduling and migration. In the context of Probabilistic Timing Analysis (PTA) time-randomised caches are used. We propose a new hardware mechanism to control inter-task interferences in shared time-randomised caches without the need of any hardware or software partitioning. Our proposed mechanism effectively bounds inter-task interferences by limiting the cache eviction frequency of each task, while providing tighter WCET estimates than cache partitioning algorithms. In a 4-core multicore processor setup our proposal improves cache partitioning by 56% in terms of guaranteed performance and 16% in terms of average performance.

References

[1]

Guidelines and methods for conducting the safety assessment process on civil airborne systems and equipment. ARP4761, 2001.

[2]

J. Abella, E. Quiñones, T. Vardanega, and F.J. Cazorla. Measurement-based probabilistic timing analysis and i.i.d property. White Paper. 2013. http://www.proartis-project.eu/publications/MBPTA-white-paper.

[3]

AUTOSAR. Technical Overview V2.0.1, 2006.

[4]

G. Bernat, A. Colin, and S.M. Petters. WCET analysis of probabilistic hard real-time systems. In IEEE Real-Time Systems Symposium (RTSS 2002), Austin, Texas (USA), 2002.

Digital Library

[5]

F.J. Cazorla et al. PROARTIS: Probabilistically analysable real-time systems. ACM TECS, 2013.

Digital Library

[6]

S. Chattopadhyay, A. Roychoudhury, and T. Mitra. Modeling shared cache and bus in multi-cores for timing analysis. In 13th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2010), St. Goar, Germany, 2010.

Digital Library

[7]

L. Cucu-Grosjean et al. Measurement-based probabilistic timing analysis for multi-path programs. In 24th Euromicro Conference on Real-Time Systems, (ECRTS 2012), 2012.

Digital Library

[8]

R. I. Davis, L. Santinelli, S. Altmeyer, C. Maiza, and L. Cucu-Grosjean. Analysis of probabilistic cache related pre-emption delays. In 25th Euromicro Conference on Real-Time Systems, (ECRTS 2013), 2013.

Digital Library

[9]

W. Feller. An introduction to Probability Theory and Its Applications. John Willer and Sons, 1996.

[10]

C. Ferdinand and R. Wilhelm. Fast and Efficient Cache Behavior Prediction for Real-Time Systems. Real-Time System, XVII, 1999.

Digital Library

[11]

J. Hansen, S Hissam, and G. A. Moreno. Statistical-based WCET estimation and validation. In 9th Workshop on Worst-Case Execution Time (WCET) Analysis, 2009.

[12]

D. Hardy and I. Puaut. WCET analysis of multi-level non-inclusive set-associative instruction caches. In IEEE Real-Time Systems Symposium (RTSS 2008), 2008.

Digital Library

[13]

J. Jalle, L. Kosmidis, J. Abella, E. Quiñones, and F.J. Cazorla. Bus designs for time-probabilistic multicore processors. In Design, Automation and Test in Europe (DATE 2014), 2014.

Digital Library

[14]

H. Kim, A. Kandhalu, and R. Rajkumar. A coordinated approach for practical os-level cache management in multi-core real-time systems. In 25th Euromicro Conference on Real-Time Systems, (ECRTS 2013), Paris, France, 2013.

Digital Library

[15]

L. Kosmidis, J. Abella, E. Quinones, and F.J. Cazorla. A cache design for probabilistically analysable real-time systems. In Design, Automation and Test in Europe (DATE 2013), 2013.

Digital Library

[16]

L. Kosmidis, J. Abella, E. Quiñones, and F.J. Cazorla. Multi-level unified caches for probabilistically time analysable real-time systems. In IEEE Real-Time Systems Symposium (RTSS), 2013.

Digital Library

[17]

L. Kosmidis, T. Vardanega, J. Abella, E. Quiñones, and F.J. Cazorla. Applying measurement-based probabilistic timing analysis to buffer resources. In 13th Workshop on Worst-Case Execution Time (WCET) Analysis, 2013.

[18]

S. Kotz and S. Nadarajah. Extreme value distributions: theory and applications. World Scientific, 2000.

[19]

B. Lesage, D. Hardy, and I. Puaut. WCET analysis of multi-level set-associative data caches. 9th Workshop on Worst-Case Execution Time (WCET) Analysis, 2009.

[20]

J. Liedtke, H. Hartig, and M. Hohmuth. OS-controlled cache predictability for real-time systems. In Real-Time and Embedded Technology and Applications Symp. (RTAS), 1997.

Digital Library

[21]

G. Marsaglia and A. Zaman. A new class of random number generators. Annals of Applied Probability, 1(3):462--480, 1991.

[22]

F. Mueller. Predicting instruction cache behavior. Language, Compilers and Tools for Real-Time Systems, 1994.

[23]

F. Mueller. Compiler support for software-based cache partitioning. In ACM SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems (LCTES), 1995.

Digital Library

[24]

M. Paolieri, E. Quiñones, F.J. Cazorla, G. Bernat, and M. Valero. Hardware support for WCET analysis of hard real-time multicore systems. In 36th International Symposium on Computer Architecture (ISCA 2009), 2009.

Digital Library

[25]

M. Paolieri, E. Quiñones, F.J. Cazorla, and M. Valero. An Analyzable Memory Controller for Hard Real-Time CMPs. Embedded System Letters (ESL), 2009.

Digital Library

[26]

J. Poovey. Characterization of the EEMBC Benchmark Suite. North Carolina State University, 2007.

[27]

J. Reineke, D. Grund, C. Berg, and R. Wilhelm. Timing predictability of cache replacement policies. Real-Time Systems, 37:99--122, November 2007.

Digital Library

[28]

H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET prediction by separated cache andpath analyses. Real-Time Syst., 18(2/3), May 2000.

Digital Library

[29]

B. Ward, J. Herman, C. Kenna, and J. Anderson. Making shared caches more predictable on multicore platforms. In 25th Euromicro Conf. on Real-Time Systems, (ECRTS), 2013.

Digital Library

[30]

F. Wartel et al. Measurement-based probabilistic timing analysis: Lessons from an integrated-modular avionics case study. In 8th IEEE International Symposium on Industrial Embedded Systems (SIES), Porto, Portugal, 2013.

[31]

Wilhelm R. et al. The worst-case execution-time problem overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems, 7:1--53, May 2008.

Digital Library

[32]

W. Zhang and J. Yan. Static timing analysis of shared caches for multicore processors. Journal of Computing Science and Engineering, 6(4), 2012.

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
Barrera JKosmidis LTabani HAbella JCazorla F(2022)Contention Tracking in GPU Last-Level Cache2022 IEEE 40th International Conference on Computer Design (ICCD)10.1109/ICCD56317.2022.00021(76-79)Online publication date: Oct-2022
https://doi.org/10.1109/ICCD56317.2022.00021
Show More Cited By

Index Terms

Time-Analysable Non-Partitioned Shared Caches for Real-Time Multicore Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Recommendations

Multi-level Unified Caches for Probabilistically Time Analysable Real-Time Systems
RTSS '13: Proceedings of the 2013 IEEE 34th Real-Time Systems Symposium

Caches are key resources in high-end processor architectures to increase performance. In fact, most high-performance processors come equipped with a multi-level cache hierarchy. In terms of guaranteed performance, however, cache hierarchies severely ...
Smaller Split L-1 Data Caches for Multi-core Processing Systems
ISPAN '09: Proceedings of the 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks

As more cores (processing elements) are included in a single chip, it is likely that the sizes of per core L-1 caches will become smaller while more cores will share L-2 cache resources. It becomes more critical to improve the use of L-1 caches and ...
Integrated instruction cache analysis and locking in multitasking real-time systems
DAC '13: Proceedings of the 50th Annual Design Automation Conference

Cache locking improves timing predictability at the cost of performance. We explore a novel approach that opportunistically employs both cache analysis and locking to enhance schedulability in preemptive multi-tasking real-time systems. The cache is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DAC '14: Proceedings of the 51st Annual Design Automation Conference

June 2014

1249 pages

ISBN:9781450327305

DOI:10.1145/2593069

Copyright © 2014 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]

In-Cooperation

EDAC: Electronic Design Automation Consortium
SIGBED: ACM Special Interest Group on Embedded Systems
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CEDA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

DAC '14

DAC '14: The 51st Annual Design Automation Conference 2014

June 1 - 5, 2014

CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
162
Total Downloads

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

Reflects downloads up to 12 Nov 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
Barrera JKosmidis LTabani HAbella JCazorla F(2022)Contention Tracking in GPU Last-Level Cache2022 IEEE 40th International Conference on Computer Design (ICCD)10.1109/ICCD56317.2022.00021(76-79)Online publication date: Oct-2022
https://doi.org/10.1109/ICCD56317.2022.00021
Reghenzani FMassari GFornaciari W(2020)Timing Predictability in High-Performance Computing with Probabilistic Real-TimeIEEE Access10.1109/ACCESS.2020.3038559(1-1)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3038559
Cazorla FKosmidis LMezzetti EHernandez CAbella JVardanega T(2019)Probabilistic Worst-Case Timing AnalysisACM Computing Surveys10.1145/330128352:1(1-35)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3301283
Slijepcevic MHernandez CAbella JCazorla F(2019)Time-Randomized Wormhole NoCs for Critical ApplicationsACM Journal on Emerging Technologies in Computing Systems10.1145/328102915:1(1-23)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3281029
Trilla DHernandez CAbella JCazorla F(2018)Cache side-channel attacks and time-predictability in high-performance critical real-time systemsProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196003(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196003
Arcaro LSilva KOliveira R(2018)On the Reliability and Tightness of GP and Exponential Models for Probabilistic WCET EstimationACM Transactions on Design Automation of Electronic Systems10.1145/318515423:3(1-27)Online publication date: 16-Mar-2018
https://dl.acm.org/doi/10.1145/3185154
Silva KArcaro Lde Oliveira Dde Oliveira R(2018)An Empirical Study on the Adequacy of MBPTA for Tasks Executed on a Complex Computer Architecture with Linux2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA.2018.8502513(321-328)Online publication date: Sep-2018
https://doi.org/10.1109/ETFA.2018.8502513
Davis RAltmeyer SIndrusiak LMaiza CNelis VReineke J(2018)An extensible framework for multicore response time analysisReal-Time Systems10.1007/s11241-017-9285-454:3(607-661)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11241-017-9285-4
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 Table of Contents