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

Sahar Abbaspourseyedi, Alexander Jordan, Florian Brandner

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

150 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of 14th International Workshop on Worst-Case Execution Time Analysis : WCET 2014
EditorsHeiko Falk
Number of pages10
PublisherOASICS
Publication date2014
Pages83-92
ISBN (Electronic)978-3-939897-69-9
Publication statusPublished - 2014
Event14th International Workshop on Worst-Case Execution Time Analysis - Madrid, Spain
Duration: 18 Jul 201418 Jul 2014
Conference number: 14
http://www.uni-ulm.de/en/in/wcet2014.html

Conference

Conference14th International Workshop on Worst-Case Execution Time Analysis
Number14
CountrySpain
CityMadrid
Period18/07/201418/07/2014
Internet address
SeriesOpen Access Series in Informatics
Volume39
ISSN2190-6807

Cite this

Abbaspourseyedi, S., Jordan, A., & Brandner, F. (2014). Lazy Spilling for a Time-Predictable Stack Cache: Implementation and Analysis. In H. Falk (Ed.), Proceedings of 14th International Workshop on Worst-Case Execution Time Analysis: WCET 2014 (pp. 83-92). OASICS. Open Access Series in Informatics, Vol.. 39 http://drops.dagstuhl.de/opus/volltexte/2014/4598/pdf/1.pdf