INTRODUCTION TO PARALLEL COMPUTING — 2ND EDITION

Chapter 2

Parallel Programming Platforms

From implicit parallelism inside a single CPU to the architectures that connect thousands of processors

Ananth Grama · Anshul Gupta · George Karypis · Vipin Kumar

 CHAPTER ROADMAP

Four Big Ideas in This Chapter

01 02 03 04

A Dichotomy of
Implicit Parallelism Physical Organization Communication Costs
Platforms
How a single modern Classifying parallel machines The PRAM abstraction, real Why moving data, not just
processor already runs several by control structure interconnection networks, and computing, dominates the
things at once — pipelining, (SIMD/MIMD) and cache coherence. performance of parallel
superscalar issue, VLIW. communication model. programs.

Chapter 2 — Parallel Programming Platforms 1

 MOTIVATION

Why the Platform Matters as Much as the Algorithm

✦ A parallel algorithm's real-world speed depends on how well it matches

the underlying hardware, not only on its theoretical operation count. Parallel Algorithm

✦ The same algorithm can behave very differently on a multicore laptop, a

GPU, and a distributed cluster.

✦ Understanding processor-level and network-level design choices helps Programming Model

programmers reason about scalability, communication overhead, and
memory behavior before writing code.

✦ This chapter builds the vocabulary used throughout the rest of the book
to describe and compare platforms. Hardware Platform

Chapter 2 — Parallel Programming Platforms 2

 IMPLICIT PARALLELISM

Parallelism Hidden Inside a Single Processor

✦ Even a program written with no parallel constructs runs on hardware that is

internally parallel. Pipelining
1
Overlap instruction stages
✦ Modern CPUs exploit instruction-level parallelism (ILP) automatically,
without the programmer's knowledge.

✦ Three classic mechanisms deliver this: pipelining, superscalar execution, Superscalar

and VLIW (compiler-scheduled) execution. 2
Issue multiple instructions/cycle

✦ These techniques motivate why understanding hardware helps explain

performance even for “serial” code.
VLIW
3
Compiler packs instructions

Chapter 2 — Parallel Programming Platforms 3

 IMPLICIT PARALLELISM

Pipelining: Overlapping Instruction Stages

✦ An instruction's execution is split into stages — e.g. Fetch, Decode, Execute, Write-back — handled by separate hardware units.
✦ While one instruction is being decoded, the next can already be fetched, so several instructions are in flight simultaneously.
✦ Throughput improves even though any single instruction still takes the same number of stages to finish.

t1 t2 t3 t4 t5 t6 t7

Fetch I1 I2 I3 I4

Decode I1 I2 I3 I4

Execute I1 I2 I3 I4

Write-back I1 I2 I3 I4

Four instructions (I1–I4) overlap across the four pipeline stages — by cycle t4 the pipeline is full.

Chapter 2 — Parallel Programming Platforms 4

 IMPLICIT PARALLELISM

Limits on Pipelining

! Data Hazards ! Control Hazards

An instruction needs a result that a previous instruction hasn't Branches are not resolved until late in the pipeline, so the fetched
produced yet, forcing a stall. instruction stream may be wrong.

! Structural Hazards ! Diminishing Returns

Two instructions need the same hardware unit at the same time. Deeper pipelines increase clock speed potential but raise the
misprediction and stall penalty.

Chapter 2 — Parallel Programming Platforms 5

 IMPLICIT PARALLELISM

Superscalar Execution

✦ A superscalar processor has multiple functional units (e.g. two integer ALUs,
a floating-point unit, a load/store unit) that can operate in the same cycle. Fetch / Decode / Dispatch
✦ Hardware examines a window of upcoming instructions and dynamically
issues several of them at once, provided there is no dependency conflict.

✦ Instructions may also complete out of order, with results reordered

afterward so the program's visible behavior stays correct.

✦ This raises average instructions-per-cycle (IPC) beyond what simple ALU 1 ALU 2 FPU Load/Store

pipelining allows, at the cost of more complex control logic.

Several functional units execute concurrently once instructions are

dispatched.

Chapter 2 — Parallel Programming Platforms 6

 IMPLICIT PARALLELISM

Very Long Instruction Word (VLIW) Processors

✦ VLIW moves the work of finding independent instructions from runtime hardware to compile-time software.
✦ The compiler packs several independent operations into one long instruction word, which the processor issues together every cycle.
✦ Hardware becomes simpler (no dynamic scheduling logic), but performance now depends heavily on compiler quality and on the program
having enough exposed parallelism.

Aspect Superscalar VLIW

Who finds parallelism? Hardware, at run time Compiler, at compile time

Hardware complexity High (dynamic scheduler) Lower (simple issue logic)

Sensitive to... Instruction window size Compiler scheduling quality

Typical use General-purpose CPUs DSPs, embedded / research CPUs

Chapter 2 — Parallel Programming Platforms 7

 MEMORY SYSTEM PERFORMANCE

The Growing Gap Between CPU and Memory Speed

✦ Processor clock speeds have historically improved far faster than DRAM Illustrative trend
access latency.
Processor speed
✦ The result is often called the “memory wall”: a fast processor can sit idle
Memory speed
waiting for data.

✦ Both latency (time for one request) and bandwidth (data delivered per
second) limit effective performance — improving one does not fix the other.

1990 2000 2010 2020

Chapter 2 — Parallel Programming Platforms 8

 MEMORY SYSTEM PERFORMANCE

Bridging the Gap: The Memory Hierarchy

Faster, smaller
✦ Caches sit between the processor and main memory, holding recently used
data in small, fast storage.
Registers

✦ They work because of locality of reference: programs tend to reuse recently

accessed data (temporal locality) and access nearby addresses (spatial
locality). L1 Cache

✦ The closer a memory level sits to the processor, the smaller and faster —
but more expensive per byte — it is.
L2 / L3 Cache

Main Memory (DRAM)

Slower, larger

Chapter 2 — Parallel Programming Platforms 9

 MEMORY SYSTEM PERFORMANCE

Why Hit Ratio Matters: A Simple Illustration

✦ Effective average access time blends the fast cache-hit time and the slow miss penalty, weighted by how often each occurs.

✦ Effective time ≈ (hit ratio × cache time) + (miss ratio × memory time). Small changes in hit ratio can produce large swings in effective
performance.

Cache hit ratio Effective access time (relative units)

70% ≈ 3.7

90% ≈ 2.1

97% ≈ 1.3

99% ≈ 1.1

Chapter 2 — Parallel Programming Platforms 10

Illustrative figures assuming a cache access is roughly 20× faster than a memory access — the qualitative trend (small miss-rate changes causing large swings) is what matters, not the
 MEMORY SYSTEM PERFORMANCE

Multithreading for Latency Hiding

✦ Instead of stalling while one thread waits on a memory reference, the

processor switches to another ready thread. Thread A

✦ As long as enough independent threads exist, the processor stays busy and
memory latency is “hidden” behind useful work. Thread B

✦ This requires low-cost context switching and sufficient thread-level

Thread C
parallelism in the workload to be effective.

Orange = actively computing on the processor — while one thread waits

on memory, another fills the cycle.

Chapter 2 — Parallel Programming Platforms 11

 MEMORY SYSTEM PERFORMANCE

Prefetching

✦ Prefetching issues a request for data before the processor actually needs it,
overlapping the memory latency with ongoing computation.
Compute Prefetch Compute
✦ Hardware prefetchers watch access patterns (e.g. sequential strides) and on A[i] A[i+k] on A[i+1]
speculatively fetch ahead.

✦ Software prefetching lets the compiler or programmer insert explicit hints so

data arrives just in time. The prefetch for a future element overlaps with computation on the
current one, hiding memory latency.
✦ Poorly tuned prefetching can waste bandwidth by fetching data that is never
used.

Chapter 2 — Parallel Programming Platforms 12

 Flynn’s Classification

● Number of concurrent instructions (or control) streams and data stream available
in the architecture can be single or multiple.

Single Instruction Stream, Single Data Stream (SISD)

2. Single Instruction Stream, Multiple Data Streams (SIMD)

3. Multiple Instruction Streams, Single Data Stream (MISD)

4. Multiple Instruction Streams, Multiple Data Streams (MIMD)

 A DICHOTOMY OF PLATFORMS

Two Independent Ways to Classify a Parallel Machine

✦ Beyond implicit, single-processor parallelism, real parallel machines are built from many processing elements, and can be classified
along two largely independent dimensions.

Control Structure Communication Model

How processing elements receive and follow instructions. How processing elements exchange data with one another.

SIMD Shared Address Space

MIMD Message Passing

Chapter 2 — Parallel Programming Platforms 13

 CONTROL STRUCTURE

SIMD: Single Instruction, Multiple Data

✦ One control unit broadcasts a single instruction to many processing

elements, each applying it to its own piece of data in lockstep.
Control Unit
✦ All active elements execute the same operation on the same clock cycle —
simple, efficient hardware, but rigid.

✦ Well suited to regular, data-parallel work such as image processing and

dense linear algebra.

✦ Modern GPUs and vector/SIMD instruction extensions follow this model at

PE1 PE2 PE3 PE4
various scales.

Same instruction, different data, every element in step.

Chapter 2 — Parallel Programming Platforms 14

 CONTROL STRUCTURE

MIMD: Multiple Instruction, Multiple Data

✦ Each processing element has its own control unit and follows its own
independent instruction stream, on its own data. CU1 CU2 CU3 CU4

✦ Processors can run entirely different programs, or the same program at

different points — no lockstep requirement.

✦ Far more flexible than SIMD, at the cost of more complex hardware and the PE1 PE2 PE3 PE4
need to coordinate independently-running processors.

✦ Most general-purpose parallel machines today — multicore CPUs, clusters,

clouds — are MIMD. Each PE follows its own control unit — independent instructions,
independent data.

Chapter 2 — Parallel Programming Platforms 15

 CONTROL STRUCTURE

SIMD vs. MIMD at a Glance

Aspect SIMD MIMD

Instruction stream One, broadcast to all PEs One per processing element

Flexibility Low — lockstep execution High — independent execution

Hardware cost per PE Lower (no control unit) Higher (own control unit)

Best suited for Regular, data-parallel work Irregular, task-parallel work

Examples GPUs, vector units Multicore CPUs, clusters

Chapter 2 — Parallel Programming Platforms 16

 COMMUNICATION MODEL

Shared-Address-Space Platforms

✦ All processors can read and write a common, global memory address space
— communication happens implicitly through ordinary loads and stores.
Shared Memory
✦ Uniform Memory Access (UMA): every processor sees the same access time
to any memory location.

✦ Non-Uniform Memory Access (NUMA): each processor has memory that is

“closer” and faster to reach than the rest.

✦ Simple to program, but requires careful synchronization to avoid race

conditions. P1 P2 P3 P4

Every processor reads and writes the same memory.

Chapter 2 — Parallel Programming Platforms 17

 COMMUNICATION MODEL

Message-Passing Platforms

✦ Each processor has its own private local memory; there is no shared address
space.
P1 P2 P3 P4
✦ Processors exchange data explicitly, through send and receive operations
over an interconnection network.

✦ The programmer is fully responsible for orchestrating communication and Mem Mem Mem Mem
synchronization — more effort, but often scales to far larger systems.

✦ This model underlies clusters and distributed-memory supercomputers, Each processor owns private memory; data moves only via explicit
typically programmed with libraries like MPI. messages.

Chapter 2 — Parallel Programming Platforms 18

 COMMUNICATION MODEL

Shared Memory vs. Message Passing: Trade-offs

Aspect Shared Address Space Message Passing

Programming style Implicit via loads/stores Explicit send/receive calls

Synchronization Locks, semaphores, barriers Message ordering, barriers

Scalability Limited by memory contention Scales to very large systems

Data movement Hidden from the programmer Fully visible and controlled

Chapter 2 — Parallel Programming Platforms 19

 PHYSICAL ORGANIZATION

The Ideal Parallel Computer: PRAM

✦ The Parallel Random Access Machine (PRAM) is a theoretical model: p

processors, each able to access any word of a shared global memory in one
unit of time. Global Shared Memory
(unit-time access)
✦ It ignores communication and synchronization costs entirely, isolating the
effect of an algorithm's inherent parallelism.

✦ Extremely useful for algorithm design and asymptotic analysis, but no real
machine can offer uniform, unit-time access at large scale.

✦ PRAM variants differ in how they handle simultaneous access to the same P1 P2 P3 P4
memory location.

Chapter 2 — Parallel Programming Platforms 20

 PHYSICAL ORGANIZATION

PRAM Variants

✦ PRAM models are distinguished by whether they permit concurrent (simultaneous) reads and/or writes to the same memory location.

Model Concurrent Reads? Concurrent Writes?

EREW No — Exclusive Read No — Exclusive Write

CREW Yes — Concurrent Read No — Exclusive Write

ERCW No — Exclusive Read Yes — Concurrent Write

CRCW Yes — Concurrent Read Yes — Concurrent Write

CRCW needs a conflict-resolution rule (e.g. lowest-index processor wins) when several processors write simultaneously.

Chapter 2 — Parallel Programming Platforms 21

 PHYSICAL ORGANIZATION

Interconnection Networks: Static vs. Dynamic

Static Networks Dynamic Networks

Fixed, dedicated point-to-point links between processors that do Programmable switches connect processors to memory or to each
not change at run time. other on demand.

Bus Crossbar

Ring Multistage (e.g. Omega)

Mesh

Tree

Hypercube

Chapter 2 — Parallel Programming Platforms 22

 INTERCONNECTION NETWORKS

Static Topologies: Bus, Ring, Mesh

Bus Ring 2-D Mesh

All processors share one communication line —

Each processor links to exactly two neighbors, Processors form a grid, each linked to its (up to 4)
simple, but contention grows with processor
forming a closed loop. grid neighbors.
count.

Chapter 2 — Parallel Programming Platforms 23

 INTERCONNECTION NETWORKS

Static Topologies: Tree and Hypercube

Complete Binary Tree 3-D Hypercube

Processors sit at the leaves; internal nodes route messages upward and Each of the 8 nodes connects to the 3 nodes differing by one bit — short
downward. diameter, rich connectivity.

Chapter 2 — Parallel Programming Platforms 24

 INTERCONNECTION NETWORKS

Dynamic Networks: Crossbar and Multistage

✦ A crossbar switch connects every input to every output through a grid of

switching points, giving full connectivity with no contention — but its cost
Crossbar (4×4)
grows quadratically with the number of ports.

✦ Multistage networks (e.g. the Omega network) use several stages of small
switches to approximate full connectivity at much lower cost, at the price of
possible contention between paths.

✦ Dynamic networks trade cost, contention, and latency against one another;
the right choice depends on system scale and traffic pattern.

Chapter 2 — Parallel Programming Platforms 25

 INTERCONNECTION NETWORKS

Comparing Topologies: Key Metrics

✦ Diameter: the longest shortest-path between any two nodes — lower means faster worst-case communication.
✦ Bisection width: the minimum number of links that must be cut to split the network into two equal halves — higher means better resistance to
bottlenecks.
✦ Cost: roughly the total number of links — more links generally mean better performance but higher hardware expense.

Topology Diameter Bisection Width Cost (links)

Bus O(1) 1 O(1)

Ring (p nodes) O(p) 2 O(p)

2-D Mesh (√p × √p) O(√p) O(√p) O(p)

Hypercube (p = 2^d) O(log p) O(p) O(p log p)

Complete graph O(1) O(p²) O(p²)

Chapter 2 — Parallel Programming Platforms 26

 CACHE COHERENCE

The Cache Coherence Problem

✦ In a shared-memory multiprocessor, each processor typically keeps its own

cache of shared data for speed.
P1 Cache: x=5 P2 Cache: x=3
✦ If processor A updates its cached copy of a variable, other processors' cached
copies of that same variable become stale unless something intervenes.

✦ A cache-coherence protocol ensures all processors observe a consistent view

Main Memory: x=5
of shared memory despite these private caches.

✦ The two dominant approaches are snooping (bus-based) and directory-based

protocols. P2 wrote x=3 locally — P1's cache and main memory are now stale unless
the protocol updates them.

Chapter 2 — Parallel Programming Platforms 27

 CACHE COHERENCE

Snooping vs. Directory-Based Protocols

Aspect Snooping Directory-Based

A central/distributed directory tracks which caches hold each

Mechanism Caches monitor a shared bus for relevant transactions
block

Network assumption Requires a broadcast medium (bus) Works over general interconnects

Scalability Limited — bus bandwidth saturates Scales to large processor counts

Overhead Low for small systems Directory storage and lookup overhead

Chapter 2 — Parallel Programming Platforms 28

 CHAPTER 2 — KEY TAKEAWAYS

Parallel Programming Platforms: What to Remember

✦ Modern processors already exploit implicit parallelism via pipelining, superscalar issue, and VLIW.

✦ Memory bandwidth and latency, not raw compute, often bound real performance — hidden by caching, multithreading,
and prefetching.

✦ Platforms differ along two axes: control structure (SIMD/MIMD) and communication model (shared memory/message
passing).

✦ The PRAM model isolates algorithmic parallelism; real interconnection networks add diameter, bisection width, and cost
trade-offs.

✦ Cache coherence protocols (snooping, directory-based) keep shared data consistent across private caches.

Chapter 2 — Parallel Programming Platforms 29