A Per-Access Upper Bound for Shared-Resource Interference in Direct-Mapped Multicore Architectures

Felipe T. Pedroni · 2026

Read A Per-Access Upper Bound for Shared-Resource Interference in Direct-Mapped Multicore Architectures by Felipe T. Pedroni (2026) 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-2605-24026.txt.

Introduction

Pedroni proves a per-access ceiling on interference in multicore chips under strict rules: direct-mapped L2 cache, no miss-status registers, single-bank memory, pinned tasks, and pessimistic arbitration. Under those rules, the stall on any critical access of a target task is bounded by memory latency times one less than the core count. A synchronized adversarial workload attains that bound. The argument is direct and analytical, needing no informal interference multiplier. It offers a way to separate multicore interference from worst-case execution budgets for airborne certification.

Catalog record

CREATORFelipe T. Pedroni
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25885
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24026

Browse the full library · About the Tower of Babel

Full text

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

A Per-Access Upper Bound for Shared-Resource Interference in Direct-Mapped Multicore Architectures Felipe T. Pedroni Abstract We present a formal bounding analysis for maximum credible interference in multicore processors under strict architectural invariants: direct-mapped L2 cache (1-way associativity), disabled Miss Status Handling Registers (MSHRs), single-bank main memory, deterministic pinned tasks with fixed physical memory mapping, and a pessimistic L2/memory arbitration policy. We prove that, under these invariants, the per-critical-access stall imposed on a target task T T is bounded above by ( N − 1 ) ​ L mem (N-1)L_{\text{mem}} , and that this bound is attained by a synchronized adversarial workload of N − 1 N-1 congruent-different-tag memory requests issued in phase with T T ’s critical accesses. The argument is per-access and direct, requiring no informal multiplicative interference function. The derivation is purely analytical and discussed in the context of DO-178C/CAST-32A certification objectives for airborne software. Limitations and conditions for applicability are explicitly stated. This work provides a traceable method for separating multicore interference from Worst-Case Execution Time (WCET) budgets under fixed architectural constraints. Keywords: Multicore interference, WCET analysis, DO-178C, CAST-32A, formal bounding, cache contention, real-time systems, RISC-V safety-critical extensions 1 Introduction Multicore processors introduce shared-resource contention channels that complicate timing analysis for safety-critical systems. Certification standards such as DO-178C with CAST-32A guidance require demonstration of “maximum credible interference” for shared resources including caches, buses, and memory controllers [ 1 ] . However, existing approaches often rely on empirical measurement or conservative pessimism without formal closure of the adversarial search space. This work addresses the following question: Given a fixed architectural configuration and arbitration policy, can we formally bound the worst-case shared-resource interference on a target task and exhibit an adversarial workload that attains the bound? We answer affirmatively under a well-defined constraint space. Our contribution is threefold: (i) A formal system model capturing hardware invariants, workload determinism, an arbitration policy, and configuration parameters ( Section 3 ); (ii) Three lemmas establishing per-dimension upper bounds on spatial, temporal, and pattern-based interference ( Section 4 ); (iii) A main theorem proving a per-access stall bound of (N-1)L_{\text{mem}} , attained by a synchronized congruent-different-tag adversarial workload ( Section 5 ). The result may support certification evidence packages requiring traceable, analytically justified interference bounds, provided the target platform is independently characterized to satisfy the stated invariants. It also aligns with pre-silicon verification workflows for customizable ISAs (e.g., RISC-V extensions) where timing predictability must be established before tape-out. 2 Related Work Interference analysis in multicore real-time systems has been extensively studied. Pellizzoni et al. [ 2 ] introduced a framework for bounding memory contention in COTS multicore platforms. Schranzhofer et al. [ 3 ] developed timing analysis models for shared buses and caches. More recent work by Kelter et al. [ 4 ] and Bhattacharjee et al. [ 5 ] addresses cache partitioning and interference-aware scheduling. However, most prior approaches either: (a) assume set-associative caches with replacement policies that complicate worst-case analysis; (b) rely on probabilistic or measurement-based bounds without formal closure; or (c) treat interference dimensions independently rather than proving joint maximality. Our work differs by establishing a direct per-access bound under explicitly stated architectural invariants and a documented arbitration assumption, providing a formally closed adversarial search space for certification purposes. The CAST-32A guidance [ 1 ] emphasizes the need for “credible” worst-case scenarios but does not prescribe methods for proving maximality. This work fills that methodological gap for a well-defined architectural subclass. 3 Formalization of the Search Space We define the system as a closed tuple S=\langle H,W,R,C\rangle , separating the arbitration policy R from the configurable adversarial parameters C : Definition 1 (Hardware Invariants H ) . The hardware platform satisfies the following invariants: • N processor cores: C_{0},C_{1},\dots,C_{N-1} • Private L1 instruction and data caches per core • Shared L2 cache: direct-mapped (1-way associative), no MSHRs • Main memory: single-bank architecture, shared across all cores • Fixed latency per L2 miss: L_{\text{mem}} (includes dirty write-back + read + bus turnaround) • Address decomposition: every physical address a admits a decomposition into a set index \sigma(a) and a tag \tau(a) . The cache-set mapping function is S(\cdot)(a):=\sigma(a) . Definition 2 (Workload W ) . Target task T with deterministic address sequence per period: \mathcal{A}_{T}=\langle a_{1},a_{2},\dots,a_{k}\rangle The critical access set \mathcal{P}_{\text{crit}}\subseteq\mathcal{A}_{T} comprises those accesses that lie on the data/control dependency chain determining T ’s WCET. All instances of T are pinned to cores, have identical period, worst-case execution time, and start synchronized at time M . Definition 3 (Arbitration Model R ) . The L2/memory arbitration policy is a function that, at each scheduling decision, selects one core’s pending request among the contending requests. We say the policy is pessimistic for T if, whenever T ’s request contends simultaneously with one or more adversarial requests, T is selected last; equivalently, T is served only after all contending adversarial requests have been completed. Assumption 4 (Pessimistic Arbitration) . The arbitration policy R is pessimistic for T . This is a worst-case modeling assumption used throughout the proofs: under any policy that is not pessimistic for T (e.g., fixed priority favoring T ’s core, round-robin starting at T , age-based with T arriving first), the stall on T is less than or equal to the bound established here. 4 therefore yields a sound upper bound and, when the implemented arbiter is not characterized, is the appropriate certification-time abstraction. Definition 5 (Configuration C ) . Parameters defining N-1 adversarial tasks: • Memory mapping: physical-to-cache-set function S(\cdot) • Start time offset relative to T • Access pattern (address sequence) Definition 6 (Admissible Configuration) . A configuration C is admissible if it satisfies all of the following: • Each of the N-1 adversarial tasks is pinned to a distinct core and shares the same period and worst-case execution time as T ; • Each adversarial core holds at most one in-flight L2 request at any instant (consistent with the no-MSHR / blocking miss-handling property of H ); • Each L2 miss incurs the fixed latency L_{\text{mem}} defined in H ; • No data sharing exists between T and the adversaries, and no out-of-model interference channels (DMA, asynchronous interrupts, power management transitions, TLB pressure, coherence traffic) are active during the analysis window. All bounds in this paper are stated over admissible configurations. Definition 7 (Interference Metric) . Total interference on T ’s execution time: I_{T}=\sum_{i=1}^{k}\Delta t(a_{i}) where \Delta t(a_{i}) is the additional stall imposed on access a_{i} due to contention on shared resources (L2 arbiter, memory bus, memory controller). Assumption 8 (Architectural Invariants) . The hardware configuration H is fixed and documented. No dynamic reconfiguration, power management, or thermal throttling occurs during the analysis window. Assumption 9 (Workload Determinism) . Task T exhibits deterministic control flow and memory access patterns for a given input. No data-dependent branching affects the critical path under analysis. Objective : Prove that, under H , W , R , and the assumptions above, I_{T}(C)\;\leq\;|\mathcal{P}_{\text{crit}}|\cdot(N-1)\,L_{\text{mem}}\quad\text{for every admissible }C, and exhibit a Baseline configuration C_{\text{base}} that attains this bound: C_{\text{base}}=\{\text{start\_sync}=M,\;S(\cdot)_{\text{adv}}=S(\cdot)_{T},\;\mathcal{A}_{\text{adv}}=\mathcal{A}_{T}\}. The bound is tight but not uniquely attained: any adversarial configuration that issues, synchronously with each a_{i}\in\mathcal{P}_{\text{crit}} , N-1 congruent-different-tag requests reaches the same value (see Remark 17 ). Remark 10 (Interpretation of \mathcal{A}_{\text{adv}}=\mathcal{A}_{T}

Read the complete text