A Software Managed Stack Cache for Real-Time Systems

Alexander Jordan, Sahar Abbaspourseyedi, Martin Schoeberl

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

Abstract

In a real-time system, the use of a scratchpad memory can mitigate the difficulties related to analyzing data caches, whose behavior is inherently hard to predict. We propose to use a scratchpad memory for stack allocated data. While statically allocating stack frames for individual functions to scratchpad memory regions aids predictability, it is limited to non-recursive programs and static allocation has to take different calling contexts into account. Using a stack cache that dynamically spills data to and fills data from external memory avoids these problems, while its simple design allows for efficiently deriving worst-case bounds through static analysis.

In this paper we present the design and implementation of software managed caching of stack allocated data in a scratchpad memory. We demonstrate a compiler-aided implementation of a stack cache using the LLVM compiler framework and report on its efficiency. Our evaluation encompasses stack management overhead and impact on worst-case execution time analysis. The state-of-the-art worst-case execution time analysis tool aiT is able to correctly classify all stack cache accesses as accesses to the scratchpad memory.
Original languageEnglish
Title of host publicationProceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16)
PublisherAssociation for Computing Machinery
Publication date2016
Pages319-326
ISBN (Print)978-1-4503-4787-7
DOIs
Publication statusPublished - 2016
Event24th International Conference on Real-Time Networks and Systems - Brest, France
Duration: 19 Oct 201621 Oct 2016
Conference number: 24
http://rtns16.univ-brest.fr/#page=home

Conference

Conference24th International Conference on Real-Time Networks and Systems
Number24
CountryFrance
CityBrest
Period19/10/201621/10/2016
Internet address

Keywords

  • Real-time systems
  • Stack caching
  • WCET analysis
  • Scratch-pad memory

Cite this

Jordan, A., Abbaspourseyedi, S., & Schoeberl, M. (2016). A Software Managed Stack Cache for Real-Time Systems. In Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16) (pp. 319-326). Association for Computing Machinery. https://doi.org/10.1145/2997465.2997488
Jordan, Alexander ; Abbaspourseyedi, Sahar ; Schoeberl, Martin. / A Software Managed Stack Cache for Real-Time Systems. Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16). Association for Computing Machinery, 2016. pp. 319-326
@inproceedings{001332e24d7749a3911f61724a2e3b5d,
title = "A Software Managed Stack Cache for Real-Time Systems",
abstract = "In a real-time system, the use of a scratchpad memory can mitigate the difficulties related to analyzing data caches, whose behavior is inherently hard to predict. We propose to use a scratchpad memory for stack allocated data. While statically allocating stack frames for individual functions to scratchpad memory regions aids predictability, it is limited to non-recursive programs and static allocation has to take different calling contexts into account. Using a stack cache that dynamically spills data to and fills data from external memory avoids these problems, while its simple design allows for efficiently deriving worst-case bounds through static analysis.In this paper we present the design and implementation of software managed caching of stack allocated data in a scratchpad memory. We demonstrate a compiler-aided implementation of a stack cache using the LLVM compiler framework and report on its efficiency. Our evaluation encompasses stack management overhead and impact on worst-case execution time analysis. The state-of-the-art worst-case execution time analysis tool aiT is able to correctly classify all stack cache accesses as accesses to the scratchpad memory.",
keywords = "Real-time systems, Stack caching, WCET analysis, Scratch-pad memory",
author = "Alexander Jordan and Sahar Abbaspourseyedi and Martin Schoeberl",
year = "2016",
doi = "10.1145/2997465.2997488",
language = "English",
isbn = "978-1-4503-4787-7",
pages = "319--326",
booktitle = "Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16)",
publisher = "Association for Computing Machinery",
address = "United States",

}

Jordan, A, Abbaspourseyedi, S & Schoeberl, M 2016, A Software Managed Stack Cache for Real-Time Systems. in Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16). Association for Computing Machinery, pp. 319-326, 24th International Conference on Real-Time Networks and Systems, Brest, France, 19/10/2016. https://doi.org/10.1145/2997465.2997488

A Software Managed Stack Cache for Real-Time Systems. / Jordan, Alexander; Abbaspourseyedi, Sahar; Schoeberl, Martin.

Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16). Association for Computing Machinery, 2016. p. 319-326.

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

TY - GEN

T1 - A Software Managed Stack Cache for Real-Time Systems

AU - Jordan, Alexander

AU - Abbaspourseyedi, Sahar

AU - Schoeberl, Martin

PY - 2016

Y1 - 2016

N2 - In a real-time system, the use of a scratchpad memory can mitigate the difficulties related to analyzing data caches, whose behavior is inherently hard to predict. We propose to use a scratchpad memory for stack allocated data. While statically allocating stack frames for individual functions to scratchpad memory regions aids predictability, it is limited to non-recursive programs and static allocation has to take different calling contexts into account. Using a stack cache that dynamically spills data to and fills data from external memory avoids these problems, while its simple design allows for efficiently deriving worst-case bounds through static analysis.In this paper we present the design and implementation of software managed caching of stack allocated data in a scratchpad memory. We demonstrate a compiler-aided implementation of a stack cache using the LLVM compiler framework and report on its efficiency. Our evaluation encompasses stack management overhead and impact on worst-case execution time analysis. The state-of-the-art worst-case execution time analysis tool aiT is able to correctly classify all stack cache accesses as accesses to the scratchpad memory.

AB - In a real-time system, the use of a scratchpad memory can mitigate the difficulties related to analyzing data caches, whose behavior is inherently hard to predict. We propose to use a scratchpad memory for stack allocated data. While statically allocating stack frames for individual functions to scratchpad memory regions aids predictability, it is limited to non-recursive programs and static allocation has to take different calling contexts into account. Using a stack cache that dynamically spills data to and fills data from external memory avoids these problems, while its simple design allows for efficiently deriving worst-case bounds through static analysis.In this paper we present the design and implementation of software managed caching of stack allocated data in a scratchpad memory. We demonstrate a compiler-aided implementation of a stack cache using the LLVM compiler framework and report on its efficiency. Our evaluation encompasses stack management overhead and impact on worst-case execution time analysis. The state-of-the-art worst-case execution time analysis tool aiT is able to correctly classify all stack cache accesses as accesses to the scratchpad memory.

KW - Real-time systems

KW - Stack caching

KW - WCET analysis

KW - Scratch-pad memory

U2 - 10.1145/2997465.2997488

DO - 10.1145/2997465.2997488

M3 - Article in proceedings

SN - 978-1-4503-4787-7

SP - 319

EP - 326

BT - Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16)

PB - Association for Computing Machinery

ER -

Jordan A, Abbaspourseyedi S, Schoeberl M. A Software Managed Stack Cache for Real-Time Systems. In Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS'16). Association for Computing Machinery. 2016. p. 319-326 https://doi.org/10.1145/2997465.2997488