research-article

Optimal static WCET-aware scratchpad allocation of program code

Authors:

Jan C. KleinsorgeAuthors Info & Claims

DAC '09: Proceedings of the 46th Annual Design Automation Conference

Pages 732 - 737

https://doi.org/10.1145/1629911.1630101

Published: 26 July 2009 Publication History

Abstract

Caches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access will result in a definite cache hit or miss. This unpredictability is highly undesired especially when designing real-time systems where the worst-case execution time (WCET) is one of the key metrics. Scratchpad memories (SPMs) have proven to be a fully predictable alternative to caches. In contrast to caches, however, SPMs require dedicated compiler support.

This paper presents an optimal static SPM allocation algorithm for program code. It minimizes WCETs by placing the most beneficial parts of a program's code in an SPM. Our results underline the effectiveness of the proposed techniques. For a total of 73 realistic benchmarks, we reduced WCETs on average by 7.4% up to 40%. Additionally, the run times of our ILP-based SPM allocator are negligible.

References

[1]

AbsInt Angewandte Informatik GmbH. aiT: Worst-Case Execution Time Analyzers. www.absint.com/ait, 2009.

[2]

A. M. Campoy, I. Puaut, A. P. Ivars, et al. Cache contents selection for statically-locked instruction caches: An Algorithm Comparison. In Proceedings of ECRTS, Palma de Mallorca, July 2005.

Digital Library

[3]

J.-F. Deverge and I. Puaut. WCET-Directed Dynamic Scratchpad Memory Allocation of Data. In Proceedings of ECRTS, Pisa, July 2007.

Digital Library

[4]

J. Engblom. Static Properties of Commercial Embedded Real-Time Programs, and Their Implication for Worst-Case Execution Time Analysis. In Proceedings of RTAS, Vancouver, 1999.

Digital Library

[5]

H. Falk, P. Lokuciejewski, and H. Theiling. Design of a WCET-Aware C Compiler. In Proceedings of ESTIMedia, Seoul, Oct. 2006. ls12- www.cs.tu-dortmund.de/research/activities/wcc.

Digital Library

[6]

H. Falk, S. Plazar, and H. Theiling. Compile Time Decided Instruction Cache Locking Using Worst-Case Execution Paths. In Proceedings of CODES+ISSS, Salzburg, Oct. 2007.

Digital Library

[7]

C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems. In Proceedings of MICRO 30, Washington DC, 1997.

Digital Library

[8]

P. Lokuciejewski, D. Cordes, H. Falk, and P. Marwedel. A Fast and Precise Static Loop Analysis based on Abstract Interpretation, Program Slicing and Polytope Models. In Proceedings of CGO, Mar. 2009.

Digital Library

[9]

Mälardalen WCET Research Group. WCET Benchmarks. www.mrtc.mdh.se/projects/wcet, Sept. 2008.

[10]

I. Puaut. WCET-centric Software-controlled Instruction Caches for Hard Real-Time Systems. In Proceedings of ECRTS, July 2006.

Digital Library

[11]

S. Steinke, L. Wehmeyer, B.-S. Lee, et al. Assigning Program and Data Objects to Scratchpad for Energy Reduction. In Proceedings of DATE, Paris, Mar. 2002.

Digital Library

[12]

V. Suhendra, T. Mitra, A. Roychoudhury, et al. WCET Centric Data Allocation to Scratchpad Memory. In Proceedings of RTSS, Miami, Dec. 2005.

Digital Library

[13]

UTDSP Benchmark Suite. www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html, Sept. 2008.

[14]

M. Verma and P. Marwedel. Advanced Memory Optimization Techniques for Low-Power Embedded Processors. Springer, 2007.

Digital Library

[15]

V. Živojnović, J. M. Velarde, C. Schläger, and H. Meyr. DSPstone: A DSP-Oriented Benchmarking Methodology. In Proceedings of ICSPAT '94, Dallas, 1994.

[16]

L. Wehmeyer and P. Marwedel. Influence of Onchip Scratchpad Memories on WCET Prediction. In Proceedings of WCET, Catania, June 2004.

[17]

L. Wehmeyer and P. Marwedel. Influence of Memory Hierarchies on Predictability for Time Constrained Embedded Software. In Proceedings of DATE, Munich, Mar. 2005.

Digital Library

[18]

L. Wehmeyer and P. Marwedel. Fast, Efficient and Predictable Memory Accesses -- Optimization Algorithms for Memory Architecture Aware Compilation. Springer, 2006.

Digital Library

Cited By

Hsu MHetzelt FGens DMaitland MFranz MChandra SBlincoe KTonella P(2023)A Highly Scalable, Hybrid, Cross-Platform Timing Analysis Framework Providing Accurate Differential Throughput Estimation via Instruction-Level TracingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616246(821-831)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616246
Jadhav SFalk H(2022)Approximating WCET and Energy Consumption for Fast Multi-Objective Memory AllocationProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534889(162-172)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534889
Körür SJungklass PBerekovic M(2022)Echtzeitfähige Ethernet-Kommunikation in automobilen Multicore-Systemen mit hierarchischem SpeicherlayoutEchtzeit 202110.1007/978-3-658-37751-9_10(83-92)Online publication date: 25-May-2022
https://doi.org/10.1007/978-3-658-37751-9_10
Show More Cited By

Index Terms

Optimal static WCET-aware scratchpad allocation of program code
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Static bus schedule aware scratchpad allocation in multiprocessors
LCTES '10

Compiler controlled memories or scratchpad memories offer more predictable program execution times than cache memories. Scratchpad memories are often employed in multi-processor system-on-chip (MPSoC) platforms which seek to meet the performance needs ...
WCET-Aware Function-Level Dynamic Code Management on Scratchpad Memory
Special Issue on Secure and Fault-Tolerant Embedded Computing and Regular Papers

Scratchpad memory (SPM) is a promising on-chip memory choice in real-time and cyber-physical systems where timing is of the utmost importance. SPM has time-predictable characteristics since its data movement between the SPM and the main memory is ...
Static bus schedule aware scratchpad allocation in multiprocessors
LCTES '11: Proceedings of the 2011 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Compiler controlled memories or scratchpad memories offer more predictable program execution times than cache memories. Scratchpad memories are often employed in multi-processor system-on-chip (MPSoC) platforms which seek to meet the performance needs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '09: Proceedings of the 46th Annual Design Automation Conference

July 2009

994 pages

ISBN:9781605584973

DOI:10.1145/1629911

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

Sponsors

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

DAC '09

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC '09: The 46th Annual Design Automation Conference 2009

July 26 - 31, 2009

California, San Francisco

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

86
Total Citations
View Citations
301
Total Downloads

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

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hsu MHetzelt FGens DMaitland MFranz MChandra SBlincoe KTonella P(2023)A Highly Scalable, Hybrid, Cross-Platform Timing Analysis Framework Providing Accurate Differential Throughput Estimation via Instruction-Level TracingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616246(821-831)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616246
Jadhav SFalk H(2022)Approximating WCET and Energy Consumption for Fast Multi-Objective Memory AllocationProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534889(162-172)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534889
Körür SJungklass PBerekovic M(2022)Echtzeitfähige Ethernet-Kommunikation in automobilen Multicore-Systemen mit hierarchischem SpeicherlayoutEchtzeit 202110.1007/978-3-658-37751-9_10(83-92)Online publication date: 25-May-2022
https://doi.org/10.1007/978-3-658-37751-9_10
Bazzaz MHoseinghorban APoursafaei FEjlali A(2021)High-Performance Predictable NVM-Based Instruction Memory for Real-Time Embedded SystemsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2018.28580209:1(441-455)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TETC.2018.2858020
Falk HJadhav SLuppold AMuts KOehlert DPiontek NRoth M(2020)Compilation for Real-Time Systems a Decade After PredatorA Journey of Embedded and Cyber-Physical Systems10.1007/978-3-030-47487-4_10(151-169)Online publication date: 31-Jul-2020
https://doi.org/10.1007/978-3-030-47487-4_10
Hemminki SKuribayashi KKonomi SNurmi PTarkoma S(2019)Crowd ReplicationACM Transactions on Spatial Algorithms and Systems10.1145/33176665:3(1-34)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3317666
Venkataramani VKulkarni AMitra TPeh LChen JShrivastava A(2019)SPECTRUM: a software defined predictable many-core architecture for LTE baseband processingProceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3316482.3326352(82-96)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3316482.3326352
Tabish RMancuso RWasly SPellizzoni RCaccamo M(2019)A real-time scratchpad-centric OS with predictable inter/intra-core communication for multi-core embedded systemsReal-Time Systems10.1007/s11241-019-09340-0Online publication date: 5-Sep-2019
https://doi.org/10.1007/s11241-019-09340-0
Frid NSruk V(2018)Memory-aware multiobjective design space exploration of heteregeneous MPSoC2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)10.23919/MIPRO.2018.8400159(0861-0866)Online publication date: May-2018
https://doi.org/10.23919/MIPRO.2018.8400159
Kuo TChen JChang YHsiu P(2018)Real-Time Computing and the Evolution of Embedded System Designs2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00011(1-12)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00011
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