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

This paper presents a formal, per-access analytical proof establishing that the maximum credible interference stall for a task in a direct-mapped multicore processor with specific architectural invariants is strictly bounded by (N-1)Lmem, thereby providing a traceable method for certifying airborne software under DO-178C/CAST-32A standards.

The Gist

Imagine a busy highway with N lanes, but there is only one single toll booth (the shared memory) and one single parking spot right before it (the L2 cache). This is the world of the computer chips described in this paper.

The author, Felipe Pedroni, is trying to answer a very specific question for safety-critical systems (like the software that flies airplanes): "What is the absolute worst-case delay a specific task could face because of traffic from other tasks?"

Here is the breakdown of the paper's findings using simple analogies:

1. The Setup: A Strictly Controlled Highway

The paper doesn't look at modern, complex highways with multiple lanes, smart traffic lights, or parallel toll booths. Instead, it sets up a very strict, "pessimistic" scenario to find a hard limit:

• The Parking Spot (L2 Cache): It's a "direct-mapped" spot. This means there is only one spot for every specific address. If a new car arrives, it kicks the old car out immediately. There are no waiting areas (no MSHRs) to hold cars while they wait for the toll booth.
• The Toll Booth (Memory): There is only one lane to the main memory. Cars must go one by one.
• The Rules: The "bad guys" (other tasks) are allowed to be as mean as possible, but they must follow the rules of this specific highway.

2. The Worst-Case Scenario: The "Perfect Storm"

The paper proves that the worst possible delay happens when N-1 other cars (adversarial tasks) arrive at the toll booth at the exact same moment as your car (the target task).

Here is how the delay builds up:

1. The Kick-Out (Spatial): The other cars park in the exact same spot as your car, but with different license plates (tags). Because the spot only holds one car, your car gets kicked out of the parking lot. Now, your car has to go all the way to the main memory to get its data.
2. The Line-Up (Temporal): Because there are no waiting areas (MSHRs), the toll booth processes cars one by one. The paper assumes the toll booth operator is "pessimistic"—meaning if your car is in line with N-1 other cars, the operator makes your car wait until everyone else is served first.
3. The Result: Your car waits for N-1 other cars to pass through the toll booth. If it takes Lmem time to cross the toll booth, your total wait is (N - 1) × Lmem.

3. The Big Discovery: The "Per-Access" Limit

The most important finding is that this delay happens per access.

• If your task needs to check the memory 10 times, and every single time N-1 other cars show up at the exact same moment to kick you out and make you wait, you pay the full penalty 10 times.
• The paper proves you cannot be delayed more than this. Even if the other cars try to be tricky, they can't force you to wait longer than (N - 1) times the toll booth duration for a single request.

4. Why This Matters for Airplanes (Certification)

In the real world, certifying software for airplanes (under standards like DO-178C) requires proving that the system will never fail, even in the worst case.

• Old Way: Engineers often guessed or ran thousands of simulations to see what might happen. This is like trying to predict traffic by driving the highway every day for a year. It's messy and hard to prove you've seen the absolute worst case.
• This Paper's Way: The author provides a mathematical formula that acts as a "guaranteed ceiling."
  • If you know your hardware follows the strict rules (1 parking spot, no waiting areas, one toll lane), you can mathematically prove: "The delay will never exceed this number."
  • This allows engineers to subtract this "worst-case delay" from their total time budget and say, "We are safe."

5. The Catch (Limitations)

The paper is very honest about where this math applies. It only works if the computer chip is built exactly as described:

• No fancy caches: If the chip has a cache with multiple "ways" (like a garage with 4 spots for the same address), the math changes.
• No parallel processing: If the chip can handle multiple memory requests at once, the delay is less, but this formula doesn't apply.
• Strict Control: The tasks must be "pinned" (stuck to specific cores) and predictable.

Summary Analogy

Imagine you are the only person allowed to use a specific elevator in a building with N floors.

• The Rule: The elevator only holds one person at a time, and it takes 1 minute to go up and down.
• The Worst Case: Just as you step in, N-1 other people step in with you. The elevator operator forces you to wait until they all get off and come back.
• The Result: You wait (N-1) minutes.
• The Paper's Value: It proves that no matter how many people try to squeeze in, or how they try to time it, they cannot make you wait more than (N-1) minutes per trip, provided the elevator has no extra features (like a waiting room or a second elevator).

This gives engineers a precise, unbreakable number to use when designing safety-critical systems, ensuring that even if the "worst-case traffic jam" happens, the system will still finish its job on time.

Technical Summary

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

Problem Statement
Multicore processors introduce shared-resource contention (caches, buses, memory controllers) that complicates timing analysis for safety-critical systems. Certification standards such as DO-178C and CAST-32A require the demonstration of "maximum credible interference" for these resources. However, existing approaches often rely on empirical measurements or conservative pessimism without formally closing the adversarial search space. Furthermore, many prior analyses assume set-associative caches or probabilistic bounds, which can obscure the derivation of a strict, analytically justified worst-case execution time (WCET). This work addresses the question of whether a formal bound for worst-case shared-resource interference can be established and attained under a well-defined, constrained architectural configuration.

Methodology and System Model
The paper proposes a formal bounding analysis based on a closed system tuple $S = \langle H, W, R, C \rangle$, separating hardware invariants ($H$), workload ($W$), arbitration ($R$), and configuration ($C$). The analysis relies on the following strict architectural invariants:

• Hardware: $N$ processor cores with private L1 caches, a shared direct-mapped (1-way associative) L2 cache with no Miss Status Handling Registers (MSHRs), and a single-bank main memory.
• Latency: Fixed latency $L_{mem}$ per L2 miss (including write-back, read, and bus turnaround).
• Workload: Deterministic, pinned tasks with fixed physical memory mapping. The target task $T$ has a known critical access set $P_{crit}$.
• Arbitration: A pessimistic arbitration policy where, in the event of contention, the target task $T$ is served last after all adversarial requests are completed.
• Adversarial Model: $N-1$ adversarial tasks pinned to distinct cores, sharing the same period as $T$, with no data sharing or out-of-model interference channels (e.g., DMA, interrupts).

The methodology proceeds via three lemmas addressing spatial, temporal, and pattern-based interference dimensions, culminating in a main theorem.

Key Contributions and Derivation

1. Spatial Sufficiency (Lemma 11): In a direct-mapped cache, a single adversarial request accessing the same cache set index ($\sigma$) but with a different tag ($\tau$) is sufficient to evict the target task's line, forcing an L2 miss. Additional adversaries on the same set do not cause further evictions but contribute to serialization pressure.
2. Temporal Maximality (Lemma 13): With MSHRs disabled, the memory controller processes misses sequentially. The serialization latency for $T$ is maximized when all $N-1$ adversarial requests arrive simultaneously with $T$'s request. In this synchronous case, $T$ is served last, incurring a stall of $(N-1)L_{mem}$.
3. Pattern Sufficiency (Lemma 14): If the adversarial schedule issues exactly $N-1$ congruent-different-tag requests synchronously with every critical access of $T$, the per-access stall attains the temporal bound.

Main Result
The paper proves the Monotonic Interference Upper Bound (MIUB):
Under the stated invariants and assumptions, the total interference $I_T$ on the target task's execution time is bounded by:
$$I_T \le |P_{crit}| \cdot (N - 1) L_{mem}$$

The paper demonstrates that this bound is tight (attainable) by constructing a "Baseline" adversarial configuration ($C_{base}$) where $N-1$ copies of the task run on private physical pages with controlled placement. These copies issue requests to cache sets congruent to $T$'s critical accesses but with distinct tags, synchronized perfectly with $T$'s execution.

Significance and Scope
The paper positions this work as a methodological template for certification evidence packages (specifically for DO-178C/CAST-32A) that require traceable, analytically justified interference bounds. Its significance lies in:

• Formal Closure: It provides a formally closed adversarial search space for a specific architectural subclass, avoiding the need for empirical measurement or informal multiplicative interference functions.
• Per-Access Granularity: The bound is derived per-critical-access, allowing for precise separation of multicore interference from application WCET budgets.
• Tool Independence: The analysis does not rely on proprietary simulation tools or extensive calibration, making it suitable for pre-silicon verification of customizable ISAs (e.g., RISC-V extensions).

Limitations and Applicability
The authors explicitly state that the result is not a universal bound for modern commercial off-the-shelf (COTS) multicore processors. It applies strictly to the defined subclass: direct-mapped L2, no MSHRs, single-bank memory, and deterministic pinned tasks.

• If any invariant is relaxed (e.g., set-associative caches, enabled MSHRs, multi-bank memory), the bound must be re-derived.
• The analysis covers static contention only; dynamic interference sources (DMA, power management, coherence traffic) are out of scope.
• The pessimistic arbitration assumption ensures the bound is a sound upper limit, though it may overestimate stall on platforms with non-pessimistic policies (e.g., fixed priority favoring the target).

The work concludes that for platforms satisfying these specific invariants, the derived bound offers a precise, maintainable, and certification-compliant method for quantifying worst-case interference.