Multicores, Multiprocessors & Clusters: Parallelism & Scalability

Key Concepts and Definitions

1. Parallelism vs. Concurrency

Parallelism refers to the ability of a system to execute multiple tasks simultaneously using multiple processing units (cores, CPUs, or nodes). Concurrency, on the other hand, refers to the ability to manage multiple tasks interleaved over time (e.g., time-sharing in a single-core system).

mindmap
  root((Parallelism & Concurrency))
    Parallelism["Multiple tasks execute **simultaneously**"]
      Types["Spatial (true parallelism)"]
      Types["Temporal (pseudo-parallelism)"]
    Concurrency["Tasks appear to run simultaneously but are interleaved"]
      Example["Single-core OS scheduling"]
      Example["Multithreading in a single core"]
    KeyDifference["Parallelism requires **hardware** support (multiple cores), while concurrency can work on a single core."]

2. Multicore Processors

A multicore processor integrates multiple independent processing units (cores) into a single chip. Each core can execute instructions independently, sharing resources like cache and memory.

How Multicores Work

• Symmetric Multiprocessing (SMP): All cores are identical and share a common memory.
• Asymmetric Multiprocessing (AMP): Cores have different roles (e.g., one master core, others as slaves).
• Hyperthreading (Intel) / SMT (Simultaneous Multithreading): A single core appears as multiple logical cores by interleaving threads.

flowchart LR
  A["Multicore CPU"] --> B["Core 1"]
  A --> C["Core 2"]
  A --> D["Core 3"]
  B --> E["L1 Cache"]
  C --> F["L1 Cache"]
  D --> G["L1 Cache"]
  E --> H["L2 Cache"]
  F --> H
  G --> H
  H --> I["Shared L3 Cache"]
  I --> J["Main Memory"]
  J --> K["I/O"]

Advantages of Multicores

• Higher throughput: Multiple tasks run in parallel.
• Better power efficiency: Idle cores can be powered down.
• Cost-effective: More performance per watt.

Disadvantages

• Complexity in programming: Requires parallel algorithms (e.g., OpenMP, MPI).
• Memory contention: Shared resources (cache, memory) can become bottlenecks.
• Amdahl’s Law: Speedup is limited by sequential parts of a program.

In the Real World

1. WhatsApp (Meta):

   • Uses multicore servers to handle billions of messages simultaneously. Each core processes a subset of users, reducing latency.
   • Example: When you send a message, it is routed to a core handling your region, ensuring faster delivery.

2. Nepal Rastra Bank (NRB) Financial Systems:

   • Banks like Nabil Bank and Global IME use multiprocessor servers to process thousands of transactions per second.
   • Example: During loan processing, multiple cores verify credit scores, process payments, and update databases in parallel.

3. Google Cloud & YouTube:

   • Google’s data centers use clusters of multicore servers to handle YouTube’s video encoding, CDN distribution, and search queries.
   • Example: When you upload a video, it is split into chunks processed by different cores before being distributed globally.

3. Multiprocessor Systems

A multiprocessor system consists of multiple CPUs (not necessarily on the same chip) connected via a shared bus, crossbar switch, or network.

Types of Multiprocessor Architectures

flowchart TD
  A["Multiprocessor System"] --> B["CPU 1"]
  A --> C["CPU 2"]
  A --> D["CPU 3"]
  B --> E["Local Cache"]
  C --> F["Local Cache"]
  D --> G["Local Cache"]
  E --> H["Shared Memory Bus"]
  F --> H
  G --> H
  H --> I["Main Memory"]
  I --> J["I/O"]

Worked Example: NUMA in a Database Server

Consider a MySQL server with 4 CPUs in a NUMA architecture:

• Query 1: A user from Kathmandu requests data stored in CPU 1’s local memory.
  • Latency: Low (direct access).
• Query 2: A user from Pokhara requests data stored in CPU 3’s local memory.
  • Latency: Higher (remote access via interconnect).

Solution: Databases like PostgreSQL use NUMA-aware scheduling to minimize remote memory access.

4. Clusters and Distributed Systems

A cluster is a group of interconnected computers (nodes) working together as a single system. Clusters improve scalability and fault tolerance.

Types of Clusters

flowchart LR
  A["Cluster"] --> B["Node 1"]
  A --> C["Node 2"]
  A --> D["Node 3"]
  B --> E["Load Balancer"]
  C --> E
  D --> E
  E --> F["Shared Storage"]
  F --> G["Client Requests"]

Real-World Example: Daraz’s Order Processing

Daraz uses a cluster of servers to handle millions of orders during sales events (e.g., 11.11).

• Step 1: A user places an order → Request goes to a load balancer.
• Step 2: Load balancer routes the request to an available node.
• Step 3: Node processes payment, inventory, and shipping in parallel.
• Step 4: If a node fails, another takes over (HA cluster).

Visualization of Daraz’s Cluster:

sequenceDiagram
  User->>Load Balancer: Place Order
  Load Balancer->>Node1: Route Request
  Node1->>Payment Server: Verify Payment
  Node1->>Inventory Server: Check Stock
  Node1->>Shipping Server: Process Delivery
  Node1-->>User: Order Confirmation

5. Parallel Programming Models

To utilize multicores/multiprocessors, we need parallel programming models:

Worked Example: Matrix Multiplication on a Multicore CPU

Consider multiplying two 4×4 matrices on a quad-core CPU:

• Sequential Approach: Takes O(n³) time (16×16×16 = 4096 operations).
• Parallel Approach:
  • Divide the matrix into 4 blocks (one per core).
  • Each core computes a 2×2 submatrix.
  • Total time: ~4× faster (assuming no overhead).

# Pseudocode for Parallel Matrix Multiplication (OpenMP)
import numpy as np
from multiprocessing import Pool

def multiply_block(args):
    A_block, B_block = args
    return np.dot(A_block, B_block)

if __name__ == "__main__":
    A = np.random.rand(4, 4)
    B = np.random.rand(4, 4)
    blocks = [(A[i:i+2], B) for i in range(0, 4, 2)]  # Split into 4 blocks
    with Pool(4) as p:  # Use 4 cores
        result = np.vstack(p.map(multiply_block, blocks))

6. Challenges in Parallel Computing

Example: Bank Transaction Deadlock

Two users transfer money between accounts:

• User 1: Locks Account A, reads Account B, updates Account A.
• User 2: Locks Account B, reads Account A, updates Account B.
• Result: Both wait forever → Deadlock.

Solution: Use two-phase locking (lock all accounts before any update).

7. Exam Tip

What to Expect in TU/PU Exams

1. Definitions & Comparisons:

   • Differentiate SMP vs. NUMA vs. AMP.
   • Explain multithreading vs. multiprocessing.
   • Marks: 5-10 (direct recall).

2. Diagrams & Worked Examples:

   • Draw a multicore CPU block diagram (show caches, shared bus).
   • Trace a NUMA memory access scenario (local vs. remote).
   • Marks: 10-15 (must be accurate).

3. Real-World Applications:

   • Explain how WhatsApp uses clusters for message routing.
   • Describe Daraz’s load balancing during sales.
   • Marks: 5-10 (link theory to practice).

4. Problem-Solving:

   • Given a parallel algorithm, calculate speedup using Amdahl’s Law.
   • Example Question:

     "A program has 20% sequential code. If you use 8 cores, what is the maximum speedup?" Solution: $\text{Speedup}=\frac{1}{(1-0.8)+\frac{0.8}{8}}=4.44$

5. Short Answer:

   • "What is a race condition? How is it prevented?"
   • "List two advantages of GPU computing."

Summary Table: Multicore vs. Multiprocessor vs. Cluster

Final Thoughts

• Multicores are everywhere (your laptop, phone, and even Raspberry Pi).
• Multiprocessors power servers and supercomputers.
• Clusters enable cloud services (AWS, Google Cloud).
• Parallel programming is the key to unlocking performance.

Practice:

1. Draw a 4-core CPU with shared L3 cache.
2. Explain how WhatsApp avoids deadlocks in message delivery.
3. Calculate the speedup for a program with 30% sequential code on 16 cores.

A plot showing speedup vs. number of processors for different sequential fractions. (Image: Daniels220 at English Wikipedia, CC BY-SA 3.0, via Wikimedia Commons)