Article

Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison

Authors:

Isabelle Puaut,

Christophe PaisAuthors Info & Claims

DATE '07: Proceedings of the conference on Design, automation and test in Europe

Pages 1484 - 1489

Published: 16 April 2007 Publication History

Abstract

We propose in this paper an algorithm for off-line selection of the contents of on-chip memories. The algorithm supports two types of on-chip memories, namely locked caches and scratchpad memories. The contents of on-chip memory, although selected off-line, is changed at run-time, for the sake of scalability with respect to task size. Experimental results show that the algorithm yields to good ratios of on-chip memory accesses on the worst-case execution path, with a tolerable reload overhead, for both types of on-chip memories. Furthermore, we highlight the circumstances under which one type of on-chip memory is more appropriate than the other depending of architectural parameters (cache block size) and application characteristics (basic block size).

References

[1]

C. Berg. PLRU cache domino effects. In 6th International Workshop on Worst-Case Execution Time Analysis, in conjunction with the 18th Euromicro Conference on Real-Time Systems, Dresden, Germany, July 2006.

[2]

A. Colin and I. Puaut. A modular and retargetable framework for tree-based WCET analysis. In Proceedings of the 13th Euromicro Conference on Real-Time Systems, pages 37--44, Delft, The Netherlands, June 2001.

Digital Library

[3]

R. Heckmann, M. Langenbach, S. Thesing, and R. Wilhelm. The influence of processor architecture on the design and the results of WCET tools. Proceedings of the IEEE, 91(7), July 2003.

[4]

M. Kandemir, J. Ramanujam, M. J. Irwin, N. Vijaykrishnan, I. Kadayil, and A. Parikh. Dynamic management of scratchpad memory space. In Proc. of the 38th Design Automation Conference (DAC'01), Dec. 2001.

Digital Library

[5]

L. Li, L. Gao, and J. Xue. Memory coloring: A compiler approach for scratchpad memory management. In Proc. of the 14th International Conference on Parallel Architectures and Compilation Techniques, 2005.

Digital Library

[6]

Y.-T. S. Li, S. Malik, and A. Wolfe. Cache modeling for real-time software: Beyond direct mapped instruction cache. In Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS96), pages 254--263. IEEE, Dec. 1996.

Digital Library

[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):183--207, Nov. 1999.

Digital Library

[8]

T. Lundqvist and P. Stenström. Timing anomalies in dynamically scheduled microprocessors. In IEEE Real-Time Systems Symposium, pages 12--21, 1999.

Digital Library

[9]

A. Marti-Campoy, A. P. Ivars, and J. V. Busquets-Mataix. Static use of locking caches in multitask preemptive real-time systems. In IEEE/IEE Real-Time Embedded Systems Workshop (Satellite of the IEEE Real-Time Systems Symposium), London, UK, Dec. 2001.

[10]

F. Mueller. Timing analysis for instruction caches. Real-Time Systems, 18(2):217--247, May 2000.

Digital Library

[11]

I. Puaut. WCET-centric software-controlled instruction caches for hard real-time systems. In Proceedings of the 18th Euromicro Conference on Real-Time Systems, Dresden, Germany, July 2006.

Digital Library

[12]

I. Puaut and D. Decotigny. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS02), pages 114--123, Austin, Texas, Dec. 2002.

Digital Library

[13]

P. Puschner and A. Burns. A review of worst-case execution-time analysis. Real-Time Systems, 18(2--3):115--128, May 2000. Guest Editorial.

Digital Library

[14]

V. Suhendra, T. Mitra, A. Roychoudhury, and T. Chen. WCET centric data allocation to scratchpad memory. In Proceedings of the 26th IEEE Real-Time Systems Symposium (RTSS05), Dec. 2005.

Digital Library

[15]

S. Udayakumaran and R. Barua. Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Nov. 2003.

Digital Library

[16]

M. Verma, L. Wehmeyer, and P. Marwedel. Cache-aware scratchpad allocation algorithm. In Proceedings of Design Automation and Test in Europe (DATE), Paris, France, Feb. 2004.

Digital Library

Cited By

Louise S(2019)A First Step Toward Using Quantum Computing for Low-level WCETs EstimationsACM Transactions on Architecture and Code Optimization10.1145/333554916:3(1-22)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1145/3335549
Lee MKim S(2019)Time-sensitivity-aware shared cache architecture for multi-core embedded systemsThe Journal of Supercomputing10.1007/s11227-019-02891-w75:10(6746-6776)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11227-019-02891-w
Siddique NBadawy ACook JResnick DJacob B(2017)LMStrProceedings of the International Symposium on Memory Systems10.1145/3132402.3132440(152-165)Online publication date: 2-Oct-2017
https://dl.acm.org/doi/10.1145/3132402.3132440
Show More Cited By

Recommendations

Endurance-Aware Allocation of Data Variables on NVM-Based Scratchpad Memory in Real-Time Embedded Systems
Nonvolatile memory (NVM) has many benefits compared to the traditional static RAM, such as improved reliability and reduced power consumption, but it has long write latency and limited write endurance. Scratchpad memory (SPM) is software-managed small on-...
Data Caches in Multitasking Hard Real-Time Systems
RTSS '03: Proceedings of the 24th IEEE International Real-Time Systems Symposium

Data caches are essential in modern processors, bridgingthe widening gap between main memory and processorspeeds. However, they yield very complex performancemodels, which makes it hard to bound execution timestightly.This paper contributes a new ...
Fetch Caches

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '07: Proceedings of the conference on Design, automation and test in Europe

April 2007

1741 pages

ISBN:9783981080124

General Chair:
Rudy Lauwereins
IMEC and KULeuven, Belgium
,
Program Chair:
Jan Madsen
DTU, Denmark

Sponsors

The EDA Consortium
EDAA: European Design Automation Association
ECSI
SIGDA: ACM Special Interest Group on Design Automation
The IEEE Computer Society TTTC
IEEE Council on Electronic Design Automation (CEDA)
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

EDA Consortium

San Jose, CA, United States

Publication History

Published: 16 April 2007

Check for updates

Qualifiers

Article

Conference

DATE07

Sponsor:

EDAA
SIGDA
The Russian Academy of Sciences

DATE07: Design, Automation and Test in Europe

April 16 - 20, 2007

Nice, France

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
333
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Louise S(2019)A First Step Toward Using Quantum Computing for Low-level WCETs EstimationsACM Transactions on Architecture and Code Optimization10.1145/333554916:3(1-22)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1145/3335549
Lee MKim S(2019)Time-sensitivity-aware shared cache architecture for multi-core embedded systemsThe Journal of Supercomputing10.1007/s11227-019-02891-w75:10(6746-6776)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11227-019-02891-w
Siddique NBadawy ACook JResnick DJacob B(2017)LMStrProceedings of the International Symposium on Memory Systems10.1145/3132402.3132440(152-165)Online publication date: 2-Oct-2017
https://dl.acm.org/doi/10.1145/3132402.3132440
Melani ABertogna MDavis RBonifaci VMarchetti-Spaccamela AButtazzo G(2017)Exact Response Time Analysis for Fixed Priority Memory-Processor Co-SchedulingIEEE Transactions on Computers10.1109/TC.2016.261481966:4(631-646)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TC.2016.2614819
Kuo MAndalam SRoop PFanucci LTeich J(2016)Precision timed industrial automation systemsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972045(1024-1025)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972045
Underwood DCheng A(2016)Timing analysis of P-FRP systemsACM SIGBED Review10.1145/2930957.293096013:2(20-23)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2930957.2930960
Mittal S(2016)A Survey of Techniques for Cache LockingACM Transactions on Design Automation of Electronic Systems10.1145/285879221:3(1-24)Online publication date: 16-May-2016
https://dl.acm.org/doi/10.1145/2858792
Melani ABertogna MBonifaci VMarchetti-Spaccamela AButtazzo GForget J(2015)Memory-processor co-scheduling in fixed priority systemsProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834854(87-96)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834854
Gracioli GAlhammad AMancuso RFröhlich APellizzoni R(2015)A Survey on Cache Management Mechanisms for Real-Time Embedded SystemsACM Computing Surveys10.1145/283055548:2(1-36)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2830555
Ismail MLo DSuh G(2015)Improving worst-case cache performance through selective bypassing and register-indexed cacheProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744855(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744855
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten