4.3 Parallel Processing & Multiprocessor Architectures

Prerequisites

Before studying this chapter, ensure you have reviewed the following topics:

• Chapter 1.4: Interconnection & Bus Structures (bus arbitration and bus protocol signaling)
• Chapter 3.3: Cache Memory & Mapping (direct, associative, set-associative cache mappings)
• Chapter 3.4: Cache Writing Policies (write-through vs write-back policies)
• Chapter 4.2: Pipelining (instruction execution stages, hazards, and branch penalties)

1. Introduction to Parallel Processing

Performance scalability of single-processor architectures is constrained by three physical limits: the **memory wall** (memory latency gap), the **ILP wall** (diminishing returns of instruction-level parallelism), and the **power wall** (thermal dissipation limits of CMOS technology). To continue scaling compute performance, architectures exploit **concurrency** across multiple layers:

• Bit-Level Parallelism: Increasing word size (e.g., from 32-bit to 64-bit ALUs) to reduce instruction counts for large calculations.
• Instruction-Level Parallelism (ILP): Overlapping instructions using pipelining and superscalar execution.
• Data-Level Parallelism (DLP): Operating on arrays of data simultaneously using vector or array processing.
• Task-Level Parallelism (TLP): Running independent thread processes concurrently on multiple physical cores or CPUs.

The speedup limit of parallelizing any program is governed by **Amdahl's Law**:

Equation 4.3.1: Amdahl's Law, where f is the fraction of the program that is parallelizable, and N is the number of parallel processing elements.

2. Vector and Array Processing

Both vector and array processors utilize data-level parallelism (SIMD) to accelerate mathematical matrix computations.

Vector Processing

Vector processors operate on entire arrays of data using a single instruction (e.g., adding two vectors $A+B$ of length 64). Rather than replicating ALUs, a vector processor uses deeply pipelined **vector functional units**. Operands are streamed continuously from high-speed **vector registers** into the execution pipeline, producing one vector element result per clock cycle once the pipeline is full.

Array Processors

Unlike vector processors which pipeline operations, **Array Processors** utilize a spatial array of independent **Processing Elements (PEs)**, each with its own local memory, controlled by a central **Master Control Unit (MCU)**. The MCU fetches and decodes instructions, broadcasting the control signals to all PEs. All PEs execute the same instruction on different local data elements in parallel.

3. Multiprocessor System Architectures

A multiprocessor system contains two or more processing units sharing memory and input-output systems:

• Shared Memory (Tightly Coupled): Processors share a single, global physical address space. Communication occurs implicitly through shared memory reads and writes. These systems are classified as **Symmetric Multiprocessors (SMP)** (uniform memory access time) or **Non-Uniform Memory Access (NUMA)** (memory access time varies depending on physical distance to memory bank).
• Distributed Memory (Loosely Coupled): Each processor has its own local memory and address space. Communication occurs explicitly by passing messages over a message-passing network interface.

4. Interconnection Structures

To link multiple processors with memory modules or message interfaces, systems utilize different interconnection network topologies:

• Time-Shared Common Bus: All processors and memory share a single communication bus. Cost is minimal ($O(1)$), but bandwidth limits performance as processor counts scale due to bus contention.
• Crossbar Switch Matrix: Provides a dedicated, separate switch at every path junction between $N$ processors and $M$ memory modules. Cost is high ($O(N \times M)$), but contention only occurs if two processors target the exact same memory module simultaneously.
• Multistage Interconnection Network (MIN): Balances cost and performance using smaller $2\times2$ crossbar switches organized in cascading stages. An example is the **Omega Network**, which uses a shuffle-exchange wiring pattern. An $N \times N$ network requires: $$\text{Stages} = \log_2 N, \quad \text{Switches per Stage} = \frac{N}{2}$$
• Hypercube Topology: An $n$-dimensional hypercube connects $N = 2^n$ nodes. Each node represents a vertex of an $n$-dimensional cube and is connected to exactly $n$ neighbor nodes. The node address is represented by binary labels, and links exist only between nodes whose binary addresses differ by exactly 1 bit (Hamming distance of 1).

5. Inter-processor Arbitration & Bus Contention

When multiple processors share a common bus, an **Arbitration Circuit** must resolve conflicting requests:

• Daisy Chain (Serial) Arbitration: A single bus grant signal is routed serially through all master modules. The first processor in the chain requesting the bus intercepts the signal, preventing downstream processors from accessing the bus. This circuit is cheap ($O(1)$ lines) but assigns static priority based on physical location, introducing a single point of failure.
• Parallel Arbitration: Each processor has dedicated bus request ($BR_i$) and bus grant ($BG_i$) lines connected to a central arbiter. The arbiter resolves conflicts using dynamic algorithms (e.g., Round Robin or Rotating Priority).

6. Cache Coherence & The MESI Snoopy Protocol

In shared-memory multiprocessors, each processor features its own local cache. If multiple processors cache the same memory block $X$, and processor $P_1$ writes a new value to $X$, the other caches contain stale data. This is the **Cache Coherence Problem**.

To maintain consistency, processors implement **Snoopy Protocols**, where cache controllers monitor (snoop) the shared bus to detect writes to cached memory blocks.

The MESI snoopy protocol defines 4 states for a cache block:

• M (Modified): The block is present only in the local cache and contains modified, dirty data that differs from main memory. The local cache is responsible for writing it back.
• E (Exclusive): The block is present only in the local cache, containing clean data that matches main memory.
• S (Shared): The block is present in multiple caches, containing clean data matching main memory.
• I (Invalid): The block does not contain valid data.

7. Superscalar Processors & Instruction Concurrency

While pipelining overlaps instructions sequentially, a **Superscalar Processor** exploits Instruction-Level Parallelism (ILP) by executing multiple instructions *in parallel during the same clock cycle*.

A superscalar CPU features multiple parallel execution units (multiple ALUs, FPUs, and Load/Store units) and an instruction fetch unit that retrieves multiple instructions per cycle.

To maximize ALU utilization, modern superscalar CPUs implement **Out-of-Order (OoO) Execution**. Instructions are fetched and decoded in-order, placed in **Reservation Stations**, executed out-of-order as soon as their data operands become available, and finally retired in-order using a **Reorder Buffer (ROB)** to maintain correct program execution logic.

8. Worked Examples

9. Practice Numerical Problems

10. Assessment Bank (GATE & University)

GATE Questions

University Exam Questions

UQ 4.3.1: Define and compare Symmetric Multiprocessors (SMP) and Non-Uniform Memory Access (NUMA) multiprocessors. (8 marks)

UQ 4.3.2: Describe the 4 states of the MESI cache coherence protocol. Detail the transition that occurs when a processor reads a block that is in the Modified state in another processor's cache. (10 marks)

Viva Voce Questions

VQ 4.3.1: What is the difference between tightly coupled and loosely coupled multiprocessors?

Model Answer: Tightly coupled multiprocessors share a single global memory address space, and processors communicate implicitly through shared memory variables. Loosely coupled multiprocessors possess independent local address spaces and memory blocks, communicating explicitly by passing message packets over a network interface.