TY - GEN
T1 - Top-down and bottom-up multi-level cache analysis for WCET estimation
AU - Zhang, Zhenkai
AU - Koutsoukos, Xenofon
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/5/14
Y1 - 2015/5/14
N2 - In many multi-core architectures, inclusive shared caches are used to reduce cache coherence complexity. However, the enforcement of the inclusion property can cause invalidation of memory blocks at higher cache levels. In order to ensure safety, analysis of cache hierarchies with inclusive caches for worst-case execution time (WCET) estimation is typically based on conservative decisions. Thus, the estimation may not be tight. In order to tighten the estimation, this paper proposes an approach that can more precisely analyze the behavior of a cache hierarchy maintaining the inclusion property. We illustrate the approach in the context of multi-level instruction caches. The approach first analyzes all the inclusive caches in the hierarchy in a bottom-up direction, and then analyzes the remaining non-inclusive caches in a top-down direction. In order to capture the inclusion victims and their effects, we also propose a concept of aging barrier and integrate it with the traditional must and persistence analyses to safely slow down their aging process so as to derive more precise analyses. We evaluate the proposed approach on a set of benchmarks and the evaluation reveals that the estimations are tightened.
AB - In many multi-core architectures, inclusive shared caches are used to reduce cache coherence complexity. However, the enforcement of the inclusion property can cause invalidation of memory blocks at higher cache levels. In order to ensure safety, analysis of cache hierarchies with inclusive caches for worst-case execution time (WCET) estimation is typically based on conservative decisions. Thus, the estimation may not be tight. In order to tighten the estimation, this paper proposes an approach that can more precisely analyze the behavior of a cache hierarchy maintaining the inclusion property. We illustrate the approach in the context of multi-level instruction caches. The approach first analyzes all the inclusive caches in the hierarchy in a bottom-up direction, and then analyzes the remaining non-inclusive caches in a top-down direction. In order to capture the inclusion victims and their effects, we also propose a concept of aging barrier and integrate it with the traditional must and persistence analyses to safely slow down their aging process so as to derive more precise analyses. We evaluate the proposed approach on a set of benchmarks and the evaluation reveals that the estimations are tightened.
UR - http://www.scopus.com/inward/record.url?scp=84944678642&partnerID=8YFLogxK
U2 - 10.1109/RTAS.2015.7108413
DO - 10.1109/RTAS.2015.7108413
M3 - Conference contribution
AN - SCOPUS:84944678642
T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
SP - 24
EP - 35
BT - Proceedings - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 21st IEEE Real Time and Embedded Technology and Applications Symposium, RTAS 2015
Y2 - 13 April 2015 through 16 April 2015
ER -