Multiprocessor System
Open in the Padhaiko app8.1 Multiprocessor computers and their characteristics
Multiprocessor System
A multiprocessor is a computer system containing two or more autonomous Central Processing Units (CPUs) that share common main memory and I/O facilities under the coordinated control of a single operating system, placing it in Flynn's MIMD (Multiple Instruction, Multiple Data) category.
Key Characteristics of Multiprocessors
- Tightly Coupled vs. Loosely Coupled:
- Tightly Coupled (Shared-Memory) Multiprocessor: Processors communicate directly via a shared global main memory (e.g., Symmetric Multiprocessing, SMP, where every processor has equal access to memory and I/O).
- Loosely Coupled (Distributed-Memory Multicomputer): Each processor owns private local memory and communicates by exchanging explicit messages over an interconnection network.
- Memory Access Uniformity (UMA vs. NUMA):
- UMA (Uniform Memory Access): Access latency to any physical memory word is identical for every processor (typical SMP).
- NUMA (Non-Uniform Memory Access): Shared address space, but memory is physically distributed across processor nodes so local memory accesses are faster than remote-node accesses.
- Improved Performance & Throughput: Parallel execution of independent programs or concurrent threads of a single parallel task reduces turnaround time.
- High Reliability & Availability: Failure of one processor degrades throughput gracefully (graceful degradation) rather than crashing the entire system.
- Cache Coherence Requirement: Because each processor holds private caches of shared memory locations, hardware protocols (e.g., MESI snooping or directory-based coherence) must prevent stale reads.
8.2 Multi-core computers and their architecture
A multi-core computer (Chip Multiprocessor, CMP) integrates two or more complete processing cores onto a single silicon die (chip).
Architectural Organization
Each core contains its own instruction fetch/decode pipeline, ALU/FPU, registers, and private L1 (often split L1-I/L1-D) and usually L2 caches. All cores on the die typically share a large L3 last-level cache and integrated memory/I/O controllers connected by an on-chip interconnect (ring bus, mesh, or crossbar).
Key Design Choices
- Homogeneous vs. Heterogeneous Cores:
- Homogeneous (Symmetric): All cores share identical ISA and microarchitecture (e.g., server CPUs).
- Heterogeneous (Asymmetric): Combines high-performance "big" cores with power-efficient "little" cores (e.g., ARM
big.LITTLE, hybrid desktop/mobile SoCs), or pairs general CPU cores with specialized GPU/NPU accelerators.
- Simultaneous Multithreading (SMT / Hyper-Threading): Each physical core maintains multiple architectural register states so two hardware threads share execution pipelines simultaneously, hiding memory stall latencies.
- Advantages Over Multi-Chip SMP: On-chip core-to-core communication operates at CPU clock speeds with minimal capacitive power, avoiding off-chip pin bottlenecks and thermal limits of high-frequency single cores.
8.3 Interconnection structure: Time-shared common bus, multiport memory, crossbar switch, multistage switching network and hypercube system
The interconnection structure defines how CPUs, memory modules, and I/O subsystems exchange data in a multiprocessor.
| Topology | Structure & Operation | Advantages | Limitations |
|---|---|---|---|
| Time-Shared Common Bus | Single set of shared address, data, and control lines connecting all CPUs, memory modules, and I/O | Lowest hardware cost; easy to add boards; natural broadcast for cache snooping | Severe bus contention limits scalability ( CPUs max); only 1 transfer at a time |
| Multiport Memory | Each memory module has separate independent ports (one per CPU) with internal priority arbitration logic | High bandwidth: multiple CPUs access different memory modules simultaneously | Expensive memory logic; fixed maximum number of CPUs wired at design time |
| Crossbar Switch | grid of crosspoint switches linking processors to memory modules | Simultaneous non-blocking transfers between all disjoint CPU–memory pairs | Switch count grows as , costly for large |
| Multistage Switching Network (Omega) | Layers of crossbar switch elements ( stages of switches for ports) | Balances cost and concurrency; switch complexity grows as | Higher latency ( stages); internal blocking possible between paths |
| Hypercube System | processor-memory nodes (dimension ) where each node connects directly to its neighbors differing in 1 bit of binary ID | Distributed routing with no central switch bottleneck; diameter is only hops | Requires links per node; point-to-point message passing latency |
Omega Network & Hypercube Addressing Details
- In an Omega multistage network (), there are stages, each containing two-input/two-output switches, giving total switches. Routing uses perfect shuffle wiring and destination address bits stage-by-stage (
0= upper output,1= lower output). - In a -dimensional hypercube ( nodes labeled to in -bit binary), two nodes connect directly iff their binary addresses differ in exact Hamming distance (1 bit flip). Routing from source to destination takes at most hops by flipping differing bits in (e-cube / dimension-order routing).
8.4 Interprocessor arbitration
When multiple CPUs or DMA controllers share a common system bus (or memory port), an interprocessor bus arbiter grants bus mastership to only one requester at a time, resolving simultaneous requests fairly and deterministically.
Static (Fixed-Priority) Hardware Arbitration
- Serial (Daisy-Chain) Arbitration: Bus Grant (
BG) passes serially from the highest-priority unit to the lowest. If a unit needs the bus, it blocksBGfrom propagating downstream and asserts Bus Busy (BBSY). Simple wiring, but physically distant units can suffer starvation. - Parallel Arbitration (Centralized Priority Encoder): Each processor has dedicated Bus Request (
BR_i) and Bus Grant (BG_i) lines wired to a priority encoder and decoder. Fast single-step resolution without daisy-chain propagation delay.
Dynamic Arbitration Algorithms
To prevent low-priority processors from starving under heavy load, dynamic arbitration updates priorities after every bus cycle:
- Time Slice (Fixed Time Slots): Allocates fixed time slices in sequence regardless of demand.
- Polling: Controller broadcasts sequential device addresses on poll lines; the addressed requester claims the bus.
- LRU (Least Recently Used): Gives highest priority to the processor that has waited longest without bus access.
- FIFO (First-In, First-Out): Services requests strictly in arrival order.
- Rotating Daisy Chain: The
BGchain forms a ring where priority rotates to the device immediately following the most recent bus master.
8.5 Interprocessor communication and synchronization
Processors cooperating on a shared task must exchange data safely and coordinate execution order.
Interprocessor Communication
- Shared-Memory Communication: Processors exchange information by reading and writing shared variables, buffers, and mailboxes in global main memory (fast, requires synchronization to prevent race conditions).
- Message-Passing Communication: In loosely coupled multicomputers (or distributed clusters), processors communicate explicitly using
send(dest, msg)andreceive(src, msg)primitives over the network.
Interprocessor Synchronization and Mutual Exclusion
When multiple processors read-modify-write a shared variable (counter = counter + 1), unsynchronized interleaving causes race conditions (lost updates). Hardware must provide atomic Read-Modify-Write instructions to build critical-section locks (semaphores / spinlocks):
Test-and-Set (TSL): Atomically reads a memory lock flag (0= free,1= locked) into a register and sets the memory location to1in an indivisible bus/cache cycle.- If the old value returned was
0, the processor acquired the lock and enters its critical section. - If the old value returned was
1, another processor holds the lock, so the caller loops (spinlock) until the holder clears the flag to0.
- If the old value returned was
Swap/Compare-and-Swap (CAS): Atomically swaps a register with memory (or updates memory only if it matches an expected value), enabling both spinlocks and lock-free shared data structures.- Hardware Barrier Synchronization: Ensures all participating processors reach a coordination point (
barrier()) before any processor proceeds to the next parallel phase.
Worked Out Examples
1
Compare the hardware switch count and communication properties of connecting processors to memory modules (or processor-memory nodes) using:
- A full Crossbar Switch
- A Omega Multistage Switching Network built from switch elements
- A -dimensional Hypercube ( nodes)
Analyzing the Crossbar Switch:
- Total crosspoint switches switches.
- Non-blocking: all disjoint CPU–memory pairs can transfer simultaneously in switch hop.
Analyzing the Omega Multistage Network: With :
- Number of stages stages.
- switches per stage .
- Total switch elements switches (far fewer than , though internal blocking can occur).
Analyzing the -Dimensional Hypercube ():
- Links per node bidirectional links.
- Total bidirectional communication links links.
- Network diameter (maximum hops between any two nodes, e.g.,
0000to1111) hops.
- Crossbar: crosspoints, non-blocking. 2. Omega network: stages two-by-two switches. 3. 4D Hypercube: links per node, total bidirectional links, maximum distance hops.
2
In a -dimensional hypercube ( nodes with binary IDs 0000 through 1111), trace the shortest path from source node S = 0101 (node ) to destination node D = 1110 (node ) using e-cube (dimension-order) routing (resolving bit positions from LSB to MSB ). Also list all direct neighbors of node 0101.
Finding all direct neighbors of 0101: Flipping one bit at a time ():
- Flip :
0100(node ) - Flip :
0111(node ) - Flip :
0001(node ) - Flip :
1101(node )
Tracing shortest e-cube path from 0101 to 1110: Compute . Bits differ (Hamming distance hops):
- Start:
0101() - Hop 1 (flip ):
01010100() - Hop 2 (flip ):
01000110() - Hop 3 ( matches, flip ):
01101110(, destination reached)
Neighbors of 0101 are 0100, 0111, 0001, and 1101. The -hop e-cube path is 0101 -> 0100 -> 0110 -> 1110.
3
Explain why an ordinary LOAD + STORE sequence fails to enforce mutual exclusion in a multiprocessor, and write a spinlock acquire_lock / release_lock routine using an atomic TSL (Test-and-Set Lock) instruction to protect a shared counter update.
Explaining why LOAD + STORE fails: If Processor 1 and Processor 2 both execute LOAD R1, [LOCK] before either executes STORE [LOCK], #1, both observe LOCK == 0, both believe the lock is free, and both enter the critical section simultaneously—corrupting shared data.
Writing the atomic TSL-based spinlock: TSL R1, [LOCK] atomically reads [LOCK] into R1 and writes 1 to [LOCK] in one uninterruptible bus/cache operation:
ACQUIRE_LOCK:
TSL R1, [LOCK] ; atomically R1 <- LOCK; LOCK <- 1
CMP R1, #0 ; was the lock previously free?
JNZ ACQUIRE_LOCK ; if old value was 1, spin and retry
RET ; old value was 0 -> lock acquired
; --- Critical Section ---
; Safely update shared variables here
RELEASE_LOCK:
STORE [LOCK], #0 ; release lock so waiting CPU can enter
RETSeparate LOAD/STORE suffers a race condition between reading 0 and writing 1. An atomic TSL instruction combines both into an indivisible operation so at most one CPU observes 0 and enters the critical section.
Exercises
Exercise — Multiprocessor System
Define a multiprocessor system and distinguish between: (a) tightly coupled vs. loosely coupled multiprocessors, and (b) UMA vs. NUMA shared-memory architectures. Explain why cache coherence is essential in SMP systems.
Distinguishing coupling and memory-access models:
- Tightly Coupled vs. Loosely Coupled: Tightly coupled multiprocessors share a global main memory under one OS and communicate via shared variables; loosely coupled multicomputers give each node private local memory and communicate via explicit message passing.
- UMA vs. NUMA: UMA gives every processor equal latency to any shared memory address, whereas NUMA physically distributes shared memory across nodes so local accesses are faster than remote accesses.
Explaining cache coherence: When multiple processors cache copies of the same shared memory block and one CPU modifies its cached copy, other CPUs holding old copies would read stale values unless a coherence protocol (snooping or directory-based) invalidates or updates the stale copies.
Tightly coupled systems share global memory (UMA equal-latency or NUMA distance-dependent latency), whereas loosely coupled systems pass messages between private-memory nodes. Cache coherence ensures all CPUs observe consistent updates across private caches.
Describe the architecture of a multi-core computer (CMP), distinguishing between private and shared cache levels, homogeneous vs. heterogeneous cores, and how Simultaneous Multithreading (SMT) complements multiple physical cores.
Describing CMP architecture and design variants:
- Cache Hierarchy: Each physical core holds private L1 (and typically L2) caches for low-latency access, while all cores share a large on-die L3 cache and memory controller.
- Homogeneous vs. Heterogeneous: Homogeneous CMPs replicate identical cores for uniform throughput; heterogeneous CMPs combine high-performance cores with power-efficient cores (or specialized accelerators) to optimize performance per watt.
- SMT: Allows a single physical core to maintain two or more thread register contexts and dispatch instructions from both threads in the same cycle to fill idle execution slots during cache misses.
Multi-core chips integrate multiple cores with private L1/L2 caches and a shared L3 cache, using either identical (homogeneous) or mixed performance/efficiency (heterogeneous) cores, often paired with SMT to keep core pipelines busy across memory stalls.
Compare a Time-Shared Common Bus, Crossbar Switch, and Omega Multistage Network for interconnecting processors and memory modules. Calculate the switch count for the Crossbar and Omega network, and find the total links and diameter of an -node (-D) Hypercube.
Comparing topologies and calculating switch/link counts:
- Time-Shared Common Bus: Simplest ( shared bus), lowest cost, but allows only memory transfer at a time (high contention).
- Crossbar Switch (): crosspoints; supports simultaneous non-blocking transfers.
- Omega Network (, ): stages switches per stage two-by-two switches; cost with possible internal blocking.
- 3-D Hypercube (): Degree links per node, diameter hops, and total bidirectional links links.
An Crossbar needs crosspoints (non-blocking), an Omega network needs two-by-two switches ( stages), and a 3-D Hypercube has bidirectional links with diameter .
Contrast static (fixed-priority) bus arbitration (daisy-chain and parallel priority) with dynamic bus arbitration schemes (polling, LRU, FIFO, rotating daisy chain). Which problem of static arbitration do dynamic schemes solve?
Contrasting static and dynamic bus arbitration:
- Static Arbitration: Assigns permanent fixed priorities—either serially via a daisy-chain (
BGpropagates from highest- to lowest-priority device) or in parallel via a central priority encoder. Under heavy bus demand from high-priority masters, low-priority processors suffer starvation. - Dynamic Arbitration: Continuously rotates or updates priorities after each grant—using polling, LRU (oldest unserved requester wins), FIFO (arrival order), time-slicing, or a rotating daisy chain—guaranteeing bounded waiting time and fairness for every processor.
Static arbitration (daisy-chain or parallel priority) gives fixed priority and risks starving low-priority processors under heavy traffic, whereas dynamic schemes (polling, LRU, FIFO, rotating daisy chain) vary priority each cycle to ensure fair access.
Compare shared-memory and message-passing interprocessor communication, and explain how hardware atomic instructions such as Test-and-Set or Compare-and-Swap implement critical-section synchronization and barriers.
Comparing communication models and synchronization mechanisms:
- Shared-Memory: Processors communicate implicitly by reading and writing shared variables/mailboxes in global RAM; low latency but requires explicit locking against race conditions.
- Message-Passing: Processors with private memories communicate explicitly via
send/receiveprimitives; scales cleanly to large clusters with no shared-memory hardware needed. - Atomic Hardware Synchronization: Instructions like
Test-and-Set(TSL) andCompare-and-Swap(CAS) execute a read and conditional write atomically in a single indivisible memory/cache transaction, preventing two CPUs from simultaneously acquiring a spinlock or corrupting barrier counters.
Shared-memory communication exchanges data via global RAM variables/mailboxes while message-passing uses explicit send/receive calls. Atomic instructions (TSL, CAS) perform indivisible read-modify-write cycles to safely build spinlocks, semaphores, and synchronization barriers.