Paper Info
Title
WCET-aware static locking of instruction caches
Abstract
In the past decades, embedded system designers moved from simple, predictable system designs towards complex systems equipped with caches. This step was necessary in order to bridge the increasingly growing gap between processor and memory system performance. Static analysis techniques had to be developed to allow the estimation of the cache behavior and an upper bound of the execution time of a program. This bound is called worst-case execution time (WCET). Its knowledge is crucial to verify whether hard real-time systems satisfy their timing constraints, and the WCET is a key parameter for the design of embedded systems. In this paper, we propose a WCET-aware optimization technique for static I-cache locking which improves a program's performance and predictability. To select the memory blocks to lock into the cache and avoid time consuming repetitive WCET analyses, we developed a new algorithm employing integer-linear programming (ILP). The ILP models the worst-case execution path (WCEP) of a program and takes the influence of locked cache contents into account. By modeling the effect of locked memory blocks on the runtime of basic blocks, the overall WCET of a program can be minimized. We show that our optimization is able to reduce the estimated WCET (abbr. WCETest) of real-life benchmarks by up to 40.8%. At the same time, our proposed approach is able to outperform a regular cache by up to 23.8% in terms of WCETest.
Year
DOI
Venue
2012
10.1145/2259016.2259023
CGO
Keywords
Field
DocType
execution time,overall wcet,regular cache,locked cache content,estimated wcet,worst-case execution time,complex system,cache behavior,time consuming repetitive wcet,embedded system,instruction cache,static analysis,upper bound,satisfiability,code generation,system design,worst case execution time,subgraph isomorphism
Complex system,Predictability,Upper and lower bounds,Cache,Computer science,Lock (computer science),Parallel computing,Static analysis,Real-time computing,Code generation,Subgraph isomorphism problem
Conference
Citations 
PageRank 
References 
21
0.69
12
Authors
4
Name
Order
Citations
PageRank
Sascha Plazar1954.71
Jan C. Kleinsorge2743.38
Peter Marwedel31904184.40
Heiko Falk446231.54