Concurrency vs Parallelism

Many developers use "concurrency" and "parallelism" interchangeably, but they refer to entirely different levels of software and hardware architecture. Rob Pike, co-creator of Go, famously stated: "Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once."

1. Learning Objectives

• Contrast the logical design of concurrent applications with the physical execution of parallel applications.
• Understand CPU Cache hierarchies (L1, L2, L3) and how they impact thread synchronization.
• Define and prevent False Sharing on multi-core systems.
• Explain cache coherence protocols (such as MESI) at a high level.
• Analyze performance improvements using Amdahl's Law and identify hardware bottlenecks.

2. Problem & Naive Solution

Suppose you are building a scientific simulation application that calculates prime numbers within a massive range (e.g., finding all primes up to 50,000,000). This task is purely CPU-bound and requires trillions of mathematical instructions.

The Naive Solution (Multithreading on a Single Core)

A developer attempts to speed up this task by simply spawning multiple threads on a single execution core:

3. Issues with the Naive Approach

• Lack of Real Speedup on Single-Core Hardware: If the target environment only has a single core, running two threads will not make the code run faster. Instead, it runs *slower* than a single sequential loop because the CPU spends extra clock cycles saving registers, swapping stacks, and scheduling threads (context switching overhead).
• Confusing Logical Concurrency with Physical Parallelism: Simply creating Thread objects does not guarantee they execute at the same time. If the underlying OS scheduler cannot schedule them on separate physical cores, parallelism is not achieved.

4. Real-world Analogy

5. Theory: Cache Hierarchies, MESI & False Sharing

To design efficient parallel systems, we must understand how CPU cache designs affect multi-threaded execution:

A. CPU Cache Hierarchies

Accessing RAM takes about 100-200 CPU cycles. To avoid this latency, CPUs feature hierarchy caches:

• L1 Cache: Extremely fast (1-2 cycles), private to each core, usually 32-64KB.
• L2 Cache: Fast (3-10 cycles), private to each core, usually 256-512KB.
• L3 Cache: Shared across all cores on the CPU die (10-30 cycles), usually 8-32MB.

B. Cache Coherency (MESI Protocol)

When Core 1 modifies a variable X stored in its private L1 cache, Core 2 (which also cached X) must be informed to prevent it from reading outdated values. CPUs manage this using the MESI (Modified, Exclusive, Shared, Invalid) protocol:

• M (Modified): The cache line is valid but dirty (only present in the current cache and differs from main RAM).
• E (Exclusive): The cache line is present only in the current cache and matches main RAM.
• S (Shared): The cache line is present in multiple caches and matches main RAM.
• I (Invalid): The cache line contains invalid data. Any read requires fetching the line again.

C. False Sharing

CPUs load memory in chunks called cache lines (typically 64 bytes). If two threads running on different cores modify unrelated variables that happen to sit on the *same cache line*, the MESI protocol forces the cache line to bounce back and forth between cores. Each write invalidates the other core's cache, severely degrading performance. This is called False Sharing.

6. Timeline Diagrams

This Gantt chart shows the structural difference between concurrency time-slicing on Core 1 and true parallel execution on Cores 1 & 2.

7. Syntax Explanation

To harness multi-core parallel processing, we use standard concurrency structures:

• Java: Uses Parallel Streams or the ForkJoinPool to split large arrays and execute tasks across all available CPU cores.
• Python: Because of the Global Interpreter Lock (GIL), running multiple threads does not achieve CPU parallelism. You must use the multiprocessing module to spin up separate OS processes, each with its own Python interpreter.
• C++: Uses std::async with the std::launch::async execution policy, instructing the runtime to allocate tasks to background threads on separate CPU cores.

8. Step-by-Step Implementation

1. Identify CPU Core Counts: Dynamically query the host machine's physical core count.
2. Partition the Workload: Split the CPU-bound mathematical task into independent segments.
3. Launch Parallel Tasks: Spin up execution threads/processes to handle each segment in parallel.
4. Join and Consolidate: Block the caller thread until all segments report back, then aggregate the results.

9. Complete Code (Prime Number Search Comparison)

This program calculates prime numbers, comparing sequential and multi-core parallel processing speeds.

10. Code Walkthrough

• Partitioning Strategy: Notice that we slice the computation range (e.g. 1 to 5,000,000) into even segments, assigning each segment to a different core thread/process. This avoids overlapping calculations and maximizes parallelism.
• Multiprocessing in Python: We use multiprocessing.Pool instead of threading.Thread. In Python, threads cannot run on multiple CPU cores simultaneously because of the Global Interpreter Lock (GIL). By spawning processes instead of threads, we run separate Python interpreter instances on distinct cores, achieving true parallelism.
• C++ Futures: std::async returns a std::future. Calling .get() blocks the main thread until that core completes its partition, returning the result.

11. Execution Flow

1. Determine Hardware Capability: The runtime checks available CPU threads.
2. Decompose Workload: The input range is split into $K$ chunks (where $K$ is the core count).
3. Physical Core Scheduling: The operating system assigns each task to a separate physical core's execution pipeline.
4. Concurrent Cache Modification: Each core calculates prime numbers independently, populating its private L1/L2 caches.
5. Aggregation: The parent thread gathers and sums the counts from each child process/thread and returns the result.

12. Internal Working (False Sharing Mitigation)

In parallel computing, false sharing degrades performance when threads on different cores modify adjacent elements in a shared array. For example:

When Core 1 writes to counts[0] and Core 2 writes to counts[1], the MESI protocol invalidates the entire cache line across both cores, causing "cache line bouncing". To mitigate this:

• Use Thread-Local Variables: Perform computations inside local variables on the thread stack and only write to the shared array once at the very end.
• Padding: Pad the array elements with empty space (e.g., in Java, using @Contended annotation or inserting empty variables between active variables) so that adjacent elements land on different 64-byte cache lines.

13. Complexity Analysis

• Time Complexity: $O(M / K)$ where $M$ is the complexity of searching the range sequentially and $K$ is the number of cores.
• Space Complexity: $O(K)$ memory space to hold intermediate partition variables.

14. Best Practices

• Match Thread Count to Physical Cores: For CPU-bound tasks, limit the thread count to the machine's physical core count (Runtime.getRuntime().availableProcessors()). Adding more threads introduces context switching overhead without adding computation speed.
• Keep Tasks Stateless: Ensure threads do not share variables directly during parallel loops. This removes the need for locks, preventing thread contention.

15. Common Mistakes

• Using Python Threads for Math: Spawning threading.Thread in Python to run math computations. Because of the GIL, Python executes threads sequentially on a single core, providing no speedup. Use multiprocessing instead.
• Lock Contention in Parallel Loops: Locking a shared variable inside a parallel loop. This forces threads to wait for one another, turning the parallel execution back into a slow sequential run.

16. Interview Discussion

17. Practice Exercises

• Easy: Write a program that verifies if two variables sit on the same cache line by benchmarking modifications with different memory padding.
• Medium: Implement a parallel matrix multiplication program. Split the work across cores by rows.
• Hard: Build a parallel merge-sort algorithm using a custom ForkJoin task pool. Compare its performance with sequential merge-sort.

18. Challenge Problem

Write a high-performance Parallel Image Blur Filter. The filter applies a box blur to a 4K image (represented as a 2D integer array). Partition the image into horizontal bands and process them in parallel. Ensure you prevent false sharing at partition boundaries by using thread-local accumulation arrays. Compare processing times on different CPU core allocations.

19. Summary & Cheat Sheet

• Concurrency is about designing a program's execution structure; Parallelism is about physical simultaneous execution on multi-core hardware.
• False Sharing occurs when unrelated variables on the same 64-byte cache line are modified by different cores, triggering MESI invalidation cycles.
• Use thread-local storage to accumulate results before writing to shared memory.

20. Quiz

21. Next Lesson Preview

In the next lesson, we will explore Processes vs. Threads. We will examine how operating systems allocate isolated memory maps to processes versus shared memory to threads, and analyze context switching costs at the OS level!