Multiprocessor & Multicore Systems: Design, Coherence, Parallelism & Flynn’s Taxonomy

Core Concepts

1. Why Multiprocessors?

Multiprocessor systems use two or more processors (CPUs) to execute tasks simultaneously. This is critical for:

• Performance: Faster execution of parallelizable workloads (e.g., rendering 3D graphics, scientific simulations).
• Reliability: If one processor fails, others can continue (fault tolerance).
• Scalability: Adding more processors increases throughput (e.g., web servers handling thousands of requests).

Real-world example:

• eSewa (Nepal): Uses multicore servers to process thousands of online transactions per second. Each transaction (e.g., bill payment) is assigned to a separate core, reducing wait times.

2. Multiprocessor vs. Multicore Systems

3. Cache Coherence: The Biggest Challenge

In shared-memory multiprocessors, multiple cores access a shared cache. This creates problems:

• Cache Inconsistency: If Core A updates a value in cache, Core B might still see the old value.
• False Sharing: Two cores modify different variables in the same cache line, causing unnecessary cache invalidations.

sequenceDiagram
    participant CoreA
    participant CoreB
    participant Bus
    CoreA->>Bus: Write to Cache Line X (MESI: Modified)
    Bus-->>CoreB: Invalidate Cache Line X (MESI: Invalid)
    CoreB->>Bus: Read Request for Cache Line X
    Bus-->>CoreB: Data from CoreA (MESI: Shared)
    note right of CoreB: CoreB now sees updated value

Solutions: Cache Coherence Protocols

1. Snooping Protocols (e.g., MSI, MESI):

   • Every cache monitors (snoops) bus transactions.
   • States: Modified (M), Shared (S), Invalid (I), Exclusive (E).
   • Example: In a quad-core system, if Core 1 writes to a cache line, all other cores invalidate their copy.

   stateDiagram-v2
     [*] --> M: Modified (exclusive)
     M --> S: Shared (read-only)
     S --> I: Invalid (on write)
     I --> E: Exclusive (clean)
     E --> M: Modified (on write)

2. Directory-Based Protocols (used in large systems):

   • A central directory tracks which cores have which data.
   • Example: Used in IBM Power systems.

Real-world example:

• Khalti (Nepal): When multiple users check their balance simultaneously, the system uses MESI protocol to ensure all cores see the latest transaction data.

4. Flynn’s Taxonomy: Classifying Parallelism

Flynn classified computers based on instruction and data streams:

Real-world example:

• YouTube (Google): Uses SIMD in GPUs to encode videos faster (parallel processing of pixels).
• NTC’s traffic monitoring: Uses MIMD to analyze camera feeds from multiple locations simultaneously.

5. Performance Issues in Multicore Systems

1. Amdahl’s Law:

   • Not all tasks can be parallelized. Speedup is limited by the sequential portion.
   • Formula: $$\text{Speedup}=\frac{1}{(1-P)+\frac{P}{N}}$$ Where $P$ = parallelizable fraction, $N$ = number of cores.
   • Example: If 20% of a task is sequential, adding 8 cores only gives 1.25x speedup (not 8x).

2. False Sharing:

   • Two cores modify different variables in the same cache line → cache thrashing.
   • Fix: Pad variables to separate cache lines (e.g., alignas(64) int a, b;).

3. Memory Bottleneck:

   • All cores compete for the same memory bandwidth.
   • Solution: Use NUMA (Non-Uniform Memory Access) architectures (e.g., Intel Xeon).

Worked Example: Amdahl’s Law A program has 80% parallelizable code. What’s the speedup with 4 cores? $$\text{Speedup}=\frac{1}{(1-0.8)+\frac{0.8}{4}}=\frac{1}{0.2+0.2}=2.5x$$ Real-world tie-in: If Daraz’s order processing is 80% parallelizable, adding 4 cores only halves the time (not quarters it).

6. Shared-Memory vs. Distributed-Memory Systems

7. Multicore Design Challenges

1. Power Consumption:
   • More cores → higher heat → need better cooling (e.g., liquid cooling in servers).
2. Programming Complexity:
   • Race conditions, deadlocks, and starvation require careful synchronization (e.g., mutexes, semaphores).
3. Cache Hierarchy:
   • Private L1/L2 caches per core + shared L3 cache (e.g., Intel’s ring bus).

Real-world example:

• Pathao’s ride-matching: Uses multicore servers to handle thousands of driver-location updates. A race condition here could assign the same rider to two drivers!

In the Real World

1. eSewa’s Transaction Processing:

   • Uses MESI protocol to keep all cores synchronized when updating user balances during payments.
   • Why? If two users transfer money simultaneously, the system must ensure no double-spending.

2. Google’s Tensor Processing Units (TPUs):

   • SIMD architecture for AI training. Each TPU core processes a batch of data in parallel (e.g., training a neural network on 1000 images at once).

3. Nepal Electricity Authority (NEA) Grid Monitoring:

   • Uses MIMD to analyze power consumption data from thousands of substations in real time. Each core processes a different region’s data.

4. WhatsApp’s End-to-End Encryption:

   • On your phone’s multicore chip, encryption/decryption uses SIMD instructions (e.g., AES-NI) to speed up cryptographic operations.

Exam Tip

1. Cache Coherence is Key:

   • Always explain why coherence is needed (shared data inconsistency) and how protocols like MESI solve it.
   • Past exam pitfall: Students often forget to mention false sharing as a performance issue.

2. Flynn’s Taxonomy:

   • Memorize the table and give real examples (e.g., GPU = SIMD, supercomputer = MIMD).
   • Exam trick: If asked about parallelism in uniprocessors, mention instruction-level parallelism (ILP) (e.g., pipelining, superscalar execution).

3. Amdahl’s Law:

   • Always calculate speedup if given parallelizable fraction and core count. Show your work step-by-step.
   • Example question: "A program is 70% parallelizable. What’s the speedup with 8 cores?" → Answer: ~2.67x.

4. Multicore vs. Multiprocessor:

   • Compare cost, scalability, and communication (e.g., "Multiprocessors use a crossbar switch, while multicores share a bus").
   • Past exam win: Mention NUMA for large shared-memory systems.

5. Real-World Applications:

   • Tie examples to Nepal (e.g., Ncell’s call routing uses MIMD, NEPSE’s stock trading uses low-latency multicore servers).
   • Avoid generic answers: Instead of "used in servers," say "Khalti’s payment system uses MESI to prevent double-spending."

graph TD
    A["Multiprocessor System"] --> B["Shared Memory"]
    A --> C["Distributed Memory"]
    B --> D["Cache Coherence\n(MESI, MOESI)"]
    B --> E["NUMA Architecture"]
    C --> F["Message Passing\n(MPI, RPC)"]
    D --> G["False Sharing\nSolution: Padding"]
    E --> H["Non-Uniform Latency"]
    F --> I["Supercomputers\n(e.g., Summit)"]
    G --> J["Performance Degradation"]