research-article

Precise timing analysis for direct-mapped caches

Authors:

Jan ReinekeAuthors Info & Claims

DAC '13: Proceedings of the 50th Annual Design Automation Conference

Article No.: 148, Pages 1 - 10

https://doi.org/10.1145/2463209.2488917

Published: 29 May 2013 Publication History

Get Access

Abstract

Safety-critical systems require guarantees on their worst-case execution times. This requires modelling of speculative hardware features such as caches that are tailored to improve the average-case performance, while ignoring the worst case, which complicates the Worst Case Execution Time (WCET) analysis problem. Existing approaches that precisely compute WCET suffer from state-space explosion. In this paper, we present a novel cache analysis technique for direct-mapped instruction caches with the same precision as the most precise techniques, while improving analysis time by up to 240 times. This improvement is achieved by analysing individual control points separately, and carrying out optimisations that are not possible with existing techniques.

References

[1]

MicroBlaze Processor Reference Guide. www.xilinx.com (Last accessed: 01/10/2012).

Google Scholar

[2]

D. Bui, E. Lee, I. Liu, H. Patel, and J. Reineke. Temporal isolation on multiprocessing architectures. In Proc. of DAC'11, pages 274--279, San Diego, California, June 2011.

Digital Library

Google Scholar

[3]

H. Ding, Y. Liang, and T. Mitra. WCET-centric partial instruction cache locking. In Proc. of DAC'12, pages 412--420, San Francisco, California, June 2012.

Digital Library

Google Scholar

[4]

C. Ferdinand, F. Martin, R. Wilhelm, and M. Alt. Cache Behavior Prediction by Abstract Interpretation. Science of Computer Programming, 35:163--189, November 1999.

Digital Library

Google Scholar

[5]

M. Kuo, R. Sinha, and P. S. Roop. Efficient WCRT Analysis of Synchronous Programs using Reachability. In Proc. of DAC'11, San Diego, USA, June 2011.

Digital Library

Google Scholar

[6]

M. Kuo, L. H. Yoong, S. Andalam, and P. Roop. Determining the worst-case reaction time of IEC 61499 function blocks. In Proc. INDIN'10, pages 1104--1109, July 2010.

Crossref

Google Scholar

[7]

Y.-T. S. Li, S. Malik, and A. Wolfe. Performance estimation of embedded software with instruction cache modeling. ACM Trans. Des. Autom. Electron. Syst., 4(3):257--279, July 1999.

Digital Library

Google Scholar

[8]

Y. Liang and T. Mitra. Static analysis for fast and accurate design space exploration of caches. In Proc. of CODES+ISSS'08, pages 103--108, Atlanta, GA, USA, 2008.

Digital Library

Google Scholar

[9]

H. S. Negi, T. Mitra, and A. Roychoudhury. Accurate Estimation of Cache-Related Preemption Delay. In Proc. of CODES+ISSS'03, pages 201--206, CA, USA, 2003.

Digital Library

Google Scholar

[10]

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

Digital Library

Google Scholar

[11]

H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and Precise WCET Prediction by Separated Cache and Path Analyses. Real-Time Systems, 18:157--179, 1999.

Digital Library

Google Scholar

[12]

R. Wilhelm et al. The Worst-Case Execution-Time Problem---Overview of Methods and Survey of Tools. Transactions on Embedded Computing Systems, 7(3):1--53, 2008.

Digital Library

Google Scholar

Cited By

View all

Nagar KSrikant Y(2017)Refining Cache Behavior Prediction Using Cache Miss PathsACM Transactions on Embedded Computing Systems10.1145/303554116:4(1-26)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3035541
Chang WGoswami DChakraborty SJu LXue CAndalam S(2017)Memory-Aware Embedded Control Systems DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.261393336:4(586-599)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2613933
Chang WZhang LRoy DChakraborty S(2017)Control/Architecture Codesign for Cyber-Physical SystemsHandbook of Hardware/Software Codesign10.1007/978-94-017-7358-4_37-1(1-40)Online publication date: 10-Apr-2017
https://doi.org/10.1007/978-94-017-7358-4_37-1
Show More Cited By

Index Terms

Precise timing analysis for direct-mapped caches
1. Hardware
  1. Hardware validation
  2. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Recommendations

SELECTIVE VICTIM CACHING: A METHOD TO IMPROVE THE PERFORMANCE OF DIRECT-MAPPED CACHES
Opportunistic compression for direct-mapped DRAM caches
MEMSYS '18: Proceedings of the International Symposium on Memory Systems

Large off-chip DRAM caches offer performance and bandwidth improvements for many systems by bridging the gap between on-chip last level caches and off-chip memories. To avoid the high hit latency resulting from serial DRAM accesses for tags and data, ...
WCET Analysis with MRU Caches: Challenging LRU for Predictability
RTAS '12: Proceedings of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium

Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most ...

Comments

Information & Contributors

Information

Published In

DAC '13: Proceedings of the 50th Annual Design Automation Conference

May 2013

1285 pages

ISBN:9781450320719

DOI:10.1145/2463209

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

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '13

Sponsor:

EDAC
SIGDA

DAC '13: The 50th Annual Design Automation Conference 2013

May 29 - June 7, 2013

Texas, Austin

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

6
Total Citations
View Citations
174
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nagar KSrikant Y(2017)Refining Cache Behavior Prediction Using Cache Miss PathsACM Transactions on Embedded Computing Systems10.1145/303554116:4(1-26)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3035541
Chang WGoswami DChakraborty SJu LXue CAndalam S(2017)Memory-Aware Embedded Control Systems DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.261393336:4(586-599)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2613933
Chang WZhang LRoy DChakraborty S(2017)Control/Architecture Codesign for Cyber-Physical SystemsHandbook of Hardware/Software Codesign10.1007/978-94-017-7358-4_37-1(1-40)Online publication date: 10-Apr-2017
https://doi.org/10.1007/978-94-017-7358-4_37-1
Chang WZhang LRoy DChakraborty S(2017)Control/Architecture Codesign for Cyber-Physical SystemsHandbook of Hardware/Software Codesign10.1007/978-94-017-7267-9_37(1221-1260)Online publication date: 27-Sep-2017
https://doi.org/10.1007/978-94-017-7267-9_37
Chang KSinha SCline BSoutherland RDoherty MYeric GLim S(2016)Cascade2D: A design-aware partitioning approach to monolithic 3D IC with 2D commercial tools2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1145/2966986.2967013(1-8)Online publication date: 7-Nov-2016
https://dl.acm.org/doi/10.1145/2966986.2967013
Chakraborty SAl Faruque MChang WGoswami DWolf MZhu Q(2016)Automotive Cyber–Physical Systems: A Tutorial IntroductionIEEE Design & Test10.1109/MDAT.2016.257359833:4(92-108)Online publication date: Aug-2016
https://doi.org/10.1109/MDAT.2016.2573598

View Options

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

SELECTIVE VICTIM CACHING: A METHOD TO IMPROVE THE PERFORMANCE OF DIRECT-MAPPED CACHES

Opportunistic compression for direct-mapped DRAM caches

WCET Analysis with MRU Caches: Challenging LRU for Predictability

Comments

Information

Published In

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations