Skip to Main content Skip to Navigation
Journal articles

Cache-conscious Off-Line Real-Time Scheduling for Multi-Core Platforms: Algorithms and Implementation

Viet Anh Nguyen 1 Damien Hardy 1 Isabelle Puaut 1
1 PACAP - Pushing Architecture and Compilation for Application Performance
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : Most schedulability analysis techniques for multi-core architectures assume a single Worst-Case Execution Time (WCET) per task, which is valid in all execution conditions. This assumption is too pessimistic for parallel applications running on multi-core architectures with local instruction or data caches, for which the WCET of a task depends on the cache contents at the beginning of its execution, itself depending on the tasks that were executed immediately before the task under study. In this paper, we propose two scheduling techniques for multi-core architectures equipped with local instruction and data caches. The two techniques schedule a parallel application modeled as a task graph, and generate a static partitioned non-preemptive schedule, that takes benefit of cache reuse between pairs of consecutive tasks. We propose an exact method, using an Integer Linear Programming (ILP) formulation, as well as a heuristic method based on list scheduling. The efficiency of the techniques is demonstrated through an implementation of these cache-conscious schedules on a real multi-core hardware: a 16-core cluster of the Kalray MPPA-256, Andey generation. We point out implementation issues that arise when implementing the schedules on this particular platform. In addition, we propose strategies to adapt the schedules to the identified implementation factors. An experimental evaluation reveals that our proposed scheduling methods significantly reduce the length of schedules as compared to cache-agnostic scheduling methods. Furthermore, our experiments show that among the identified implementation factors, shared bus contention has the most impact.
Complete list of metadata

Cited literature [54 references]  Display  Hide  Download
Contributor : Isabelle Puaut <>
Submitted on : Thursday, February 21, 2019 - 12:08:29 PM
Last modification on : Tuesday, November 17, 2020 - 12:38:04 PM
Long-term archiving on: : Wednesday, May 22, 2019 - 7:57:15 PM


Files produced by the author(s)



Viet Anh Nguyen, Damien Hardy, Isabelle Puaut. Cache-conscious Off-Line Real-Time Scheduling for Multi-Core Platforms: Algorithms and Implementation. Real-Time Systems, Springer Verlag, In press, pp.1-37. ⟨10.4230/LIPIcs.ECRTS.2017.14⟩. ⟨hal-02044110⟩



Record views


Files downloads