⚡ OS 07: Multicore Processors, Cache Coherence & Amdahl's Law

Targeted for: Juspay Elimination Round, Hackathon Part B System Discussion & High-Performance Computing
Key Focus: Concurrency vs True Parallelism, CPU Cache Hierarchies, False Sharing, MESI Protocol state transitions, Memory Barriers, and Amdahl's Law derivations.

🔀 1. Concurrency vs True Parallelism

• Concurrency: Managing multiple computational tasks at overlapping intervals. Progress is interleaved via rapid time-slicing on a single CPU core.
• True Parallelism: Executing multiple computational tasks at the exact same physical nanosecond across distinct physical CPU cores.

💾 2. CPU Cache Hierarchy & False Sharing

The 64-Byte Cache Line

CPUs do not load individual bytes from RAM; they load Cache Lines (fixed 64 bytes of contiguous memory).

💥 The False Sharing Performance Hazard

False Sharing occurs when two independent threads running on different CPU cores modify independent variables that happen to share the same 64-byte cache line.

1. Core 0 writes to a $\implies$ Invalidates the entire 64-byte cache line in Core 1's L1 cache.
2. Core 1 writes to b $\implies$ Invalidates the entire 64-byte cache line in Core 0's L1 cache.
3. The cache line ping-pongs continuously across the inter-core interconnect bus at DRAM speed, crippling multi-threaded throughput by up to $50\times$ without any logical race condition!

How to Fix False Sharing (C++ Alignment / Padding):

🔄 3. Cache Coherence: The MESI Protocol

In a multicore architecture, each core has a private L1/L2 cache. If Core 0 updates variable x = 5, Core 1's local cache may still hold x = 0. The hardware MESI Protocol maintains cache coherence across the system bus.

The 4 MESI Cache Line States:

Direct Juspay Relevance:

When Thread A in Hackathon Part B sets locked[node] = uid, its core issues a Bus Invalidate (RFO - Request For Ownership) signal, forcing all other cores to transition their cache line for that node from Shared to Invalid. Subsequent reads on other cores incur an L3 / RAM fetch latency.

📐 4. Amdahl's Law: Limits of Multicore Scaling

Amdahl's Law computes the theoretical maximum speedup of a program when utilizing $s$ parallel processing cores:

$$S_{\text{latency}}(s) = \frac{1}{(1 - p) + \frac{p}{s}}$$

Where:

• $p$ = Fraction of the algorithm that is strictly parallelizable ($0 \le p \le 1$).
• $(1 - p)$ = Fraction of the algorithm that is strictly sequential (locks, single-threaded bottlenecks).
• $s$ = Number of CPU processing cores.

Asymptotic Limit ($s \to \infty$):

As the number of CPU cores approaches infinity: $$\lim_{s \to \infty} S_{\text{latency}}(s) = \mathbf{\frac{1}{1 - p}}$$

🧮 Worked Numerical Example:

Suppose a payment processing engine has 75% of its code parallelizable ($p = 0.75$), while 25% is serial lock acquisition ($(1 - p) = 0.25$).

1. Calculate Speedup on a 4-Core CPU ($s = 4$): $$S = \frac{1}{0.25 + \frac{0.75}{4}} = \frac{1}{0.25 + 0.1875} = \frac{1}{0.4375} \approx \mathbf{2.286\times}$$
2. Calculate Speedup on a 64-Core Server ($s = 64$): $$S = \frac{1}{0.25 + \frac{0.75}{64}} = \frac{1}{0.25 + 0.0117} = \frac{1}{0.2617} \approx \mathbf{3.82\times}$$
3. Calculate Maximum Possible Speedup with Infinite Cores ($s = \infty$): $$S_{\max} = \frac{1}{0.25} = \mathbf{4.00\times}$$ (Even with 10,000 cores, the maximum speedup can NEVER exceed 4x because of the 25% serial bottleneck!)

💬 5. Verbatim Interview Scripts (Say This Out Loud)

Q: "What is False Sharing and how do you diagnose and prevent it?"

Verbatim Answer:
"False Sharing is a hardware performance degradation that occurs in multicore systems when two independent threads running on different cores modify unrelated variables that reside within the same 64-byte cache line.

When Core 0 writes to variable $A$, the MESI cache coherence protocol marks the entire 64-byte cache line as Invalid in Core 1's cache. When Core 1 writes to adjacent variable $B$, it forces Core 0's cache line to invalidate. This triggers continuous, costly cache-line bouncing over the memory interconnect.

We diagnose false sharing using Linux profiling tools like perf c2c (cache-to-cache). We prevent it by padding shared structures or using C++17 alignas(hardware_destructive_interference_size) / alignas(64) to ensure independent variables occupy distinct cache lines."

Q: "Explain Amdahl's Law and its implications for adding more CPU cores."

Verbatim Answer:
"Amdahl's Law states that the overall speedup of a system gained from parallel hardware is strictly bounded by the sequential, non-parallelizable fraction of the task. Mathematically, $S = \frac{1}{(1-p) + p/s}$.

As cores approach infinity, speedup asymptotically caps at $\frac{1}{1-p}$. For example, if just 5% of a transaction pipeline requires sequential lock holding, the maximum possible acceleration across the entire system is strictly capped at $20\times$, regardless of whether we allocate 64 cores or 10,000 cores. This is why fine-grained, lock-free concurrency design is mandatory in high-throughput engines like Juspay."