research-article

Exploring locking & partitioning for predictable shared caches on multi-cores

Authors:

Vivy Suhendra,

Tulika MitraAuthors Info & Claims

DAC '08: Proceedings of the 45th annual Design Automation Conference

Pages 300 - 303

https://doi.org/10.1145/1391469.1391545

Published: 08 June 2008 Publication History

Get Access

Abstract

Multi-core architectures consisting of multiple processing cores on a chip have become increasingly prevalent. Synthesizing hard real-time applications onto these platforms is quite challenging, as the contention among the cores for various shared resources leads to inherent timing unpredictability. This paper proposes the use of shared cache in a predictable manner through a combination of locking and partitioning mechanisms. We explore possible design choices and evaluate their effects on the worst-case application performance. Our study reveals certain design principles that strongly dictate the performance of a predictable memory hierarchy.

References

[1]

J. Anderson, J. Calandrino, and U. Devi. Real-time scheduling on multicore platforms. In RTAS, 2006.

Digital Library

Google Scholar

[2]

J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms. In J. Y.-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman Hall/CRC Press, 2004.

Google Scholar

[3]

D. Chiou. Extending the reach of microprocessors: column and curious caching. PhD thesis, MIT, 1999.

Digital Library

Google Scholar

[4]

D. Kirk. SMART (Strategic Memory Allocation for Real-Time) Cache Design. In RTSS, 1989.

Google Scholar

[5]

Y.-T. Li and S. Malik. Performance Analysis of Real-time Embedded Software. Springer, 1998.

Digital Library

Google Scholar

[6]

J. López, M. García, J. Díaz, and D. García. Worst-Case Utilization Bound for EDF Scheduling on Real-Time Multiprocessor Systems. In ECRTS, 2000.

Crossref

Google Scholar

[7]

T. Lundqvist and P. Stenström. An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Systems, 17(2/3), 1999.

Digital Library

Google Scholar

[8]

I. Puaut. WCET-centric software-controlled instruction caches for hard real-time systems. In ECRTS, 2006.

Digital Library

Google Scholar

[9]

I. Puaut and D. Decotigny. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In RTSS, 2002.

Digital Library

Google Scholar

[10]

R. Reddy and P. Petrov. Eliminating inter-process cache interference through cache reconfigurability for real-time and low-power embedded multi-tasking systems. In CASES, 2007.

Digital Library

Google Scholar

[11]

J. Sasinowski and J. Strosnider. A dynamic programming algorithm for cache memory partitioning for real-time systems. IEEE Transactions on Computers, 42(8), 1993.

Digital Library

Google Scholar

[12]

G. Suh, L. Rudolph, and S. Devadas. Dynamic Cache Partitioning for Simultaneous Multithreading Systems. In PDCS, 2001.

Google Scholar

[13]

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

Digital Library

Google Scholar

[14]

X. Vera, B. Lisper, and J. Xue. Data cache locking for higher program predictability. In SIGMETRICS, 2003.

Digital Library

Google Scholar

Cited By

View all

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
Lin YDeng QHan MFeng ZWang SPeng Q(2024)LAG-based schedulability analysis for preemptive global EDF scheduling with dynamic cache allocationJournal of Systems Architecture10.1016/j.sysarc.2023.103045147(103045)Online publication date: Feb-2024
https://doi.org/10.1016/j.sysarc.2023.103045
Pujol RHassan MTabani HAbella JCazorla FHong JLanperne MPark JCerny TShahriar H(2023)Tracking Coherence-Related Contention Delays in Real-Time Multicore SystemsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577631(461-470)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577631
Show More Cited By

Index Terms

Exploring locking & partitioning for predictable shared caches on multi-cores
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Exploring cache bypassing and partitioning for multi-tasking on GPUs
ICCAD '17: Proceedings of the 36th International Conference on Computer-Aided Design

Graphics Processing Units (GPUs) computing has become ubiquitous for embedded system, evidenced by its wide adoption for various general purpose applications. As more and more applications are accelerated by GPUs, multi-tasking scenario starts to ...
Compile-time decided instruction cache locking using worst-case execution paths
CODES+ISSS '07: Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis

Caches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access results in a definite cache hit or miss. This unpredictability is highly undesired for real-time systems. The Worst-Case Execution Time (...
A Survey of Techniques for Cache Locking
Special Section on New Physical Design Techniques for the Next Generation Integration Technology and Regular Papers

Cache memory, although important for boosting application performance, is also a source of execution time variability, and this makes its use difficult in systems requiring worst-case execution time (WCET) guarantees. Cache locking is a promising ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '08: Proceedings of the 45th annual Design Automation Conference

June 2008

993 pages

ISBN:9781605581156

DOI:10.1145/1391469

General Chair:
Limor Fix
Intel Research Pittsburgh, Pittsburgh, PA

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: 08 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

DAC '08

Sponsor:

SIGDA

DAC '08: The 45th Annual Design Automation Conference 2008

June 8 - 13, 2008

California, Anaheim

Acceptance Rates

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

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
534
Total Downloads

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

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Lin YDeng QHan MFeng ZWang SPeng Q(2024)LAG-based schedulability analysis for preemptive global EDF scheduling with dynamic cache allocationJournal of Systems Architecture10.1016/j.sysarc.2023.103045147(103045)Online publication date: Feb-2024
https://doi.org/10.1016/j.sysarc.2023.103045
Pujol RHassan MTabani HAbella JCazorla FHong JLanperne MPark JCerny TShahriar H(2023)Tracking Coherence-Related Contention Delays in Real-Time Multicore SystemsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577631(461-470)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577631
Sun BRoy DKloda TBastoni APellizzoni RCaccamo M(2023)Co-Optimizing Cache Partitioning and Multi-Core Task Scheduling: Exploit Cache Sensitivity or Not?2023 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS59052.2023.00028(224-236)Online publication date: 5-Dec-2023
https://doi.org/10.1109/RTSS59052.2023.00028
Lin YSun JDeng QHan MFeng ZWang S(2023)LAG-Based Analysis for Preemptive Global Scheduling with Dynamic Cache Allocation2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA58653.2023.00022(107-116)Online publication date: 30-Aug-2023
https://doi.org/10.1109/RTCSA58653.2023.00022
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
Shen YXiao JPimentel AGrosser TLee K(2022)TCPS: a task and cache-aware partitioned scheduler for hard real-time multi-core systemsProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535067(37-49)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535067
Xiao JShen YPimentel A(2022)Cache Interference-aware Task Partitioning for Non-preemptive Real-time Multi-core SystemsACM Transactions on Embedded Computing Systems10.1145/348758121:3(1-28)Online publication date: 28-May-2022
https://dl.acm.org/doi/10.1145/3487581
Lugo TLozano SFernandez JCarretero J(2022)A Survey of Techniques for Reducing Interference in Real-Time Applications on Multicore PlatformsIEEE Access10.1109/ACCESS.2022.315189110(21853-21882)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3151891
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
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Exploring cache bypassing and partitioning for multi-tasking on GPUs

Compile-time decided instruction cache locking using worst-case execution paths

A Survey of Techniques for Cache Locking