Back to Search
Start Over
Reducing the WCET and analysis time of systems with simple lockable instruction caches
- Source :
- PLoS ONE, Addi. Archivo Digital para la Docencia y la Investigación, instname, PLoS ONE, Vol 15, Iss 3, p e0229980 (2020), Zaguán: Repositorio Digital de la Universidad de Zaragoza, Universidad de Zaragoza, Zaguán. Repositorio Digital de la Universidad de Zaragoza
- Publication Year :
- 2020
- Publisher :
- Plos One, 2020.
-
Abstract
- One of the key challenges in real-time systems is the analysis of the memory hierarchy. Many Worst-Case Execution Time (WCET) analysis methods supporting an instruction cache are based on iterative or convergence algorithms, which are rather slow. Our goal in this paper is to reduce the WCET analysis time on systems with a simple lockable instruction cache, focusing on the Lock-MS method. First, we propose an algorithm to obtain a structure-based representation of the Control Flow Graph (CFG). It organizes the whole WCET problem as nested subproblems, which takes advantage of common branch-and-bound algorithms of Integer Linear Programming (ILP) solvers. Second, we add support for multiple locking points per task, each one with specific cache contents, instead of a given locked content for the whole task execution. Locking points are set heuristically before outer loops. Such simple heuristics adds no complexity, and reduces the WCET by taking profit of the temporal reuse found in loops. Since loops can be processed as isolated regions, the optimal contents to lock into cache for each region can be obtained, and the WCET analysis time is further reduced. With these two improvements, our WCET analysis is around 10 times faster than other approaches. Also, our results show that the WCET is reduced, and the hit ratio achieved for the lockable instruction cache is similar to that of a real execution with an LRU instruction cache. Finally, we analyze the WCET sensitivity to compiler optimization, showing for each benchmark the right choices and pointing out that O0 is always the worst option.
- Subjects :
- Time Factors
Computer science
Optimizing compiler
02 engineering and technology
Parallel computing
01 natural sciences
Computer Architecture
Hit ratio
Cognition
Learning and Memory
Mathematical and Statistical Techniques
0202 electrical engineering, electronic engineering, information engineering
Heuristics
Integer programming
010302 applied physics
Multidisciplinary
Memory hierarchy
Applied Mathematics
Simulation and Modeling
Software Engineering
Programming, Linear
Robotics
020202 computer hardware & architecture
Physical Sciences
Medicine
Control flow graph
Engineering and Technology
Cache
Algorithms
Research Article
Optimization
Computer and Information Sciences
Science
Aerospace Engineering
Research and Analysis Methods
Memory
0103 physical sciences
Linear Programming
Mechanical Engineering
Biology and Life Sciences
Lock (computer science)
Source Code
Cognitive Science
Aviation
Mathematical Functions
Mathematics
Neuroscience
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- PLoS ONE, Addi. Archivo Digital para la Docencia y la Investigación, instname, PLoS ONE, Vol 15, Iss 3, p e0229980 (2020), Zaguán: Repositorio Digital de la Universidad de Zaragoza, Universidad de Zaragoza, Zaguán. Repositorio Digital de la Universidad de Zaragoza
- Accession number :
- edsair.doi.dedup.....c4e22fae8b59d2126824170562f365b9