Tight Inter-Core Cache Contention Analysis for WCET Estimation on Multicore Systems

Shuai Zhao 2 , Jieyu Jiang 2 , Shenlin Cai 2 , Yaowei Liang 2 , Chen Jie 2 , Yinjie Fang 3 , Wei Zhang 4 , Guoquan Zhang 6 , Yaoyao Gu 6 , Xiang Xiao 6 , Wei Qin 6 , Xiangzhen Ouyang 6 , Wanli Chang 3 · 2025

Read Tight Inter-Core Cache Contention Analysis for WCET Estimation on Multicore Systems by Shuai Zhao 2 , Jieyu Jiang 2 , Shenlin Cai 2 , Yaowei Liang 2 , Chen Jie 2 , Yinjie Fang 3 , Wei Zhang 4 , Guoquan Zhang 6 , Yaoyao Gu 6 , Xiang Xiao 6 , Wei Qin 6 , Xiangzhen Ouyang 6 , Wanli Chang 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13863.txt.

Introduction

Shuai Zhao and co-authors sharpen in 2025 the math that bounds how long a program can run on a multicore chip. Worst-case timing estimates bloat when cores fight over the shared cache, and older analyses overcount the misses a rival core's access can cause. Their method first finds which memory references a remote access could hurt, given the task's region order.

A fine-grained count then prices the misses by how often local and remote blocks are touched, and dynamic programming rolls the total interference up. On benchmarks the new count cut cache interference estimates by about half and worst-case times by about nine percent.

Catalog record

CREATORShuai Zhao 2 , Jieyu Jiang 2 , Shenlin Cai 2 , Yaowei Liang 2 , Chen Jie 2 , Yinjie Fang 3 , Wei Zhang 4 , Guoquan Zhang 6 , Yaoyao Gu 6 , Xiang Xiao 6 , Wei Qin 6 , Xiangzhen Ouyang 6 , Wanli Chang 3
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13863

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight Inter-Core Cache Contention Analysis for WCET Estimation on Multicore Systems Shuai Zhao 2 , Jieyu Jiang 2 , Shenlin Cai 2 , Yaowei Liang 2 , Chen Jie 2 , Yinjie Fang 3 , Wei Zhang 4 , Guoquan Zhang 6 , Yaoyao Gu 6 , Xiang Xiao 6 , Wei Qin 6 , Xiangzhen Ouyang 6 , Wanli Chang 3 Abstract WCET (Worst-Case Execution Time) estimation on multicore architecture is particularly challenging mainly due to the complex accesses over cache shared by multiple cores. Existing analysis identifies possible contentions between parallel tasks by leveraging the partial order of the tasks or their program regions. Unfortunately, they overestimate the number of cache misses caused by a remote block access without considering the actual cache state and the number of accesses. This paper reports a new analysis for inter-core cache contention. Based on the order of program regions in a task, we first identify memory references that could be affected if a remote access occurs in a region. Afterwards, a fine-grained contention analysis is constructed that computes the number of cache misses based on the access quantity of local and remote blocks. We demonstrate that the overall inter-core cache interference of a task can be obtained via dynamic programming. Experiments show that compared to existing methods, the proposed analysis reduces inter-core cache interference and WCET estimations by 52.31% and 8.94% on average, without significantly increasing computation overhead. I Introduction The worst-case execution time (WCET) of tasks is essential for ensuring the timing predictability of real-time systems, i.e. , being able to finish before deadlines [ 1 , 2 ] . In WCET estimations, the cache contention is a major source of latency, where cache misses can impose a significant delay on the execution of a task [ 3 , 4 , 5 ] . For uniprocessor systems, the cache analysis focuses on the intra-core contention caused by memory accesses of a task itself, providing the maximum cache miss number among the execution paths of the task [ 6 , 7 , 8 ] . Matured techniques are available for analysing the intra-core cache contention [ 6 , 9 ] , e.g. , the Must/May [ 10 ] and Persistence analysis [ 11 , 12 , 13 ] that compute the age of memory blocks across different paths and loop structures. With the growing demand for performance and complex functionalities, multicore architectures are widely adopted in real-time systems, which often contain a shared cache that is accessed from multiple cores in parallel [ 14 , 15 ] . In such systems, the inter-core cache contention can occur when memory blocks required by a task are evicted due to the block accesses of the remote tasks [ 16 , 17 ] . Such contention can lead to substantial misses on the shared cache, resulting in significant latency in task execution. Therefore, for multicore real-time systems, the inter-core cache contention analysis is necessary to provide correct WCET estimations of tasks [ 18 ] . Ideally, a precise bound on the inter-core cache interference of a task can be obtained by analysing all potential contentions imposed from remote tasks at each program point, with the cache state taken into account ( i.e. , the blocks in the shared cache and their ages). However, due to the non-deterministic arrivals of parallel tasks [ 19 ] , this can cause severe scalability issues that fundamentally undermine the applicability of the analysis. In addition, the complexity of the cache and the intricacies of the programs ( e.g. , loop structures) further exacerbate the problem [ 18 ] , making it even challenging to obtain a precise analytical bound efficiently. Therefore, rather than formulating an optimisation problem across all program points [ 20 ] , existing approaches explore the polynomial-time solutions that identify contentions which can occur in the worst case [ 3 , 4 ] . Specifically, the analysis in [ 3 ] leverages the lifetimes of tasks to determine the ones that cause a contention, thereby reducing the number of interfering tasks. A more recent method in [ 4 ] exploits the partial order between program regions to identify contentions that are mutually exclusive in time, and applies a dynamic program to compute the number of misses based on the feasible contentions. However, while reducing the computation complexity, these methods often rely on a pessimistic assumption that a remote access can impose a contention on all accesses of every block, neglecting the actual cache state of blocks ( i.e. , age) or the access behaviours ( i.e. , number of accesses) of the parallel tasks (see Sec. II-B for details). Consequently, they can overestimate the number of cache misses caused by a remote access, which leads to overly conservative analytical results. Main Contribution: This paper presents a novel inter-core cache contention analysis. Similar to [ 4 ] , the constructed analysis is performed at the program regions of tasks. However, for each region, we determine the number of cache misses by examining every possible age and access number of a memory block, providing tighter analytical bounds that address the limitation in existing analysis. To achieve this, the following contributions are proposed. • A sequence of contention regions (CRs) where each contains the memory references can be interfered if a remote access occurs in the corresponding program region. • A fine-grained contention analysis that quantifies the cache miss number of memory references in a CR with the actual cache accessing behaviours taken into account. • A complete inter-core cache analysis over a sequence of CRs via dynamic programming that leverages the partial order between the regions of parallel tasks. We integrate the proposed analysis into an existing WCET analysis tool named LLVM-TA [ 21 ] , forming a complete solution for analysing WCETs on multicore real-time systems 1 1 1 The implementation of the proposed inter-core cache analysis is available at https://github.com/RTS-SYSU/Timing-Analysis-Multicores . . To the best of our knowledge, this is the first inter-core cache analysis that considers both the actual cache state and accessing behaviours of parallel tasks. Experiments show that compared to the existing analysis, the proposed analysis reduces inter-core cache interference and WCET estimations by 52.31% and 8.94% on average under tasks in TacleBench without significantly increasing the computation cost. Organisation: Sec. II presents the preliminaries of the proposed analysis. Sec. III constructs the CRs based on the program regions of a task. Sec. IV presents the contention analysis on a CR. Sec. V forms the complete inter-core cache analysis of a task. Finally, Sec. VI describes the experimental results and Sec. VII draws the conclusion. II Preliminaries TABLE I: Notations Introduced in Sec. II . Notation Description \kappa The associativity of the shared cache. \tau / \tau^{\prime} The task under analysis / the interfering task. b_{i} A memory block b_{i} . \omega_{i} The block address of b_{i} . U_{x} A unordered region with an index x . \delta_{x} The number of executions of U_{x} . \lambda A path that contains a sequence of out-most URs. \Omega_{x} The set of unique block addresses in U_{x} . anc(U_{x}) The complete set of the outer URs that contain U_{x} . II-A System Model Hardware Platform.

Read the complete text