Publications Memory & Shared-Resource Management
Impact of DM-LRU on WCET: a Static Analysis Approach
31th Euromicro Conference on Real-Time Systems (ECRTS 2019), July 2019, Stuttgart, Germany
Abstract
Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache.
Cite this paper
@inproceedings{DMLRU_ECRTS19,
title = {{Impact of DM-LRU on WCET: a Static Analysis Approach}},
author = {Mancuso, Renato and Yun, Heechul and Puaut, Isabelle},
booktitle = {31th Euromicro Conference on Real-Time Systems (ECRTS 2019)},
year = 2019,
month = jul,
volume = {107},
pages = {17:1--17:25},
publisher = {Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik},
address = {Stuttgart, Germany},
doi = {10.4230/LIPIcs.ECRTS.2019.17},
url = {https://doi.org/10.4230/LIPIcs.ECRTS.2019.17}
}
TY - CONF AU - Mancuso, Renato AU - Yun, Heechul AU - Puaut, Isabelle TI - Impact of DM-LRU on WCET: a Static Analysis Approach T2 - 31th Euromicro Conference on Real-Time Systems (ECRTS 2019) PY - 2019 DA - 2019/07// VL - 107 PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Stuttgart, Germany SP - 17:1 EP - 17:25 DO - 10.4230/LIPIcs.ECRTS.2019.17 UR - https://doi.org/10.4230/LIPIcs.ECRTS.2019.17 AB - Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache. ER -
%0 Conference Paper %A Mancuso, Renato %A Yun, Heechul %A Puaut, Isabelle %T Impact of DM-LRU on WCET: a Static Analysis Approach %B 31th Euromicro Conference on Real-Time Systems (ECRTS 2019) %D 2019 %V 107 %P 17:1-17:25 %I Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik %C Stuttgart, Germany %R 10.4230/LIPIcs.ECRTS.2019.17 %U https://doi.org/10.4230/LIPIcs.ECRTS.2019.17 %X Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache.
[
{
"id": "DMLRU_ECRTS19",
"type": "paper-conference",
"title": "Impact of DM-LRU on WCET: a Static Analysis Approach",
"author": [
{
"family": "Mancuso",
"given": "Renato"
},
{
"family": "Yun",
"given": "Heechul"
},
{
"family": "Puaut",
"given": "Isabelle"
}
],
"container-title": "31th Euromicro Conference on Real-Time Systems (ECRTS 2019)",
"issued": {
"date-parts": [
[
2019,
7
]
]
},
"volume": "107",
"page": "17:1-17:25",
"publisher": "Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik",
"publisher-place": "Stuttgart, Germany",
"DOI": "10.4230/LIPIcs.ECRTS.2019.17",
"abstract": "Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET). In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache."
}
]
R. Mancuso, H. Yun, and I. Puaut, “Impact of DM-LRU on WCET: a Static Analysis Approach,” in 31th Euromicro Conference on Real-Time Systems (ECRTS 2019), vol. 107, pp. 17:1–17:25, Jul. 2019, doi: 10.4230/LIPIcs.ECRTS.2019.17.
Mancuso, R., Yun, H., & Puaut, I. (2019). Impact of DM-LRU on WCET: a Static Analysis Approach. In 31th Euromicro Conference on Real-Time Systems (ECRTS 2019) (pp. 17:1–17:25). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ECRTS.2019.17