CSC 426 — Parallel Computing: A Comprehensive

Guide
A complete, in-depth synthesis of all course materials. This guide is designed to be
read cover-to-cover as a self-contained textbook for the CSC 426 course. Every key
concept, formula, algorithm, and worked example from the source materials is included.

Table of Contents
• Part I: Foundations of Parallel Computing
• Chapter 1: Introduction to Parallel Computing
• Chapter 2: Flynn's Taxonomy — Classifying Parallel Architectures
• Chapter 3: Memory Architectures — Shared, Distributed, and Hybrid
• Part II: Processor Organizations
• Chapter 4: Symmetric Multiprocessors (SMP)
• Chapter 5: Cache Coherence and the MESI Protocol
• Chapter 6: Non-Uniform Memory Access (NUMA)
• Chapter 7: Clusters and Multithreading
• Part III: Performance Theory
• Chapter 8: Amdahl's Law — The Limits of Parallelism
• Chapter 9: Gustafson's Law — Scaled Speedup
• Chapter 10: Amdahl vs. Gustafson — A Detailed Comparison
• Part IV: Pipelining
• Chapter 11: Pipeline Fundamentals and Performance Metrics
• Chapter 12: Pipeline Hazards — Instruction and Data Dependencies
• Chapter 13: Hazard Resolution Techniques
• Chapter 14: Advanced Pipelines and Instruction-Level Parallelism
• Part V: Dependence Analysis
• Chapter 15: Control Dependencies
• Chapter 16: Data Dependencies and Bernstein's Conditions
• Part VI: The PRAM Model
• Chapter 17: PRAM Architecture and Memory Models
• Chapter 18: PRAM Algorithms — Parallel Binary Search
• Part VII: Parallel Programming Models
• Chapter 19: The Message Passing Model and MPI
 • Chapter 20: The Shared Memory Model and OpenMP
• Chapter 21: Distributed Communication Primitives
• Part VIII: Practical Parallel Program Design
• Chapter 22: Designing Parallel Programs
• Chapter 23: Performance Analysis and Debugging

Part I: Foundations of Parallel Computing

Chapter 1: Introduction to Parallel Computing

1.1 What is Parallel Computing?
Parallel computing refers to the simultaneous use of multiple processing resources to solve a
computational problem. Instead of executing a single instruction at a time on a single CPU (serial
computing), parallel computing divides a large problem into smaller, independent sub-problems that
can be processed concurrently by multiple processors.
Traditionally, all software was written for serial computation:
• Programs run on a single CPU.
• Problems are broken into a discrete set of instructions.
• Instructions are executed sequentially, one after another.
• Only one instruction may execute at any moment in time.
In contrast, parallel computation:
• Uses multiple CPUs simultaneously.
• Breaks a problem into discrete parts that can be solved concurrently.
• Each part is further broken down into a series of instructions.
• Instructions from each part execute simultaneously on different CPUs.

1.2 Why Use Parallel Computing?

There are four major motivations:
1. Save time and money: Throwing more resources at a task shortens its time to completion.
Parallel clusters can be built from cheap, commodity components.
2. Solve larger problems: Many problems are so large and complex that it is impractical or
impossible to solve them on a single computer, especially given limited memory.
3. Provide concurrency: A single compute resource can only do one thing at a time. Multiple
resources can do many things simultaneously.
 4. Use non-local resources: When local compute resources are scarce, you can leverage
resources across a wide area network or even the Internet.

1.3 Types of Parallel Computing

There are three fundamental types:

Type Description Example

Bit-level parallelism Increases processor word size A 16-bit processor can add two
to reduce the number of 16-bit numbers in one
instructions needed for multi- instruction; an 8-bit processor
word operations. needs two.
Instruction-level parallelism The processor executes multiple Superscalar processors, VLIW
(ILP) instructions per clock cycle. architectures.
Uses static (compiler) or
dynamic (hardware) analysis to
identify independent
instructions.
Task parallelism Decomposes a problem into Processing different files
subtasks. Each subtask is simultaneously on different
allocated to a different cores.
processor for concurrent
execution.

1.4 Applications
Parallel computing is used in:
• Databases and data mining — querying massive datasets
• Real-time simulation — weather modeling, crash simulations
• Multimedia and networked video — encoding and streaming
• Science and engineering — molecular dynamics, finite element analysis
• Augmented/virtual reality — real-time graphics rendering
• Collaborative environments — simultaneous multi-user access

1.5 Advantages and Disadvantages

Advantages:
• Reduced computation time and potential cost savings
• Ability to solve problems too large for a single computer
• Better resource utilization (serial computing wastes potential hardware power)
• Suitable for modeling complex real-world phenomena
• Access to non-local resources when local ones are limited
Disadvantages:
 • Parallel architectures can be difficult to program
• Clusters require better cooling and more infrastructure
• Algorithms must be specifically designed for parallelism
• Multi-core architectures consume more power
• Code requires high cohesion and low coupling, which is hard to achieve
• Synchronization, thread creation, and data transfers add overhead
• Code may need different optimizations for different architectures

1.6 History of Parallel Computing

Year Milestone
1958 Stanley Gill (Ferranti) discusses parallel
programming; IBM's Slotnick and Cocke
discuss parallelism in numerical calculations
1962 Burroughs releases the D825, a four-processor
computer
1964 Slotnick proposes large-scale parallel computer
for Lawrence Livermore
1967 Amdahl and Slotnick debate feasibility of
parallel processing at AFIPS conference;
Amdahl's Law is introduced
1969 Honeywell introduces the first Multics
asymmetric multiprocessor (up to 8 processors)
1970s Carnegie Mellon's [Link] project — one of the
first multiprocessors with many processors
1984 Synapse N+1 — the first bus-connected
multiprocessor with snooping caches

1.7 Key HPC Terminology

Term Definition
Flop(s) Floating point operation(s) — the basic unit of
computational performance
Node A standalone computer within a parallel system
CPU / Core A modern CPU has several cores, each an
individual processing unit
Task A logically discrete section of computational
work
Communication Data exchange between parallel tasks
Speedup Ratio of serial execution time to parallel
execution time: S(n) = T(1) / T(n)
Term Definition
Efficiency E(n) = S(n) / n — how well processors
are utilized
Massively Parallel Systems with hundreds of thousands of
processors
Embarrassingly Parallel Problems with many similar, independent tasks
requiring very little inter-task communication
Scalability A proportionate increase in speedup with the
addition of more processors

Chapter 2: Flynn's Taxonomy — Classifying Parallel

Architectures
2.1 Overview
The most widely used classification of parallel computer architectures was introduced by Michael
Flynn in 1972. It categorizes systems based on the number of concurrent instruction streams and
data streams available.

2.2 The Four Categories

SISD — Single Instruction, Single Data Stream
• A single processor executes a single instruction stream to operate on data stored in a
single memory.
• This is the classical uniprocessor (von Neumann machine).
• Example: A basic desktop computer with one core.
┌────────┐ ┌────────┐ ┌────────┐
│ CU │────>│ PU │────>│ MU │
│(Control│ IS │(Process│ DS │(Memory │
│ Unit) │ │ Unit) │ │ Unit) │
└────────┘ └────────┘ └────────┘

• CU = Control Unit (issues instruction stream IS)

• PU = Processing Unit (operates on data stream DS)
• MU = Memory Unit

SIMD — Single Instruction, Multiple Data Streams

• A single control unit sends the same instruction to multiple processing elements
simultaneously.
• Each processing element operates on different data from its own associated memory.
• Execution is in lockstep — all processing elements execute the same instruction at the same
 time.
• Examples: Vector processors, array processors, GPUs.
┌────────┐
│ CU │
└───┬────┘
IS │ IS
┌────────┼────────┐
▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐
│ PU₁ │ │ PU₂ │ │ PUₙ │
│ LM₁ │ │ LM₂ │ │ LMₙ │
└──────┘ └──────┘ └──────┘

MISD — Multiple Instructions, Single Data Stream

• Multiple processors execute different instruction sequences on the same data stream.
• This category is largely theoretical — no commercially significant implementations exist.
• Sometimes systolic arrays are loosely categorized here.

MIMD — Multiple Instructions, Multiple Data Streams

• Multiple processors simultaneously execute different instruction sequences on different
data sets.
• This is the most general and commercially important category.
• Sub-categories:
• Shared memory (tightly coupled): All processors share a common memory.
• SMP (Symmetric Multiprocessor) — uniform access times
• NUMA (Non-Uniform Memory Access) — variable access times
• Distributed memory (loosely coupled): Each processor has its own private
memory.
• Clusters — interconnected independent computers
Flynn's Taxonomy
├── SISD (Uniprocessor)
├── SIMD (Vector/Array processors)
├── MISD (Theoretical)
└── MIMD
├── Shared Memory (tightly coupled)
│ ├── SMP
│ └── NUMA
└── Distributed Memory (loosely coupled)
└── Clusters

2.3 Why MIMD Dominates

MIMD is the most flexible architecture because:
• Each processor is general-purpose and can process all instructions.
• Processors can be further subdivided by how they communicate (shared vs. distributed
memory).
 • It naturally maps to the most common parallel programming models.

Chapter 3: Memory Architectures — Shared, Distributed, and

Hybrid
3.1 Shared Memory Architecture
In a shared memory system, multiple processors share a common address space. All processors
can access any memory location via standard load and store operations.
┌──────┐ ┌──────┐ ┌──────┐
│ CPU₁ │ │ CPU₂ │ │ CPUₙ │
│Cache₁│ │Cache₂│ │Cacheₙ│
└──┬───┘ └──┬───┘ └──┬───┘
│ │ │
└─────────┼─────────┘
│
┌────────┴────────┐
│ Shared Memory │
└─────────────────┘

Types:
• UMA (Uniform Memory Access): All processors access all memory regions with the same
latency. Also called SMP.
• NUMA (Non-Uniform Memory Access): Memory access time depends on which memory
region is being accessed relative to the processor.
Advantages:
• Global address space provides a user-friendly programming perspective.
• Fast and uniform data sharing due to proximity of memory to CPUs.
Disadvantages:
• Lack of scalability — adding more CPUs increases traffic on the shared memory bus.
• Programmer responsibility for "correct" access to global memory (race conditions).
• Cache coherence must be maintained.

3.2 Distributed Memory Architecture

Each processor has its own private local memory. Processors communicate by exchanging
messages over a network. There is no global address space.
┌──────────┐ ┌──────────┐ ┌──────────┐
│ CPU₁ │ │ CPU₂ │ │ CPUₙ │
│ Memory₁ │ │ Memory₂ │ │ Memoryₙ │
└────┬─────┘ └────┬─────┘ └────┬─────┘
│ │ │
└──────────────┼──────────────┘
│
┌────────┴────────┐
│ Network │
 └─────────────────┘

Sub-categories:
• NORMA (No Remote Memory Access): Nodes are connected only through a network.
Data exchange is only via messages. Also called Network of Workstations (NOW) or
Clusters of Workstations (COW).
• RMA (Remote Memory Access): Special hardware allows access to remote memory, but
without a global address space. Addresses use a (processor_id, local_address)
tuple.
Advantages:
• Memory scales linearly with the number of processors.
• Each CPU can rapidly access its own memory without cache coherency overhead.
• Can scale to very large numbers of nodes (210,000+ cores).
Disadvantages:
• Programmer must explicitly manage all data communication.
• Difficult to map existing global-memory-based data structures.
• Much harder to program than shared memory.

3.3 Hybrid Distributed-Shared Memory

The largest and fastest computers today use both architectures:
• Each node is a shared memory multiprocessor (SMP or NUMA).
• Nodes are connected together via a high-speed network (e.g., InfiniBand).
• Within a node: shared memory access.
• Between nodes: message passing.
Node 1 Node 2
┌─────────────────┐ ┌─────────────────┐
│ CPU₁ CPU₂ │ │ CPU₃ CPU₄ │
│ Shared Memory │──────│ Shared Memory │
└─────────────────┘ Net └─────────────────┘

This introduces a potentially three-level parallelism hierarchy: machine → node → processor

core.
Programming: Typically a hybrid approach — MPI for inter-node communication + OpenMP for
intra-node shared memory parallelism.

Part II: Processor Organizations

Chapter 4: Symmetric Multiprocessors (SMP)
4.1 Definition
A Symmetric Multiprocessor (SMP) is a standalone computer system with the following
characteristics:
1. Two or more similar processors of comparable capability.
2. Processors share the same main memory and I/O facilities, interconnected such that
memory access time is approximately the same for each processor.
3. All processors share access to I/O devices.
4. All processors can perform the same functions (hence "symmetric").
5. The system is controlled by an integrated operating system that manages interaction
between processors at the job, task, file, and data element levels.

4.2 SMP Organization

┌──────┐ ┌──────┐ ┌──────┐
│ P₁ │ │ P₂ │ │ Pₙ │
│L1/L2 │ │L1/L2 │ │L1/L2 │
│Cache │ │Cache │ │Cache │
└──┬───┘ └──┬───┘ └──┬───┘
│ │ │
└─────────┼─────────┘
│ Shared Bus
┌─────────┼─────────┐
│ │ │
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
│Main │ │I/O │ │I/O │
│Mem │ │ Adp │ │ Adp │
└─────┘ └─────┘ └─────┘

The most common interconnection is a time-shared bus. Its features:

• Addressing: Modules can be distinguished to determine source/destination of data.
• Arbitration: Any module can temporarily become "master." A priority scheme resolves
competing requests.
• Time-sharing: When one module controls the bus, others must wait.

4.3 SMP Advantages

Advantage Description
Performance Work can be split across multiple processors for
parallel execution
Availability Failure of one processor does not halt the
machine — it degrades gracefully
Incremental growth Performance can be enhanced by adding
processors
Scaling Vendors offer products with different
Advantage Description
price/performance based on processor count
Transparency Multiple processors are transparent to the user;
the OS handles scheduling

4.4 OS Design Considerations for SMP

An SMP operating system must handle:
1. Simultaneous concurrent processes: OS routines must be reentrant — multiple
processors may execute the same OS code simultaneously. Tables and management
structures must prevent deadlock.
2. Scheduling: Any processor may perform scheduling. The scheduler assigns ready processes
to available processors while avoiding conflicts.
3. Synchronization: With multiple processes accessing shared address spaces, mutual
exclusion and event ordering must be enforced.
4. Memory management: Paging mechanisms across processors must be coordinated. Page
replacement policies must consider all processors.
5. Reliability and fault tolerance: The OS must detect processor failure, restructure tables,
and continue at reduced performance.

4.5 The IBM z990 — A Mainframe SMP Example

The IBM z990 illustrates an advanced SMP that goes beyond simple bus interconnection:
• Dual-core processor chips: Each chip contains two Central Processors (CPs) with 256 KB
L1 instruction cache + 256 KB L1 data cache each.
• Shared L2 caches: 32 MB each, arranged in clusters of five, each cluster supporting eight
processor chips.
• System Control Element (SCE): Arbitrates system communication and maintains cache
coherence.
• Main Store Control (MSC): Interconnects L2 caches and main memory.
• Memory cards: Up to 8 cards × 32 GB = 256 GB maximum.
Key innovations:
1. Switched interconnection instead of a single shared bus — main memory is split across
multiple cards with independent paths, and point-to-point links connect processors to L2
caches.
2. Shared L2 caches — IBM found that mainframe workloads show a large degree of data
sharing among processors. Shared caches reduce bus traffic when processors frequently
access the same data.
Chapter 5: Cache Coherence and the MESI Protocol
5.1 The Cache Coherence Problem
When multiple processors each have their own cache, multiple copies of the same data can exist in
different caches simultaneously. If one processor modifies its cached copy, the other caches contain
stale (invalid) data.
Example scenario:
1. Processor A reads memory location X into its cache.
2. Processor B reads the same location X into its cache.
3. Processor A writes a new value to X in its cache.
4. Processor B now has an invalid copy of X.
This is the cache coherence problem.

5.2 Write Policies

Policy Behavior Coherence Issue
Write-back Writes go only to the cache; Other caches can hold stale
main memory is updated when data. Main memory is also
the cache line is flushed. stale.
Write-through Writes go to both the cache and Main memory is always
main memory. current, but other caches may
still hold stale copies unless
notified.

Even write-through can cause inconsistency unless other caches monitor memory traffic (bus
snooping) or receive direct notification.

5.3 Solution Approaches

Software solutions: The compiler and OS mark shared variables as non-cacheable, or the compiler
inserts cache-flush instructions. This is conservative and leads to inefficient cache utilization.
Hardware solutions: The most common approach. Includes:
• Bus snooping protocols (e.g., MESI) — each cache monitors the bus for writes to addresses
it has cached.
• Directory-based protocols — a central directory tracks which caches hold copies of each
memory block.

5.4 The MESI Protocol

The MESI protocol (Modified / Exclusive / Shared / Invalid) is the most widely used cache
coherence protocol. Each cache line is in one of four states:
State Meaning
Modified (M) The line has been modified in this cache and is
different from main memory. This cache has
the only valid copy. If another processor needs
this data, it must be written back first.
Exclusive (E) The line is the same as main memory and
exists in only this cache. It can be freely
modified (transitioning to M) without bus
traffic.
Shared (S) The line is the same as main memory and may
exist in multiple caches. It can only be read, not
written, without first invalidating other copies.
Invalid (I) The line is not valid in this cache (either never
loaded or invalidated by another processor's
write).

State transitions occur when processors perform reads, writes, and when bus snooping detects
actions by other processors. The protocol ensures:
• A written line is invalidated in all other caches.
• Before a processor can write to a Shared line, it must first broadcast an invalidation signal.
• A processor reading a line that is Modified in another cache triggers a write-back and data
sharing.

Chapter 6: Non-Uniform Memory Access (NUMA)

6.1 Motivation
SMP systems hit a practical scalability limit at around 16–64 processors because:
• Bus traffic increases with more processors.
• Cache coherence signals add further burden to the shared bus.
• Beyond a threshold, the bus becomes a performance bottleneck.
Clusters solve this by giving each node private memory, but applications must then work with
distributed data explicitly. NUMA provides a middle ground: a shared global address space across
many processors, while acknowledging that access times vary.

6.2 Key Definitions

Term Definition
UMA All processors access all memory regions with
the same latency. SMP is UMA.
NUMA All processors can access all memory
Term Definition
(loads/stores), but access time varies by
memory region. Local memory is fast; remote
memory is slow.
CC-NUMA Cache-Coherent NUMA — a NUMA system
that maintains cache coherence across all
processor caches via hardware protocols.

A NUMA system without cache coherence is essentially equivalent to a cluster.

6.3 CC-NUMA Organization

Node 1 Node 2
┌──────────────────────┐ ┌──────────────────────┐
│ P₁₋₁ P₁₋₂ ...P₁₋ₘ│ │ P₂₋₁ P₂₋₂ ...P₂₋ₘ│
│ L1/L2 L1/L2 L1/L2│ │ L1/L2 L1/L2 L1/L2│
│ │ │ │
│ Main Memory 1 │ │ Main Memory 2 │
│ Directory 1 │ │ Directory 2 │
│ I/O │ │ I/O │
└──────────┬───────────┘ └──────────┬───────────┘
│ │
└──────────────┬───────────────┘
│
┌─────────┴─────────┐
│ Interconnect Net │
└───────────────────┘

• Each node is effectively an SMP with its own processors, caches, and main memory.
• All nodes are connected via an interconnection network.
• Each node maintains a directory indicating the location and cache status of memory blocks.
• From any processor's perspective, there is a single addressable memory with unique
system-wide addresses.

6.4 How Remote Memory Access Works (Detailed Example)

Suppose processor P₂₋₃ (processor 3 on node 2) needs memory location 798, which resides in node
1's memory:
1. P₂₋₃ issues a read request on node 2's snoopy bus for location 798.
2. Node 2's directory recognizes that location 798 is in node 1.
3. Node 2's directory sends a request to node 1, picked up by node 1's directory.
4. Node 1's directory, acting as a surrogate of P₂₋₃, requests the contents of 798 on node 1's
bus.
5. Node 1's main memory responds, placing the data on node 1's bus.
6. Node 1's directory picks up the data.
7. The data is transferred across the interconnect to node 2's directory.
 8. Node 2's directory places the data on node 2's bus (acting as a surrogate for the remote
memory).
9. The data is picked up and placed in P₂₋₃'s cache and delivered to P₂₋₃.

6.5 NUMA Pros and Cons

Pros Cons
Scales to much larger processor counts than More complex programming — data locality
SMP (1024+) matters greatly
Maintains a transparent shared address space Remote memory access is significantly slower
than local access
Retains SMP programming model Requires directory-based cache coherence
protocols (hardware complexity)
Each node can be optimized as an SMP Performance depends heavily on data placement

Chapter 7: Clusters and Multithreading

7.1 Clusters
A cluster is a group of interconnected, whole computers working together as a unified computing
resource. "Whole computer" means each node can run independently, apart from the cluster.
Cluster types:
• Passive standby: A secondary server takes over if the primary fails.
• Active/active: All servers process requests; if one fails, the others absorb its workload.
Advantages over SMP:
• Superior scalability — can add nodes incrementally
• Superior availability — all components can be fully redundant
• Cost-effective — built from commodity hardware
Disadvantages:
• More physical space and power than a comparable SMP
• Software must explicitly manage inter-node communication
• The programming model is more complex (message passing)

7.2 Clusters vs. SMP

Feature SMP Cluster
Programming model Shared memory — simpler Message passing — more
complex
Feature SMP Cluster
Scalability Limited (16–64 processors) Excellent (thousands of nodes)
Availability Good (graceful degradation) Superior (full redundancy)
Data sharing granularity Data element level Message or file level
Physical footprint Smaller Larger

7.3 Multithreading and Chip Multiprocessors

• Chip Multiprocessor (CMP): Multiple processor cores on a single chip.
• Multithreaded processor: A single core replicates some components to execute multiple
threads concurrently.
• Coarse-grained multithreading: Switches threads on long-latency events (e.g.,
cache misses).
• Fine-grained multithreading: Switches threads every cycle.
• Simultaneous multithreading (SMT): Issues instructions from multiple threads in
the same cycle (e.g., Intel Hyper-Threading).

7.4 Vector Computation

A special-purpose parallel organization is the vector facility, tailored for processing vectors
(arrays) of data. Instead of operating on scalar values one at a time, a vector processor applies the
same operation to entire arrays simultaneously.

Part III: Performance Theory

Chapter 8: Amdahl's Law — The Limits of Parallelism

8.1 Introduction
Amdahl's Law, proposed by Gene Amdahl at the AFIPS Spring Joint Computer Conference in
1967, establishes the theoretical maximum speedup achievable when improving part of a system.
It demonstrates the fundamental constraint: the overall performance improvement is limited by
the fraction of the system that cannot be enhanced.

8.2 The Analogy

Three friends must travel to a party separately but arrive together to enter. One drives a car, another
takes the bus, and the third walks. No matter how fast the car and bus are, they must wait for the
walker. To improve overall arrival time, focus must be on helping the slowest part — not making
the already-fast parts faster.
8.3 The Formula
1
S = ─────────────────
(1 - p) + (p / s)

Where:
• S = Overall speedup of the entire program
• p = Fraction of execution time that can be improved (parallelized)
• s = Speedup factor applied to the improvable portion
• (1 - p) = Fraction that remains sequential (the bottleneck)

8.4 In Parallel Computing Context

When s = N (number of processors):
1
S = ─────────────────
(1 - p) + (p / N)

Maximum speedup (as N → ∞):

1
S_max = ─────────
(1 - p)

This means: if only 5% of a program is sequential (p = 0.95), the maximum possible speedup is
1/0.05 = 20×, regardless of how many processors you add.

8.5 Worked Examples

Example 1: 30% Improvable, 2× Speedup
p = 0.30, s = 2
S = 1 / ((1 - 0.30) + (0.30 / 2))
= 1 / (0.70 + 0.15)
= 1 / 0.85
= 1.18×

Only an 18% improvement despite doubling the speed of 30% of the system.

Example 2: 70% Improvable, 2× Speedup

p = 0.70, s = 2
S = 1 / ((1 - 0.70) + (0.70 / 2))
= 1 / (0.30 + 0.35)
= 1 / 0.65
= 1.54×

A 54% improvement — much better because the improved portion is larger.

Example 3: Multi-Part Speedup

Consider a program with four parts: p₁ = 0.11, p₂ = 0.18, p₃ = 0.23, p₄ = 0.48. Speedup factors: s₁ =
1 (no improvement), s₂ = 5, s₃ = 20, s₄ = 1.6.
S = 1 / (p₁/s₁ + p₂/s₂ + p₃/s₃ + p₄/s₄)
= 1 / (0.11/1 + 0.18/5 + 0.23/20 + 0.48/1.6)
= 1 / (0.11 + 0.036 + 0.0115 + 0.30)
= 1 / 0.4575
≈ 2.19×

Notice: The 5× and 20× speedups on parts 2 and 3 have little impact because part 4 (48% of
execution time) is only sped up by 1.6×.

Example 4: Parallel Computing with 20% Sequential

p = 0.80, N = 4 processors
S = 1 / ((1 - 0.80) + (0.80 / 4))
= 1 / (0.20 + 0.20)
= 1 / 0.40
= 2.5×

With 4 processors, you get only 2.5× speedup because 20% of the program is sequential.

Example 5: With 5 Processors, 20% Parallelizable

p = 0.20, N = 5
S = 1 / ((1 - 0.20) + (0.20 / 5))
= 1 / (0.80 + 0.04)
= 1 / 0.84
≈ 1.19×

Only 19% improvement — the 80% sequential part is the overwhelming bottleneck.

8.6 Key Implications

Implication Explanation
Sequential bottleneck The non-parallelizable portion (1-p) limits
maximum speedup regardless of processors
added
Diminishing returns Each additional processor provides less marginal
speedup
Focus optimization Greatest improvements come from reducing the
largest sequential portions
Upper bound Amdahl's Law provides a clear upper bound on
performance

8.7 Limitations of Amdahl's Law

1. Assumes fixed problem size — in practice, as more resources become available,
programmers often solve larger problems.
2. Assumes identical processors — not true in heterogeneous systems.
3. Ignores real-world factors — communication overhead, synchronization costs, load
imbalancing, memory bandwidth, and I/O bandwidth.
Chapter 9: Gustafson's Law — Scaled Speedup
9.1 Introduction
Gustafson's Law, proposed by John L. Gustafson and Edwin H. Barsis in 1988 (published in
"Reevaluating Amdahl's Law" in Communications of the ACM), provides an alternative and more
optimistic perspective on parallel speedup.

9.2 The Key Insight

While Amdahl's Law assumes a fixed problem size and asks "how fast can we solve this problem
with N processors?", Gustafson's Law assumes that problem sizes grow with available computing
resources and asks "how large a problem can we solve in the same time with N processors?"
Gustafson observed from real workloads that:
• The time for the serial part typically does not grow as the problem and system scale.
• Programmers tend to increase problem size to fully exploit available computing power.

9.3 The Formula

S(N) = N - α(N - 1)

Or equivalently:
S(N) = α + (1 - α) × N

Where:
• S(N) = Scaled speedup
• N = Number of processors
• α = Fraction of time spent on the serial part (on the parallel system)
• (1 - α) = Fraction of time spent on the parallel part

9.4 Derivation
Let the total execution time on the parallel system be normalized to 1:
• Serial time: α

• Parallel time: (1 - α)

• Where: α + (1 - α) = 1

If we were to run this same computation on a single processor:

• Serial part still takes: α

• Parallel part now takes: N × (1 - α) (because one processor does all the parallel work)

• Total serial time: α + N × (1 - α)

Speedup = Serial time / Parallel time:

S(N) = (α + N × (1 - α)) / 1
= α + N - Nα
= N - α(N - 1)

9.5 Comparison with Amdahl's Law

Aspect Amdahl's Law Gustafson's Law
Assumption Fixed problem size Problem size scales with
processors
Formula S = 1 / ((1-p) + p/N) S = N - α(N-1)
Outlook Pessimistic — diminishing Optimistic — near-linear
returns speedup
Focus Sequential bottleneck limits Parallel portion scales to
speedup maintain efficiency
Applicability Fixed workloads Scalable workloads (most
scientific computing)
Scaling behavior Logarithmic (rapidly Linear with N
diminishing)
Proposed by Gene Amdahl (1967) John L. Gustafson (1988)

9.6 Practical Example

Amdahl's perspective: A computer boots in 1 minute. Even with infinite parallelism, if any part of
the boot process is inherently sequential, you cannot reduce the boot time below that sequential
portion.
Gustafson's perspective: A fourfold increase in computing power would lead to increased
expectations — the boot still takes 1 minute, but the new system includes more features, better
graphics, and more functionality. The time is constant; the problem size grew.

9.7 Limitations of Gustafson's Law

1. Assumes that the workload can be scaled proportionally — not all problems have larger
versions.
2. Algorithms with nonlinear runtimes (e.g., O(n²)) may not benefit proportionally from
increased parallelism.
3. Overlooks the impact of the serial portion on overall performance when the problem cannot
grow.

Chapter 10: Amdahl vs. Gustafson — A Detailed Comparison

10.1 Conceptual Difference
The fundamental difference lies in the workload assumption:
 • Amdahl: The workload is fixed. Adding processors reduces execution time but with
diminishing returns.
Fixed workload
┌─────────────────────────────┐
│ Processor 1: ████████████ │ Total time: 12ms
└─────────────────────────────┘

Fixed workload (3 processors)

┌──────────┐
│ P1: ████ │
│ P2: ████ │ Total time: 4ms
│ P3: ████ │
└──────────┘

• Gustafson: The workload is variable. Adding processors allows solving a proportionally

larger problem in the same time.
Variable workload (1 processor)
┌─────────────────────────────┐
│ Processor 1: ████████████ │ Total time: 12ms
└─────────────────────────────┘

Variable workload (3 processors)

┌──────────────────────────────┐
│ P1: ████████ │
│ P2: ████████ │ Total time: 12ms
│ P3: ████████ │ (but solving 3× larger problem)
└──────────────────────────────┘

10.2 Neither Law is "Wrong"

Gustafson's Law does not overturn Amdahl's Law. They answer different questions:
• Amdahl: "What is the maximum speedup for a fixed problem?"
• Gustafson: "How much more work can we do in the same time with more processors?"
Both are valid in their respective contexts. The correct law to apply depends on the nature of the
workload.

10.3 When to Use Each

Scenario Use Amdahl's Law Use Gustafson's Law
Fixed workload that cannot ✓
grow
Real-time systems with fixed ✓
deadlines and fixed problems
Large non-parallelizable ✓ (highlights bottleneck)
portion
Scalable scientific simulations ✓
Data-intensive problems where ✓
dataset grows
Evaluating resource utilization ✓
Scenario Use Amdahl's Law Use Gustafson's Law
at scale

Part IV: Pipelining

Chapter 11: Pipeline Fundamentals and Performance Metrics

11.1 What is Pipelining?
Pipelining is a technique where a task is divided into a sequence of subtasks, each performed by a
dedicated functional unit (stage). All stages operate simultaneously on different tasks, like an
assembly line. While one instruction is being executed, the next one is being decoded, and the one
after that is being fetched.

11.2 Pipeline Stages

A common instruction pipeline divides execution into stages:

Stage Abbreviation Function

Instruction Fetch IF / F Fetch instruction from
memory/cache
Instruction Decode ID / D Decode the instruction,
determine operands
Operand Fetch OF Fetch operands from
registers/memory
Instruction Execute IE / E Perform the operation (ALU)
Store Results IS / S / W Write results back to
registers/memory

11.3 Pipelining vs. Sequential Processing

Consider processing 3 instructions with 4 stages (F, D, E, W):
Sequential (no pipelining):
Time: 1 2 3 4 5 6 7 8 9 10 11 12
I₁: F D E W
I₂: F D E W
I₃: F D E W
Total: 12 time units

Pipelined:
Time: 1 2 3 4 5 6
I₁: F D E W
I₂: F D E W
I₃: F D E W
Total: 6 time units (50% savings!)

11.4 Performance Metrics

For a pipeline with n stages processing m tasks, where each stage takes time t:
Total pipeline time = (n + m - 1) × t time units

Speed-up S(n)
m × n × t m × n
S(n) = ───────────── = ─────────
(n + m - 1) × t n + m - 1

As m → ∞: S(n) → n

An n-stage pipeline can theoretically achieve an n-fold speedup.

Throughput U(n)
m
U(n) = ─────────────
(n + m - 1) × t

As m → ∞: U(n) → 1/t

One task per time unit in the limit.

Efficiency E(n)
S(n) m
E(n) = ────── = ─────────
n n + m - 1

As m → ∞: E(n) → 1

Perfect efficiency (100%) is approached as the number of tasks grows.

11.5 Gantt Chart Example

Processing 10 instructions on a 4-stage pipeline:
Stage 1 2 3 4 5 6 7 8 9 10 11 12 13
U₁: I₁ I₂ I₃ I₄ I₅ I₆ I₇ I₈ I₉ I₁₀
U₂: I₁ I₂ I₃ I₄ I₅ I₆ I₇ I₈ I₉ I₁₀
U₃: I₁ I₂ I₃ I₄ I₅ I₆ I₇ I₈ I₉ I₁₀
U₄: I₁ I₂ I₃ I₄ I₅ I₆ I₇ I₈ I₉ I₁₀

Total: n + m - 1 = 4 + 10 - 1 = 13 time units (vs. 40 sequential).

Chapter 12: Pipeline Hazards — Instruction and Data
Dependencies
12.1 What is a Pipeline Hazard?
A pipeline hazard (or pipeline stall / pipeline bubble) occurs when normal pipeline operation is
disrupted, causing stages to go idle and increasing total execution time. There are three types:
1. Structural hazards — hardware resource conflicts (e.g., cache miss)
2. Control hazards — instruction dependency (branch instructions)
3. Data hazards — data dependency between instructions

12.2 Structural Hazards (Cache Misses)

If an instruction fetch encounters a cache miss, requiring extra time units to fetch from main
memory, the pipeline stalls:
Stage 1 2 3 4 5 6 7 ... 16
IF: I₁ I₂ -- -- -- I₃ I₄ ...
ID: I₁ I₂ -- -- -- I₃ ...
IE: I₁ -- I₂ -- -- ...
IS: I₁ -- I₂ -- ...

The -- represents idle stages (the bubble). A 3-cycle cache miss turns 13 time units into 16 time
units for 10 instructions.

12.3 Control Hazards (Instruction Dependency)

A control hazard occurs with branch instructions. The next instruction to fetch depends on the
result of executing the branch instruction, which is not known until the branch completes.
Example: Instruction I₄ is a conditional branch. The pipeline must stall after fetching I₄ until the
branch result is known:
Stage 1 2 3 4 5 6 7 8 9 10 11 ... 16
IF: I₁ I₂ I₃ I₄ -- -- -- I₅ I₆ I₇ I₈ ...
ID: I₁ I₂ I₃ I₄ -- -- -- I₅ I₆ I₇ ...
IE: I₁ I₂ I₃ I₄ -- -- -- I₅ I₆ ...
IS: I₁ I₂ I₃ I₄ -- -- -- I₅ ...

Three bubble cycles are introduced, turning 13 into 16 time units.

12.4 Data Hazards

Data hazards occur when an instruction depends on the result of a preceding instruction that hasn't
completed yet. There are four possible cases based on read/write ordering:

Type Notation Condition Causes Stall?

Read After Write True dependency I₂ reads a register that Yes — I₂ must wait for
(RAW) (flow) I₁ writes I₁'s result
Write After Write Output dependency I₂ writes to a register Yes — write order
(WAW) that I₁ also writes must be preserved
Type Notation Condition Causes Stall?
Write After Read Anti-dependency I₂ writes to a register Yes — I₂ must not
(WAR) that I₁ reads overwrite before I₁
reads
Read After Read Input dependency Both read the same No — reads don't
(RAR) register modify data

RAW Example (Read-After-Write)

I₁: ADD R1, R2, R3 ; R3 ← R1 + R2
I₂: SUB R3, 1, R4 ; R4 ← R3 - 1 (needs R3 from I₁!)

On a 5-stage pipeline (IF, ID, OF, IE, IS):

Stage k k+1 k+2 k+3 k+4 k+5 k+6
IF: I₁ I₂
ID: I₁ I₂
OF: I₁ -- -- I₂ ← I₂ waits for R3
IE: I₁ I₂
IS: I₁ I₂

I₂ cannot fetch its operand (R3) during k+3 because I₁ hasn't stored the result yet (stored at end of
k+4). I₂ must wait until k+5.

WAW Example (Write-After-Write)

I₁: ADD R1, R2, R3 ; R3 ← R1 + R2
I₂: SL R3 ; R3 ← ShiftLeft(R3)

Both instructions write to R3. The pipeline must ensure I₁ writes before I₂.

12.5 Comprehensive Data Dependency Example

Consider this instruction sequence on a 5-stage pipeline:
I₁: Load 21, R1 ; R1 ← 21
I₂: Load 5, R2 ; R2 ← 5
I₃: Sub R2, 1, R2 ; R2 ← R2 - 1 (depends on I₂: RAW + WAW)
I₄: Add R1, R2, R3 ; R3 ← R1 + R2 (depends on I₁: RAW, I₃: RAW)
I₅: Add R4, R5, R6 ; R6 ← R4 + R5 (independent)
I₆: SL R3 ; R3 ← SL(R3) (depends on I₄: RAW + WAW)
I₇: Add R6, R4, R7 ; R7 ← R6 + R4 (depends on I₅: RAW)

The dependency table:

Instructions Dependency Type

I₃ ← I₂ RAW and WAW (both use R2)
I₄ ← I₁ RAW (R1)
I₄ ← I₃ RAW (R2)
I₆ ← I₄ RAW and WAW (R3)
I₇ ← I₅ RAW (R6)
Result: 16 time units required for 7 instructions.
Speed-up: S(5) = (7 × 5) / 16 = 2.19 Throughput: U(5) = 7 / 16 = 0.44 tasks
per time unit

Chapter 13: Hazard Resolution Techniques

13.1 Preventing Wrong Instructions/Operands
NOP Insertion
Insert NOP (No Operation) instructions after a branch or data-dependent instruction to fill the
pipeline until the correct value is available.
For instruction dependency (branch): Insert (n - 1) NOPs after the branch instruction, where n
is the number of pipeline stages.
For data dependency: Insert NOPs between dependent instructions to delay the dependent
instruction until the result is stored.
Example (data dependency on 5-stage pipeline):
ADD R1, R2, R3 ; R3 ← R1 + R2
NOP
NOP
SUB R3, 1, R4 ; R4 ← R3 - 1 (now R3 is available)
MOV R5, R6 ; R6 ← R5

Drawback: NOPs waste pipeline cycles, reducing throughput.

13.2 Reducing Stalls for Unconditional Branches

Instruction Reordering
A "smart" compiler rearranges instructions so that useful work is done during what would
otherwise be stall cycles. The branch instruction is moved earlier in the sequence.
Before reordering: I₁, I₂, I₃, I₄(branch→Ij), I₅, ..., Ij After reordering:
I₁, I₄(branch→Ij), I₂, I₃, I₅, ..., Ij
Constraint: The swapped instructions must have no data or instruction dependencies among
them.

Dedicated Branch Hardware

The fetch unit has a dedicated hardware unit that recognizes branch instructions and computes
the target address in parallel with other work, ideally with zero additional time units.

Branch Folding (Precomputing + Reordering)

Combines instruction reordering with dedicated hardware. The hardware computes the target
address concurrently with the execution of reordered instructions that fill the delay slot.
Instruction Prefetching
Instructions are fetched ahead of time and stored in an instruction queue. When a branch stalls the
pipeline, prefetched instructions from the queue can be used. A dispatch unit provides the
appropriate instruction. This technique is called branch folding.

13.3 Reducing Stalls for Conditional Branches

Delayed Branch
The instruction(s) following a conditional branch (branch delay slot) are filled with useful
instructions that can execute regardless of the branch outcome.
Example (2-stage pipeline, loop with R₂ = 3):
; Original:
Again: Load 5, R1 ; R1 ← 5
Sub R2 ; R2 ← R2 - 1
Bnn Again ; Branch if Not Negative
Add R4, R5, R3 ; R3 ← R4 + R5

; Reordered for delayed branch:

Again: Sub R2 ; R2 ← R2 - 1
Load 5, R1 ; R1 ← 5 (fills the delay slot!)
Bnn Again ; Branch if Not Negative
Add R4, R5, R3

Studies show "smart" compilers can fill branch delay slots more than 80% of the time.

Branch Prediction
Static prediction (compile-time):
• Predict always taken or always not taken.
• Simple: If the branch outcome is random, ~50% accuracy.
• Rule of thumb: Backward branches (loops) → predict taken; Forward branches → predict
not taken.
Dynamic prediction (run-time): Uses a branch history table to record past outcomes of each
branch instruction.
Two-state algorithm: States are "Likely Taken" (LTK) and "Likely Not Taken" (LNK). The state
transitions based on actual branch outcomes.
Four-state algorithm (used in ARM 11): States are Strongly Taken, Weakly Taken, Weakly Not
Taken, Strongly Not Taken. Uses a 2-bit saturating counter:
Strongly Not Taken (00) ↔ Weakly Not Taken (01) ↔ Weakly Taken (10) ↔ Strongly
Taken (11)

The counter increments on taken branches and decrements on not-taken.

ARM 11: Uses a 64-entry Branch Target Address Cache (BTAC). Dynamic prediction first; falls
back to static prediction if no record exists. ~80% prediction accuracy. Each correct prediction
saves ~5 clock cycles.
UltraSPARC III: Uses a 16K-entry branch history table with the gshare algorithm (XOR of
branch address with global branch history register). Achieves 95% prediction accuracy. Uses a
Branch Miss Queue (BMQ) to buffer fall-through instructions during prediction, reducing
misprediction penalty to 2 cycles.

13.4 Reducing Data Dependency Stalls

Hardware Operand Forwarding
The result of an ALU operation is made available to the next instruction's input in the same cycle it
is stored, via a feedback path (bypass/forwarding path) from the ALU output back to the ALU
input.
Without forwarding:
IF → ID → OF → IE → IS
↑ waits for IS to complete before OF can read

With forwarding:
IF → ID → OF → IE → IS
↑ result forwarded directly from IE

This reduces or eliminates the stall caused by RAW dependencies.

Cost: Requires additional hardware (multiplexers, bypass paths) and careful control signal timing.

Software Operand Forwarding

The compiler performs data dependency analysis to detect patterns where results can be reused
without waiting. Three patterns:
Store-Fetch: A result stored to memory is immediately needed by the next instruction.
; Before: ; After (forwarded):
Store R2, (R3) Store R2, (R3)
Load (R3), R4 Move R2, R4

Fetch-Fetch: Two instructions read from the same memory location.

; Before: ; After (forwarded):
Load (R3), R2 Load (R3), R2
Load (R3), R4 Move R2, R4

Store-Store: Two instructions write to the same location. If the first write's result isn't needed
elsewhere, eliminate it.
; Before: ; After:
Store R2, (R3) Store R4, (R3)
Store R4, (R3) ; First store eliminated
Chapter 14: Advanced Pipelines and Instruction-Level
Parallelism
14.1 Real-World Pipeline Processors
ARM 1026EJ-S (6-stage pipeline)
1. Fetch: Instruction cache access + branch prediction
2. Issue: Initial instruction decoding
3. Decode: Final decode, register read, forwarding, interlock resolution
4. Execute: Address calculation, ALU operations, shift, multiply (stage 1), condition code
check
5. Memory: Data cache access, multiply (stage 2)
6. Write: Register write, instruction retirement
Features: 64-bit fetch per cycle, 3-instruction prefetch buffer, predicted branches don't flush the
buffer. Misprediction penalty: 3 cycles.

UltraSPARC III (14-stage pipeline)

Stages: Address Generation → Instruction Prefetch → Instruction Fetch → Branch Target
Calculation → Instruction Decode → Instruction Steer → Register File Read → Integer Execution
→ Data Cache Access → Memory Bypass → Working Register Write → Pipe Extend → Trap →
Done.

14.2 Instruction-Level Parallelism (ILP)

ILP uses Multiple Issue Processors (MIP) with multiple pipelined datapaths. Each pipeline can
issue and execute one instruction per cycle, achieving CPI < 1 (cycles per instruction less than
one).
Two approaches:

Approach Scheduling Responsibility

VLIW (Very Long Static (compile-time) Compiler bundles independent
Instruction Word) operations into a single wide
instruction word
Superscalar Dynamic (run-time) Hardware fetches, decodes, and
issues multiple instructions per
cycle, checking dependencies
dynamically

14.3 Superscalar Architecture (SPA)

A superscalar processor can:
1. Fetch multiple instructions simultaneously
 2. Decode them (predecoding identifies branches; actual decoding determines operations,
operands, destinations)
3. Issue — identify which dispatched instructions can start execution
4. Execute — multiple execution units work in parallel
5. Commit — write results in original program order
The critical bottleneck is dependency analysis, whose complexity grows quadratically with
instruction word size. In practice, a degree of parallelism higher than 4 becomes impractical for
superscalar designs.

Part V: Dependence Analysis

Chapter 15: Control Dependencies

15.1 Definition
A control dependency exists when whether or not a statement executes depends on the outcome of
a preceding conditional statement.
Formal definition: Statement S₂ is control dependent on S₁ if and only if:
1. There exists a path from S₁ to S₂ such that every statement S ≠ S₂ on this path is post-
dominated by S₂.
2. S₁ does not post-dominate S₂ — i.e., there exists an execution path from S₁ to program end
that does not go through S₂.

15.2 Example
S1: if (x > 2) goto L1
S2: y := 3 ← Control dependent on S1
S3: L1: z := y + 1 ← NOT control dependent on S1

• S₂ executes only if the predicate in S₁ is false. Therefore, S₂ is control dependent on S₁.

• S₃ executes regardless of S₁'s outcome (it's the target of the goto and also follows S₂).
Therefore, S₃ is not control dependent on S₁.

15.3 Another Example

S1: if (a == b)
S2: a = a + b ← Control dependent on S1
S3: b = a + b ← NOT control dependent on S1

S₂ is control dependent on S₁ because S₂ only executes when a == b. S₃ always executes,

regardless of S₁'s outcome.
15.4 Connection to Post-Dominance
Control dependencies are the dominance frontier in the reverse graph of the control-flow graph
(CFG). To construct them:
1. Build the post-dominator tree from the CFG.
2. Compute the post-dominance frontier using the algorithm:
for each X in bottom-up traversal of post-dominator tree:
PostDominanceFrontier(X) ← ∅
for each Y in Predecessors(X):
if immediatePostDominator(Y) ≠ X:
PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
for each Z in Children(X):
for each Y in PostDominanceFrontier(Z):
if immediatePostDominator(Y) ≠ X:
PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}

1. Reverse the post-dominance frontier map to obtain the control dependence graph.

15.5 Importance
Understanding control dependencies is essential for:
• Compiler optimizations — determining which code can be safely moved or eliminated
• Parallelization — identifying independent code blocks that can execute concurrently
• Dead code elimination — removing code that can never affect program output

Chapter 16: Data Dependencies and Bernstein's Conditions

16.1 Definition
A data dependency exists between two statements when they access or modify the same memory
resource (variable, register, memory location).

16.2 Bernstein's Conditions

Named after Arthur J. Bernstein (1966), these conditions formally define when a data dependency
exists between statements S₁ and S₂ (where S₁ precedes S₂):
A dependency exists if any of these conditions hold:
1. O(S₁) ∩ I(S₂) ≠ ∅ — S₁ writes something that S₂ reads (flow/true dependency)

2. I(S₁) ∩ O(S₂) ≠ ∅ — S₁ reads something that S₂ writes (anti-dependency)

3. O(S₁) ∩ O(S₂) ≠ ∅ — Both write to the same location (output dependency)

Where:
• I(S) = set of memory locations read by statement S

• O(S) = set of memory locations written by statement S

If none of these conditions hold, the statements are independent and can be safely reordered or
executed in parallel.

16.3 Types of Data Dependencies

Flow Dependency (True Dependency / RAW — Read After Write)
S₂ reads a value that S₁ writes.
S1: x := 10
S2: y := x + c ← RAW: S₂ reads x after S₁ writes it

This is a true dependency — it cannot be removed by renaming. The data genuinely flows from S₁
to S₂.
Chaining example:
1. A = 3
2. B = A ← truly dependent on 1
3. C = B ← truly dependent on 2 (and transitively on 1)

No instruction-level parallelism is possible here.

Anti-Dependency (WAR — Write After Read)

S₂ writes a value that S₁ reads. The instructions cannot be reordered because S₂ would overwrite
the value before S₁ reads it.
S1: x := y + c ← reads y
S2: y := 10 ← writes y (must not happen before S₁ reads y)

Anti-dependencies are name dependencies — they can be removed by variable renaming:

S1: x := y + c
N: y2 := y ← copy before overwrite
S2: y := 10
; Now S1 uses y (original), S2 writes y — no conflict

Output Dependency (WAW — Write After Write)

Both S₁ and S₂ write to the same location. The final value depends on execution order.
S1: x := 10
S2: x := 20 ← Must execute after S₁ for correct final value

Also a name dependency — removable by renaming:

S1: x1 := 10 ← renamed
S2: x := 20 ← final value correctly in x

Input Dependency (RAR — Read After Read)

Both S₁ and S₂ read the same location.
S1: y := x + 3
S2: z := x + 5 ← Both read x

This is NOT a hazard — reads do not modify data, so reordering is safe.

16.4 Summary Table
Dependency S₁ Action S₂ Action Hazard? Removable by
Type Renaming?
Flow (RAW) Write Read Yes No (true
dependency)
Anti (WAR) Read Write Yes Yes (name
dependency)
Output (WAW) Write Write Yes Yes (name
dependency)
Input (RAR) Read Read No N/A

16.5 Implications in Computing

Instruction pipelining: RAW dependencies are the most critical; resolved by stalling or operand
forwarding.
Out-of-order execution: Modern processors execute instructions out of order for performance.
Name dependencies (WAR, WAW) are resolved by register renaming or scoreboarding. Memory
dependencies are handled by memory disambiguation.
Compiler optimizations: Compilers must respect data dependencies when performing:
• Instruction scheduling — reorder for better performance
• Loop transformations — unrolling, fusion, tiling
• Code motion — moving code to optimize execution
Loop dependence analysis: Computing dependencies within loops is significantly more complex
and is handled by a specialized framework.

Part VI: The PRAM Model

Chapter 17: PRAM Architecture and Memory Models

17.1 From RAM to PRAM
The RAM (Random Access Machine) is the standard theoretical model for sequential
computation:
• Single computation unit executing a program
• Unbounded memory cells, each holding an arbitrary integer
• Operations: data movement, comparisons, branching, arithmetic
• Each operation takes one time unit (unit-cost model)
 • Time complexity = number of instructions executed
• Space complexity = number of memory cells accessed
The PRAM (Parallel Random Access Machine) extends the RAM model to parallel computation.

17.2 PRAM Definition

A PRAM consists of:
1. p processors (P₁, P₂, ..., Pₚ), each with its own local memory (registers)
2. A single shared global memory — a sequence of words, each holding an arbitrary integer
3. Each processor has a unique identifier (PID): 1 ≤ i ≤ p
4. All processors operate synchronously — they share a common clock
5. Memory access takes constant time — any processor can access any memory location in
O(1)
6. A read-only input tape and write-only output tape

17.3 Execution Model

The PRAM is a synchronous MIMD shared-address-space parallel computer. Despite being
MIMD, it operates in SIMD fashion for analysis: a single program is executed, but each processor
may execute different instructions based on its PID.
Each instruction executes in a three-phase cycle:

Phase Action
Read Up to p processors simultaneously read one
value each from shared memory into local
registers
Compute Each processor performs a fixed number of
arithmetic/logic operations on its local data
Write Up to p processors simultaneously write one
value each from local registers to shared
memory

All processors execute their three-phase cycles synchronously.

17.4 Processor Activity Control

Each processor has an active flag. Only active processors participate in instruction execution.
Inactive processors skip instructions except those that reset the flag. This allows conditional
execution by subsets of processors:
if (PID is even) then
// Only even-numbered processors execute this block
17.5 Memory Contention Models
The central challenge in PRAM is memory contention — what happens when multiple processors
simultaneously access the same memory location?
PRAM defines four variants based on how simultaneous access is handled:

Model Concurrent Read? Concurrent Write? Description

EREW No No Most restrictive. No
two processors may
access the same
location
simultaneously. All
correct programs must
ensure exclusive
access.
CREW Yes No Multiple processors can
read the same location
simultaneously (all get
the same value), but
only one can write at a
time.
ERCW No Yes Only one processor can
read, but multiple can
write simultaneously.
Rarely studied
independently.
CRCW Yes Yes Most powerful.
Multiple processors can
both read and write the
same location
concurrently.

17.6 CRCW Sub-Variants

When multiple processors simultaneously write to the same location, a conflict resolution policy is
needed:

Sub-variant Resolution Rule

Common CRCW All writing processors must write the same
value. If they disagree, the result is
undefined/error.
Arbitrary CRCW An arbitrarily chosen value from the
competing writes is stored.
Priority CRCW The processor with the lowest PID (highest
priority) wins. Its value is stored.
Combining (SUM) CRCW The stored value is a combination of all written
values (e.g., sum, max).
17.7 Why Study PRAM?
1. Well-developed theory: Extensive literature on PRAM algorithm design and complexity.
2. Baseline model: PRAM focuses exclusively on concurrency, ignoring synchronization and
communication overhead. If you can't get a good algorithm on PRAM, you can't get one in
the real world.
3. Explicit model: Operations at each step and scheduling on processors must be specified.
4. Robust design paradigm: Many algorithms for other models (e.g., network models) can be
derived from PRAM algorithms.

17.8 PRAM Model Hierarchy

The models form a hierarchy in terms of power:
EREW ⊂ CREW ⊂ ERCW ⊂ CRCW

• Any algorithm that works on EREW also works on CREW, ERCW, and CRCW.
• They differ not in expressive power but in complexity-theoretic terms — more powerful
models may solve problems faster (with fewer steps).

Chapter 18: PRAM Algorithms — Parallel Binary Search

18.1 Problem Setup
Given: A sorted array A of size n and a search key K. Task: Find K in the array. Sequential
complexity: O(log n) comparisons.

18.2 CREW PRAM Implementation

Algorithm Overview
Instead of checking a single midpoint (as in sequential binary search), we use P processors to
check P probe positions simultaneously, shrinking the search range by a factor of P at each step
instead of 2.

Detailed Algorithm
Parallel Binary Search (CREW PRAM):

1. Initialize: low = 0, high = n - 1, P = number of processors

2. While (high - low + 1) > P:

a. All processors read current low and high (CONCURRENT READ)

b. For each processor i (0 ≤ i ≤ P-1) in parallel:

- Compute probe position:
probe_i = low + i × (high - low) / (P - 1)
- Read A[probe_i] concurrently
- Compare A[probe_i] with K
 c. If any processor finds K, return its index

d. Otherwise, determine new [low, high] based on comparisons:

Find adjacent probes where A[probe_j] < K < A[probe_{j+1}]
Set: low = probe_j + 1, high = probe_{j+1} - 1

3. When (high - low + 1) ≤ P:

Perform sequential binary search on the remaining small range.

Why CREW?
• Concurrent Read: All processors need to read low and high simultaneously. They also
read their respective A[probe_i] values concurrently. CREW allows this.

• Exclusive Write: Only one processor updates low and high after each iteration.

18.3 Worked Example

Setup: Array size n = 16, low = 0, high = 15, P = 4 processors, K = 26.
Array: A = [2, 5, 7, 9, 11, 15, 18, 20, 22, 24, 27, 30, 33, 35, 38, 40]
Iteration 1:
• Check: (15 - 0 + 1) = 16 > 4 ✓ (enter loop)

• Probe positions: probe₀ = 0, probe₁ = 5, probe₂ = 10, probe₃ = 15

Processor Probe Index Value Comparison with

K=26
P₀ 0 A[0] = 2 2 < 26
P₁ 5 A[5] = 15 15 < 26
P₂ 10 A[10] = 27 27 > 26
P₃ 15 A[15] = 40 40 > 26

Result: A[5] < K < A[10], so new range: low = 6, high = 9.

Iteration 2:
• Check: (9 - 6 + 1) = 4 > 4 ✗ (False — loop exits)

• Perform sequential binary search on [6, 9]:

• mid = 7, A[7] = 20 < 26 → search [8, 9]
• mid = 8, A[8] = 22 < 26 → search [9, 9]
• mid = 9, A[9] = 24 < 26 → K not found

18.4 Complexity Analysis

• Sequential binary search: O(log n) comparisons
• Parallel binary search with P processors: O(log n / log P) parallel steps
• Each step reduces the search space by a factor of ~P instead of 2
 • log_P(n) = log(n) / log(P)

Part VII: Parallel Programming Models

Chapter 19: The Message Passing Model and MPI

19.1 The Message Passing Model
The message passing model is based on a set of processes, each with private data structures.
Processes communicate by exchanging messages using explicit send and receive operations.
Characteristics:
• Natural fit for distributed memory machines (but also works on shared memory)
• The domain decomposition is implemented by developing code describing local
computations and local data structures for a single process
• Global arrays must be split up — only the local part is allocated in each process
• Access to remote data requires explicit communication: allocate temporary variables,
construct messages, and transmit them

19.2 MPI — Message Passing Interface

MPI was developed between 1993 and 1997 as a community standard defining calling interfaces
for communication and synchronization functions. It provides bindings for Fortran 77, Fortran 90,
C, and C++.
MPI includes routines for:
• Point-to-point communication (send/receive)
• Collective communication (broadcast, gather, scatter, reduce)
• One-sided communication (remote memory access)
• Parallel I/O
• Dynamic task creation

19.3 The Six Essential MPI Functions

Although MPI has 320+ functions, realistic programs can be built with just six:

Function Purpose
MPI_Init Initializes the MPI library. Must be called before
any other MPI routines.
MPI_Finalize Frees resources used by MPI. Called at program
end.
Function Purpose
MPI_Comm_size Returns the number of processes in the parallel
program.
MPI_Comm_rank Returns the unique process identifier (rank) of
the calling process.
MPI_Send Blocking send — transfers a message to a target
process. Terminates when the buffer can be
reused.
MPI_Recv Blocking receive — receives a message.
Terminates when the message is copied into the
receive buffer.

19.4 MPI Communicators

All MPI communication depends on a communicator, which consists of:
1. Process group: Processes numbered 0 to (size - 1)
2. Communication context: Identifies messages — a message must match both the tag and
the communicator
The default communicator including all processes is MPI_COMM_WORLD.

The communication context is crucial for building parallel libraries — messages sent inside a
library (using a library-specific communicator) won't interfere with messages outside.

19.5 MPI Collective Operations

Operation Description
MPI_Barrier Synchronizes all processes. None can proceed
until all have reached the barrier.
MPI_Bcast Distributes the same data from one root process
to all others.
MPI_Scatter Distributes different data from a root process to
each process in the group.
MPI_Gather Collects data from all processes at a root
process.
MPI_Reduce Performs a global operation (e.g., sum, max) on
data from all processes. The result is delivered
to a single target process.

19.6 MPI I/O

Three approaches to I/O in parallel programs:

Approach Description Pros Cons

Sequential I/O One node gathers data Simple Scalability issues
Approach Description Pros Cons
and writes; reads and
scatters.
Private I/O Each node accesses its High performance, no Must manage many
own files. synchronization needed files; split/merge for
input/output
Parallel I/O All processes access No individual files; More complex to
the same file, good performance implement
reading/writing only
relevant parts.

MPI Parallel I/O uses the view concept: each process defines a pattern of data elements to
read/write, allowing the library to optimize access. Supports both blocking and non-blocking
operations.

19.7 MPI Remote Memory Access (One-Sided Communication)

RMA operations allow accessing another process's address space without the other process's
participation.
Key concepts:
• Window: Each process defines a memory region accessible to other processes (collective
operation).
• Put/Get: Write to / read from a remote process's window.
• MPI_Win_fence: Collective synchronization ensuring all RMA operations before the fence
complete before any after the fence begin.
• Also supports General Active Target Synchronization and locks for fine-grained control.
Advantages: Lower protocol overhead than send/receive; no polling or global communication
needed for setup.

19.8 MPI Example — Computing π

Using numerical integration (midpoint rule): π = ∫₀¹ 4/(1+x²) dx
program pi_mpi
implicit none
include 'mpif.h'
integer :: i, n, ierr, myrank, numprocs
double precision :: f, x, sum, pi, h, mypi

call MPI_Init(ierr)
call MPI_Comm_rank(MPI_COMM_WORLD, myrank, ierr)
call MPI_Comm_size(MPI_COMM_WORLD, numprocs, ierr)

if (myrank == 0) then
write(*,*) "number of intervals?"
read(*,*) n
end if

call MPI_Bcast(n, 1, MPI_INTEGER, 0, MPI_COMM_WORLD, ierr)

 h = 1.0d0 / n
sum = 0.0d0
do i = myrank + 1, n, numprocs ! Each process gets every numprocs-th
iteration
x = (i - 0.5d0) * h
sum = sum + (4.d0 / (1.d0 + x*x))
end do
mypi = h * sum

call MPI_Reduce(mypi, pi, 1, MPI_DOUBLE_PRECISION, &

MPI_SUM, 0, MPI_COMM_WORLD, ierr)

if (myrank == 0) then
write(*, fmt="(A, F16.12)") "Value of pi is ", pi
endif

call MPI_Finalize(ierr)
end program

Key points:
• Lines 7–9: Initialize MPI, get rank and size
• Lines 11–14: Only rank 0 reads input
• Line 16: Broadcast n to all processes
• Line 20: Each process computes a cyclic subset of iterations
• Lines 26–27: MPI_Reduce sums all local results into a global sum at rank 0

Chapter 20: The Shared Memory Model and OpenMP

20.1 The Shared Memory Model
Based on threads that share a global address space. Computation follows the fork-join pattern:
1. The master thread executes sequentially.
2. When parallel work is needed, the master forks a team of threads.
3. Threads execute the parallel region concurrently.
4. At the end of the parallel region, threads join back to the master.
Advantages over message passing:
• No explicit data distribution needed — threads use global indices
• Incremental parallelization — parallelize one loop at a time
• Sequential code still works (directives are treated as comments)
• Easier to change domain decomposition (change scheduling strategy)
Disadvantages:
• Only works on shared memory computers
 • Automatic parallelization is limited to compile-time-analyzable access patterns

20.2 OpenMP
OpenMP is a directive-based programming interface for shared memory. Available for Fortran, C,
and C++. Directives are special comments/pragmas interpreted by the compiler.

20.3 Key OpenMP Directives

Directive Purpose
!$OMP PARALLEL DO Declares a loop as parallel. Iterations are
distributed among threads.
!$OMP PARALLEL SECTIONS Starts a set of sections, each executed by a
different thread.
!$OMP PARALLEL Creates a parallel region. Code is executed
redundantly by all threads (use carefully).
!$OMP DO / FOR Work-sharing within a parallel region.
Distributes loop iterations. No implicit sync at
start, sync at end.
!$OMP SECTIONS Work-sharing for non-loop parallelism within a
parallel region.
!$OMP TASK (v3.0+) Dynamically specifies portions of code
that can run independently.

20.4 Scheduling Strategies

For PARALLEL DO / FOR:

Strategy Description
STATIC(chunk) Iterations distributed in blocks of chunk size.
Cyclic if chunk < total/threads.
DYNAMIC(chunk) Iterations distributed on a first-come-first-served
basis in blocks of chunk.
GUIDED(chunk) Blocks of exponentially decreasing size
assigned first-come-first-served. Minimum
block size = chunk.

20.5 Data Scoping

Scope Meaning
shared One copy exists, accessible by all threads.
Default for most variables.
private Each thread has its own copy. Uninitialized at
thread start.
Scope Meaning
firstprivate Private, but initialized with the value from
before the parallel region.
reduction Private copies are combined at the end using a
specified operator (+, *, max, min, etc.).

20.6 Synchronization
Construct Purpose
barrier All threads must reach this point before any can
proceed.
critical Only one thread can enter the section at a time.
Protects shared data from race conditions.
atomic Protects a single memory update (lighter-weight
than critical).

20.7 OpenMP Example — Computing π

program pi_omp
implicit none
integer :: i, n
double precision :: f, x, sum, pi, h

write(*,*) "number of intervals?"

read(*,*) n

h = 1.0d0 / n
sum = 0.0d0
!$omp parallel do private(i, x) reduction(+:sum)
do i = 1, n
x = (i - 0.5d0) * h
sum = sum + (4.d0 / (1.d0 + x*x))
end do
pi = h * sum

write(*, fmt="(A, F16.12)") "Value of pi is ", pi

end program

Key observations:
• The !$omp parallel do directive on line 11 is the only change from the sequential
version.
• private(i, x): Each thread gets its own copies of i and x.

• reduction(+:sum): Each thread computes a partial sum; OpenMP automatically

combines them.
• The OpenMP version is also a valid sequential program — the directive is treated as a
comment without an OpenMP compiler.
• The MPI version is almost twice as long because it must explicitly manage all aspects of
 parallelization.

Chapter 21: Distributed Communication Primitives

21.1 Send and Receive
The fundamental communication operations in distributed systems:
• Send(destination, buffer): Sends data from the user buffer to the specified destination
process.
• Receive(source, buffer): Receives data from the specified source into the user buffer.

21.2 Buffered vs. Unbuffered

Mode Behavior
Buffered Data is copied from user buffer → kernel buffer
→ network. For Receive, the kernel buffer
stores data that arrives before the Receive call.
Unbuffered Data is copied directly from user buffer →
network. Lower overhead but more restrictive.

21.3 Blocking vs. Non-Blocking

Mode Behavior
Blocking Control returns to the process only after the
operation completes. The process is suspended
until the message is delivered (Send) or received
(Receive).
Non-blocking Control returns immediately, even before the
operation completes. The process can continue
computing in parallel with communication. A
handle is returned for later status checking.

21.4 Synchronous vs. Asynchronous

Mode Behavior
Synchronous Both Send and Receive handshake. The Send
completes only after the receiver acknowledges.
The Receive completes when data is in the
receiver's buffer.
Asynchronous Send completes after data is copied out of the
sender's buffer (no acknowledgment required).
21.5 The Four Modes of Send
Mode Behavior
Blocking Synchronous Data copied to kernel buffer → sent over
network → waits for receiver acknowledgment
→ returns control
Non-blocking Synchronous Returns immediately after initiating copy to
kernel buffer. Returns a handle. Completion is
posted after receiver acknowledges.
Blocking Asynchronous Blocks until data is copied from user buffer to
kernel buffer. Returns after copy completes (no
wait for acknowledgment).
Non-blocking Asynchronous Returns immediately after initiating the copy to
kernel buffer. Returns a handle. Completion
posted when data is copied out of user buffer.

21.6 Modes of Receive

Mode Behavior
Blocking Receive Blocks until expected data arrives and is written
to the user buffer.
Non-blocking Receive Returns immediately with a handle. The kernel
registers the request. Completion is posted when
data arrives and is copied to the user buffer.

21.7 Checking Completion

For non-blocking operations, the process can:
1. Check the handle (test) — non-blocking check if the operation completed
2. Wait on the handle — blocking wait until the operation completes

21.8 Communication Network Models

Model Description
FIFO Each channel is a FIFO queue. Messages arrive
in the order they were sent.
Non-FIFO (N-FIFO) A channel acts like a set. Messages can arrive in
any order.
Causal Ordering (CO) Follows Lamport's "happens-before" relation.
Preserves causal relationships between
messages.

Relationship: CO ⊂ FIFO ⊂ N-FIFO (CO is the strongest ordering guarantee).

Part VIII: Practical Parallel Program Design

Chapter 22: Designing Parallel Programs

22.1 Can My Code Be Parallelized?
Ask these questions:
1. Does it have large loops that repeat the same operations?
2. Does it perform multiple independent tasks? If dependent, is the dependency weak?
3. Can dependencies or information sharing be overlapped with computation?
4. Do multiple tasks depend on the same data?
5. Does the order of operations matter? If so, how strict?

22.2 The SPMD Model

Single Program, Multiple Data (SPMD): The same program runs on all processors, but each
computes on different data based on its processor ID. Conditional statements (if) are used to
restrict operations to specific processors.

22.3 Partitioning Strategies

Domain Decomposition
The data associated with a problem is partitioned. Each parallel task works on a portion of the
data.
Methods:
• Block distribution: Contiguous chunks of data to each processor
• Cyclic distribution: Round-robin assignment of data elements
• Block-cyclic distribution: Combines both for better load balance and cache utilization

Functional Decomposition
The work (not data) is decomposed. Each parallel task performs a different operation. Useful when
different parts of the computation are independent.

22.4 Domain Decomposition Example — Gaussian Elimination

The algorithm eliminates entries below the main diagonal of a matrix. Design considerations:

Distribution Load Balance Communication Cache Efficiency

Block columns Poor (shrinking active Moderate (broadcast Poor
rectangle) current column)
Cyclic columns Good (only 1 column Moderate Poor
differs per step)
Distribution Load Balance Communication Cache Efficiency
Block-cyclic columns Good Moderate Good (can use BLAS
operations on blocks)
Row distribution Varies Different pattern Varies
(broadcast current row)

Choosing the right decomposition requires deep knowledge of the algorithm's data access patterns
and the ability to predict the resulting communication patterns.

22.5 Communication Design

Factor Description
Cost Resources spent packaging and transmitting
data; synchronization causes idle time
Latency vs. Bandwidth Latency = time for minimum message;
Bandwidth = data rate. Many small messages →
latency-dominated
Synchronous vs. Async Blocking (synchronous) stops work; non-
blocking (async) overlaps computation and
communication
Scope Point-to-point (between two tasks) vs. collective
(all tasks in a group)

Best practices:
• Send fewer, larger messages rather than many small ones
• Use non-blocking communication to overlap with computation
• Use collective operations where possible (optimized in MPI implementations)

22.6 Load Balancing

Goal: Distribute work equally so all tasks finish at approximately the same time. The slowest task
determines the overall completion time.
Techniques:
• Equal partitioning: For uniform work per data element, distribute data equally.
• Dynamic scheduling: For non-uniform work, use a task pool — when a processor finishes,
it requests more work from the pool.
• Guided self-scheduling: Decreasing block sizes (like OpenMP's GUIDED schedule).

22.7 I/O Considerations

Challenges:
• I/O operations are orders of magnitude slower than memory operations
 • I/O conducted over the network can cause severe bottlenecks
• Parallel file systems may not be available on all systems
Best practices:
• Reduce overall I/O as much as possible
• Write large chunks rather than small ones
• Use fewer, larger files instead of many small files
• Use a parallel file system (e.g., Lustre) if available
• Consider having a subset of tasks perform I/O (gather/scatter pattern)
• MPI-IO has been available since MPI-2 (1996)

Chapter 23: Performance Analysis and Debugging

23.1 Performance Analysis Process
Performance analysis is an iterative process during development:

Phase Activity
1. Measurement Collect runtime data: cache misses, FP
operations, subroutine timing, message passing
events. Two techniques: profiling (summary
data) and tracing (detailed per-event records).
2. Analysis Inspect data to detect performance problems.
Check conditions and severity of potential
issues. Apply visualization tools.
3. Ranking Rank problems by severity. The most severe
problem is the bottleneck — address it first.

23.2 Profiling vs. Tracing

Technique How it Works Advantages Disadvantages
Profiling Summarizes data. Moderate data size; Not fine-grained; can't
Sampling (interrupt good overview analyze individual
every ~10ms, record instances
location) or
instrumentation (insert
monitoring calls).
Tracing Records every event Very detailed; can Very large data files;
(subroutine entry/exit, analyze individual potential overhead
each message, instances
timestamps).
Profiling methods:
• Sampling (e.g., UNIX prof): Regularly interrupts the program, accumulates time per
source location.
• Instrumentation: Compiler or tool inserts calls to a monitoring library at region boundaries.
More precise but higher overhead.
Tracing:
• Records per event: timestamp, message size, target process, bandwidth, etc.
• Trace records stored in per-process buffers, merged into a single time-ordered trace file.

23.3 Parallel Debugging

Debugging parallel programs is harder than sequential because:
1. Multiple processes/threads must be monitored simultaneously
2. Program behavior may be non-deterministic and non-reproducible (race conditions)
3. Current tools handle issue (1) but not (2)
Common tools:
• TotalView (Totalview Technologies) — breakpoints, single stepping, variable inspection
for individual or groups of processes
• DDT (Allinea/ARM) — similar capabilities with process grouping and data summarization
Both support MPI and OpenMP on multiple platforms.

23.4 Performance Tools

Tool From Capabilities
TAU University of Oregon Profiling and tracing
Vampir TU Dresden Trace visualization
Scalasca Jülich Supercomputing Centre Automatic performance
problem detection
ParaDyn University of Wisconsin- Automatic performance
Madison analysis

23.5 Future Trends

• Automated performance analysis: Tools that automatically identify common performance
problems (Scalasca, KOJAK).
• Hybrid programming: Clustered shared memory systems with multi-core nodes create 3-
level parallelism hierarchies requiring combined MPI + OpenMP programming.
• PGAS languages: Partitioned Global Address Space languages (UPC, Co-array Fortran)
provide simpler data distribution with implicit one-sided communication.
Quick Reference: Formulas and Key Equations
Formula Expression Context
Amdahl's Law S = 1 / ((1-p) + p/N) Maximum speedup with N
processors, p = parallelizable
fraction
Amdahl's Max Speedup S_max = 1 / (1-p) Upper bound as N → ∞
Gustafson's Law S = N - α(N-1) Scaled speedup, α = serial
fraction on parallel system
Pipeline Speedup S(n) = m×n / (n+m-1) m tasks on n-stage pipeline
Pipeline Throughput U(n) = m / Tasks per time unit
((n+m-1)×t)
Pipeline Efficiency E(n) = m / (n+m-1) Actual vs. maximum speedup
ratio
Speedup S(n) = T(1) / T(n) Time on 1 processor / time on n
processors
Efficiency E(n) = S(n) / n How well processors are
utilized

This guide synthesizes all materials from the CSC 426 Parallel Computing course. For examination
preparation, focus on understanding the concepts deeply, being able to derive formulas, and
working through examples step by step.