Maximilien Dupont de Dinechin, Matheus Schuh,
Matthieu Moy , Claire Maiza
Scaling Up the Memory Interference Analysis for Hard Real-Time Many-Core Systems (Full Version) (2019)
Scaling Up the Memory Interference Analysis for Hard Real-Time Many-Core Systems (Full Version) (2019)
TR-2019-1.pdf
Keywords: response time analysis, algorithm optimization, many-core architectures, real-time systems
Abstract: The emergence of many-core architectures has raised interest even from the embed ded hard real-time market for their performance and integrity capabilities. However, to use such processors in these safety-critical systems, the software running on it must have statically bounded execution time. Due to the presence of multiples cores, interference may appear when accessing shared resources, increasing the overall run-time and diminishing predictability. In RTNS 2016, Rihani et al. proposed an algorithm to compute the impact of interference on memory accesses on the timing of a task graph. It calculates a static, time-triggered schedule, i.e. a release date and a worst-case response time for each task. The task graph is a DAG, typically obtained by compilation of a high-level dataflow language, and the tool assumes a previously determined mapping and execution order. The algorithm is precise, but suffers from a high O( n^4) complexity, n being the number of input tasks. Since we target many-core platforms with tens or hundreds of cores, applications likely to exploit the parallelism of these platforms are too large to be handled by this algorithm in reasonable time. This paper proposes a new algorithm that solves the same problem. Instead of performing global fixed-point iterations on the task graph, we compute the static schedule incrementally, reducing the complexity to O(n^2) . Experimental results show a reduction from 535 seconds to 0.90 seconds on a benchmark with 384 tasks, i.e. 593 times faster.
