Paper Info
Title
A synergetic approach to accurate analysis of cache-related preemption delay
Abstract
The worst-case execution time (WCET) of a task denotes the largest possible execution time for all possible inputs and thus, hardware states. For non-preemptive multitask scheduling, techniques for the static estimation of safe upper bounds have been subject to industrial practice for years. For preemptive scheduling however, the isolated analysis of tasks becomes imprecise as interferences among tasks cannot be considered with sufficient precision. For such scenarios, the cache-related preemption delay (CRPD) denotes a key metric as it reflects the effects of preemptions on the execution behavior of a single task. Until recently, proposals for CRPD analyses were often limited to direct mapped caches or comparably imprecise for k-way set-associative caches. In this paper, we propose how the current best techniques for CRPD analysis, which have only been proposed separately and for different aspects of the analysis can be brought together to construct an efficient CRPD analysis with unique properties. Moreover, along the construction, we propose several different enhancements to the methods employed. We also exploit that in a complete approach, analysis steps are synergetic and can be combined into a single analysis pass solving all formerly separate steps at once. In addition, we argue that it is often sufficient to carry out the combined analysis on basic block bounds, which further lowers the overall complexity. The result is a proposal for a fast CRPD analysis of very high accuracy.
Year
DOI
Venue
2011
10.1145/2038642.2038693
EMSOFT
Keywords
Field
DocType
single analysis,cache-related preemption delay,combined analysis,analysis step,synergetic approach,worst-case execution time,isolated analysis,accurate analysis,efficient crpd analysis,crpd analysis,execution behavior,largest possible execution time,fast crpd analysis,multitasking,upper bound,worst case execution time,task analysis,scheduling,preemptive scheduling,static analysis
Preemption,Task analysis,Scheduling (computing),Upper and lower bounds,Cache,Computer science,Static analysis,Real-time computing,Basic block,Human multitasking,Distributed computing
Conference
Citations 
PageRank 
References 
6
0.45
17
Authors
3
Name
Order
Citations
PageRank
Jan C. Kleinsorge1743.38
Heiko Falk246231.54
Peter Marwedel31904184.40