Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis
Document Open Access Logo

Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis

Authors Sahar Abbaspour, Alexander Jordan, Florian Brandner

PDF
Thumbnail PDF

File

OASIcs.WCET.2014.83.pdf
  • Filesize: 0.55 MB
  • 10 pages

Document Identifiers

Author Details

Sahar Abbaspour
Alexander Jordan
Florian Brandner

Cite As Get BibTex

Sahar Abbaspour, Alexander Jordan, and Florian Brandner. Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis. In 14th International Workshop on Worst-Case Execution Time Analysis. Open Access Series in Informatics (OASIcs), Volume 39, pp. 83-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/OASIcs.WCET.2014.83

Abstract

The growing complexity of modern computer architectures increasingly complicates the prediction of the run-time behavior of software. For real-time systems, where a safe estimation of the program's worst-case execution time is needed, time-predictable computer architectures promise to resolve this problem. A stack cache, for instance, allows the compiler to efficiently cache a program's stack, while static analysis of its behavior remains easy. Likewise, its implementation requires little hardware overhead.

This work introduces an optimization of the standard stack cache to avoid redundant spilling of the cache content to main memory, if the content was not modified in the meantime. At first sight, this appears to be an average-case optimization. Indeed, measurements show that the number of cache blocks spilled is reduced to about 17% and 30% in the mean, depending on the stack cache size. Furthermore, we show that lazy spilling can be analyzed with little extra effort, which benefits the worst-case spilling behavior that is relevant for a real-time system.

Subject Classification

Keywords
  • Lazy Spilling
  • Stack Cache
  • Real-Time Systems
  • Program Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Abbaspour, F. Brandner, and M. Schoeberl. A time-predictable stack cache. In Proc. of the Workshop on Software Techn. for Embedded and Ubiquitous Systems. IEEE, 2013. Google Scholar
  2. Christian Ferdinand, Reinhold Heckmann, and Bärbel Franzen. Static memory and timing analysis of embedded systems code. In Proc. of Symposium on Verification and Validation of Software Systems, pages 153-163. Eindhoven Univ. of Techn., 2007. Google Scholar
  3. Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. Real-Time Systems, 17(2-3):131-181, 1999. Google Scholar
  4. Matthew R. Guthaus, Jeffrey S. Ringenberg, Dan Ernst, Todd M. Austin, Trevor Mudge, and Richard B. Brown. MiBench: A free, commercially representative embedded benchmark suite. In Proc. of the Workshop on Workload Characterization, WWC'01, 2001. Google Scholar
  5. A. Jordan, F. Brandner, and M. Schoeberl. Static analysis of worst-case stack cache behavior. In Proc. of the Conf. on Real-Time Networks and Systems, pages 55-64. ACM, 2013. Google Scholar
  6. Hsien-Hsin S. Lee, Mikhail Smelyanskiy, Gary S. Tyson, and Chris J. Newburn. Stack value file: Custom microarchitecture for the stack. In Proc. of the International Symposium on High-Performance Computer Architecture, HPCA'01, pages 5-14. IEEE, 2001. Google Scholar
  7. Soyoung Park, Hae woo Park, and Soonhoi Ha. A novel technique to use scratch-pad memory for stack management. In In Proc. of the Design, Automation Test in Europe Conference, DATE'07, pages 1-6. ACM, 2007. Google Scholar
  8. J. Reineke, I. Liu, H. D. Patel, S. Kim, and E. A. Lee. PRET DRAM controller: Bank privatization for predictability and temporal isolation. In Proc. of the Conference on Hardware/Software Codesign and System Synthesis, pages 99-108. ACM, 2011. Google Scholar
  9. Martin Schoeberl, Benedikt Huber, and Wolfgang Puffitsch. Data cache organization for accurate timing analysis. Real-Time Systems, 49(1):1-28, 2013. Google Scholar
  10. Martin Schoeberl, Pascal Schleuniger, Wolfgang Puffitsch, Florian Brandner, Christian W. Probst, Sven Karlsson, and Tommy Thorn. Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach, volume 18, pages 11-21. OASICS, 2011. Google Scholar
  11. BoundT Time and Stack Analyzer - Application Note SPARC/ERC32 V7, V8, V8E. Technical Report TR-AN-SPARC-001, Version 7, Tidorum Ltd., 2010. Google Scholar
  12. Randall T. White, Christopher A. Healy, David B. Whalley, Frank Mueller, and Marion G. Harmon. Timing analysis for data caches and set-associative caches. In Proceedings of the Real-Time Technology and Applications Symposium, RTAS'97, pages 192-203, 1997. Google Scholar
  13. Reinhard Wilhelm, Daniel Grund, Jan Reineke, Marc Schlickling, Markus Pister, and Christian Ferdinand. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. Trans. Comp.-Aided Des. Integ. Cir. Sys., 28(7):966-978, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact