Fine-Grained Shared Cache Interference Analysis Using Basic Block's Execution Time

Shared last-level caches in multi-core architectures may lead to mutual interference in memory accesses between cores, resulting in additional access latency. To ensure the accuracy of programs' worst-case execution time (WCET) analysis, the inter-core interference of shared caches must be analyzed. This involves getting the time when memory access may occur between cores (i.e., inter-core context). But due to the uncertainty of inputs, describing inter-core context becomes extremely challenging. Existing works often consider the entire execution time of program as the time when all memory accesses may occur to enhance scalability, which ignores the timing information within programs and may lead to an overestimation of interference. This paper proposes a fine-grained shared cache interference analysis method based on the execution time of basic blocks. It employs a path-based strategy to estimate the execution time of basic blocks and use it as the lifecycles of memory accesses within the blocks, which can effectively eliminate impossible interferences. Experiments show that compared to the all interference method, we can reduce WCET by 65% in the best case and by 14% on average, with only a 130% increase in average analysis time.