SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 11

CS Fundamentals for Placements · Lesson 11 of 90 · 15 min

Pipelining and parallel processors

instruction pipelinestages (IF, ID, EX, MEM, WB)pipeline registerspeedupthroughputefficiencypipelined vs non-pipelined time numericalspipeline hazards (structural, data, control)RAW/WAR/WAW dependenciesstall/bubbleoperand forwarding (bypassing)branch penaltystatic and dynamic branch predictiondelayed branch

These are the notes for CS Fundamentals for Placements, episode 11. In episode 6 the CPU ran the instruction cycle (fetch, decode, execute) for one instruction, start to finish, before starting the next. Here you make it work on five instructions at once: the instruction pipeline and its stages (IF, ID, EX, MEM, WB), pipeline registers, speedup, throughput and efficiency, with pipelined vs non-pipelined time numericals. Then everything that breaks: pipeline hazards (structural, data, control), RAW/WAR/WAW dependencies, stalls (bubbles), operand forwarding (bypassing), branch penalty, static and dynamic branch prediction, and the delayed branch. Finally, beyond one pipeline: superscalar processors, out-of-order execution, instruction-level parallelism, Flynn's taxonomy (SISD, SIMD, MISD, MIMD), hyper-threading / SMT, GPUs, and SMP vs NUMA. Every term is explained in plain words, and there is a full glossary at the end. All outputs below are real: every program was run with Python 3.13. All timings are made up for the numericals.

A quick refresher from earlier episodes: the program counter (PC) holds the address of the next instruction; a register is a tiny, very fast storage slot inside the CPU (written here as r1, r2, ...); the ALU (arithmetic logic unit) does the arithmetic; a clock cycle is one tick of the CPU's clock, and every step of the hardware happens in step with it; CPI (cycles per instruction) is the average number of cycles one instruction takes; a load instruction reads memory into a register and a store writes a register to memory; a branch instruction may jump to another address (an if, or the end of a loop); a flip-flop is a 1-bit storage circuit (episode 5).

The five problems

Problem What it teaches
One instruction at a time is slow Pipelining, the 5 stages, pipeline registers, space-time diagram, k + n − 1, speedup, throughput, efficiency, unequal stages
Instructions get in each other's way Hazards (structural, data, control), stalls/bubbles, forwarding, load-use stall, RAW/WAR/WAW, register renaming
Branches Branch penalty, CPI with branches, flushing, static and dynamic (1-bit, 2-bit) prediction, delayed branch
Beyond one pipeline Superscalar, out-of-order execution, ILP, SMT / Hyper-Threading
Many processors Flynn's taxonomy (SISD, SIMD, MISD, MIMD), GPU, SMP vs NUMA

Problem 1: one instruction at a time is slow (pipelining)

A dosa counter: one cook takes the order, pours the batter, adds masala, folds and serves. Five steps, one minute each, and he starts the next dosa only after serving this one. 100 customers take 500 minutes, and at any moment four of the five steps' tools sit idle.

The fix: five cooks, one step each, passing the plate down the line. Each dosa still takes 5 minutes (its latency), but once the line is full, a dosa comes out every minute. Overlapping the steps of many instructions like this is pipelining.

The 5-stage pipeline

Stage Name What happens
IF Instruction fetch Read the instruction at the PC from (instruction) memory; PC moves on
ID Instruction decode Work out what the instruction is; read its source registers
EX Execute The ALU computes (add, compare, or the address of a load/store)
MEM Memory access A load reads data memory; a store writes it; others do nothing
WB Write back Write the result into the destination register

Between each pair of stages sits a pipeline register (latch): a set of flip-flops that holds one instruction's half-done work (its decoded fields, values, ALU result) at the end of each clock cycle, so the next stage can pick it up in the next cycle. It is the plate passed from cook to cook. Every stage takes exactly one clock cycle.

The space-time diagram, live

# print the pipeline: which stage each instruction is in
STAGES = ["IF", "ID", "EX", "MEM", "WB"]
n = 4
print("cycle  " + " ".join(f"{c:>4}" for c in range(1, n + 5)))
for i in range(n):
    row = ["    "] * (n + 4)
    for s, name in enumerate(STAGES):
        row[i + s] = f"{name:>4}"   # I(i+1) enters at cycle i+1
    print(f"I{i + 1}     " + " ".join(row))

Output:

cycle     1    2    3    4    5    6    7    8
I1       IF   ID   EX  MEM   WB               
I2            IF   ID   EX  MEM   WB          
I3                 IF   ID   EX  MEM   WB     
I4                      IF   ID   EX  MEM   WB

In cycle 5 every stage is busy with a different instruction. 4 instructions finish in 8 cycles = 5 + 4 − 1.

Time, speedup, throughput, efficiency

For n instructions on a k-stage pipeline with cycle time t:

  • Non-pipelined time = n × k × t (when every stage takes t).
  • Pipelined time = (k + n − 1) × t: k cycles to fill the pipe for the first instruction, then one more instruction finishes every cycle.
  • Speedup = non-pipelined time ÷ pipelined time = n·k ÷ (k + n − 1). As n grows, speedup → k (the ideal).
  • Throughput = instructions finished per unit time = n ÷ pipelined time.
  • Efficiency = speedup ÷ k = n ÷ (k + n − 1): the fraction of stage-slots doing useful work.
# n instructions, k stages, each stage takes t ns
n, k, t = 100, 5, 1

no_pipe = n * k * t              # one instruction at a time
pipe = (k + n - 1) * t           # fill k, then 1 per cycle
speedup = no_pipe / pipe

print("non-pipelined:", no_pipe, "ns")
print("pipelined    :", pipe, "ns")
print(f"speedup = {speedup:.2f}  (max = k = {k})")
print(f"throughput = {n / pipe:.2f} instructions per ns")
print(f"efficiency = {speedup / k:.0%}")

Output:

non-pipelined: 500 ns
pipelined    : 104 ns
speedup = 4.81  (max = k = 5)
throughput = 0.96 instructions per ns
efficiency = 96%

Pipelining does not make one instruction faster (its latency is still 5 cycles, slightly more with latch delays). It raises throughput.

Unequal stages: the slowest stage sets the clock

Real stages take different times. The clock must be long enough for the slowest stage, plus the delay of the pipeline register.

  • Cycle time = max(stage delays) + latch delay.
  • Non-pipelined time per instruction = sum of stage delays (no latches needed).
# unequal stages: the cycle is set by the SLOWEST stage
stages = [4, 6, 5, 3, 2]       # ns for IF ID EX MEM WB
latch = 1                      # pipeline register delay, ns
n, k = 100, len(stages)

cycle = max(stages) + latch
no_pipe = n * sum(stages)
pipe = (k + n - 1) * cycle
print("cycle time   :", cycle, "ns")
print("non-pipelined:", no_pipe, "ns")
print("pipelined    :", pipe, "ns")
print(f"speedup      : {no_pipe / pipe:.2f}")

Output:

cycle time   : 7 ns
non-pipelined: 2000 ns
pipelined    : 728 ns
speedup      : 2.75

A speedup of 2.75, far below 5. Lesson: designers balance the stages (split slow stages, merge fast ones).

Problem 2: instructions get in each other's way (hazards)

A hazard is anything that stops the next instruction from entering its stage in the next cycle.

The dosa line Hazard In a CPU
Two cooks need the one tawa at the same moment Structural hazard Two stages need the same hardware at once, e.g. IF and MEM both reading one memory. Fix: more hardware (split instruction/data caches, episode 10)
The folder needs masala that the previous cook hasn't added yet Data hazard An instruction needs a result an earlier instruction hasn't produced yet
The customer changes the order; half-made dosas are wasted Control hazard A branch changes which instruction comes next; instructions already fetched are the wrong ones

A data hazard gives a wrong answer, live

I1: ADD r1 = r2 + r3 writes r1 in WB (cycle 5). I2: SUB r4 = r1 − 1 reads r1 in ID (cycle 3), two cycles too early.

# I1: ADD r1 = r2 + r3     I2: SUB r4 = r1 - 1
reg = {"r1": 0, "r2": 2, "r3": 3}

def run(stalls, forwarding=False):
    if forwarding:
        ready, need = 3, 4 + stalls   # I1's EX -> I2's EX
    else:
        ready, need = 5, 3 + stalls   # I1's WB -> I2's ID
    ok = need > ready
    r1 = reg["r2"] + reg["r3"] if ok else reg["r1"]
    how = "forwarding" if forwarding else "register file"
    print(f"{how}, {stalls} stalls: r1 = {r1}, r4 = {r1 - 1}")

run(0)
run(3)
run(0, forwarding=True)

Output:

register file, 0 stalls: r1 = 0, r4 = -1
register file, 3 stalls: r1 = 5, r4 = 4
forwarding, 0 stalls: r1 = 5, r4 = 4
  • Fix 1: stall. The hardware holds I2 back and sends empty slots, called stalls or bubbles, down the pipeline until r1 is written. Correct but slow. (In this simple model the register is read strictly after WB, so 3 stalls. Many textbook designs write the register file in the first half of a cycle and read it in the second half, which needs only 2 stalls. Read the question's assumption.)
  • Fix 2: operand forwarding (bypassing). The sum already exists at the end of I1's EX stage, in the EX/MEM pipeline register. An extra wire (a bypass path) feeds it straight into I2's EX stage. Zero stalls.
  • Load-use hazard: a load's data arrives only at the end of MEM, one cycle later than an ALU result. An instruction that uses the loaded value right away still needs 1 stall, even with forwarding. Compilers reorder instructions to put something independent in that slot.

Three kinds of data dependency

Dependency Name Example Real data flow?
RAW (read after write) True dependency r1 = r2 + r3; r4 = r1 − 1 Yes: the second needs the first's result
WAR (write after read) Anti-dependency r4 = r1 − 1; r1 = r5 + r6 No: the second must not overwrite r1 before the first reads it
WAW (write after write) Output dependency r1 = r2 + r3; r1 = r5 + r6 No: the last write must be the one that remains

In a simple in-order 5-stage pipeline only RAW causes hazards. WAR and WAW matter when instructions can finish out of order. They are just name clashes (two instructions using the same register name), so the hardware fixes them with register renaming: it gives the second instruction a different, hidden physical register.

Problem 3: branches (control hazards)

A branch is decided only a few stages in. Until then, what should IF fetch?

A chai stall Branch handling
Wait for the order, then start Stall until the branch is decided. The lost cycles are the branch penalty
Start your usual chai as you walk in; throw it away if you order coffee Branch prediction: guess, keep fetching, flush (discard) the wrong instructions if the guess was wrong
Remember what you ordered last time Dynamic branch prediction: guess from the branch's own past

The cost of branches, live

CPI = 1 + (branch fraction) × (fraction handled badly) × (penalty in cycles).

# CPI with branch stalls: 20% of instructions are branches,
# a wrong guess (or no guess) costs 3 cycles
branches, penalty = 0.20, 3

for name, wrong in [("stall on every branch", 1.00),
                    ("predictor, 90% right ", 0.10)]:
    cpi = 1 + branches * wrong * penalty
    print(f"{name}: CPI = {cpi:.2f}")

Output:

stall on every branch: CPI = 1.60
predictor, 90% right : CPI = 1.06

Static and dynamic prediction

  • Static prediction: a fixed rule decided before the program runs (by the hardware designer or the compiler).
  • Always not taken: keep fetching the next instruction.
  • Always taken.
  • Backward taken, forward not taken (BTFN): a branch that jumps backwards is usually a loop, so predict taken.
  • Dynamic prediction: a small table (a branch history table) keeps a few bits per branch and learns.
  • 1-bit predictor: predict whatever happened last time.
  • 2-bit predictor (saturating counter): a counter 0 to 3; taken adds 1 (max 3), not taken subtracts 1 (min 0); predict taken at 2 or 3. It changes its mind only after two wrong guesses in a row.
  • Delayed branch: the instruction right after the branch (the delay slot) always executes, whichever way the branch goes. The compiler moves a useful, independent instruction into that slot so the cycle isn't wasted (or puts a NOP, "no operation", if it finds none).
# two branches in a loop body, run 100 times:
#   loop:  taken 9 times, then not taken
#   check: "if error" - never taken
loop = ([True] * 9 + [False]) * 10
check = [False] * 100

def score(predict, update, start):
    right = 0
    for outcomes in (loop, check):    # own history per branch
        s = start
        for taken in outcomes:
            right += predict(s) == taken
            s = update(s, taken)
    return f"{right}/200"

print("always taken:", score(lambda s: True, lambda s, t: s, 0))
print("1-bit       :", score(lambda s: s == 1,
                             lambda s, t: int(t), 1))
print("2-bit       :", score(lambda s: s >= 2,
      lambda s, t: min(s + 1, 3) if t else max(s - 1, 0), 2))

Output:

always taken: 90/200
1-bit       : 180/200
2-bit       : 189/200

Why 1-bit loses to 2-bit on the loop: at the loop exit it is wrong once and flips to "not taken", so it is wrong again on the first branch of the next loop: two misses per loop. The 2-bit counter drops from 3 to 2 at the exit, still predicts taken, and misses once per loop.

Problem 4: beyond one pipeline

Idea Real-life What it means
Superscalar A toll plaza opening more lanes Two or more pipelines side by side: several instructions start (issue) per cycle, so CPI can drop below 1
Out-of-order execution While the biryani cooks, the chef makes quick chai orders; the waiter still serves tokens in order Run instructions whose inputs are ready, even if earlier ones are waiting (e.g. on a slow load); results are made visible (committed) in program order
ILP (instruction-level parallelism) How many orders don't depend on each other How many instructions in a program could run at the same time
SMT (simultaneous multithreading) One cook juggling two orders, filling idle moments One core runs instructions from two threads at once, sharing its units
  • A superscalar CPU's speedup is limited by the program's ILP: dependent instructions still wait.
  • Hyper-Threading is Intel's proprietary name for its SMT implementation: each physical core appears to the operating system as two logical processors. It was introduced on Xeon server processors in February 2002 and on Pentium 4 desktop processors in November 2002 (source: Wikipedia, "Hyper-threading", fetched 29 Oct 2026).
  • A thread (more in the OS episodes) is one independent sequence of instructions inside a program.

Problem 5: many processors

Flynn's taxonomy

Flynn's taxonomy sorts computers by two questions: how many instruction streams and how many data streams are processed at once.

Class Meaning Real-life (a school) Example
SISD Single instruction, single data One tutor, one student A classic single-core CPU
SIMD Single instruction, multiple data PT teacher: "Everyone, jump!" Vector units (one instruction adds 8 pairs of numbers), GPUs
MISD Multiple instructions, single data Three examiners each check the same paper differently Rare: some fault-tolerant systems
MIMD Multiple instructions, multiple data Every class studies its own subject Multicore processors, clusters

GPU, SMP and NUMA

  • GPU (graphics processing unit): thousands of simple cores that all run the same instructions on different data (pixels, matrix entries). Excellent for graphics and AI; poor at branchy, one-thing-at-a-time code.
  • SMP (symmetric multiprocessing): several processors share one memory, all at the same distance and speed. Like one fridge in the middle of the house. Simple, but the shared memory path becomes a bottleneck as processors grow.
  • NUMA (non-uniform memory access): each processor has its own local memory; it can reach the others' memory too, but more slowly. Like a fridge on every floor. Programs run best when each thread uses the memory near its processor.

Common mistakes (and the real output)

Mistake Real output Fix
Reading a register before it is written register file, 0 stalls: r1 = 0, r4 = -1 Stall, or forward the result
Pipelined time = n × cycle wrong: n x cycle = 100 ns right: (k + n - 1) x cycle = 104 ns Add the k − 1 fill cycles
Cycle time = average stage time wrong cycle (average) = 4.0 ns right cycle (max + latch) = 7 ns The slowest stage (plus latch) sets the clock
Non-pipelined time = n × k × pipelined cycle wrong speedup = 4.81 right speedup = 2.75 Non-pipelined time uses the sum of stage delays, no latches
Charging the branch penalty on every branch when most are predicted wrong CPI = 1.60 right CPI = 1.06 Multiply by the misprediction rate
One static rule for every branch always taken: 90/200 Dynamic 2-bit prediction: 189/200

The program behind rows 2 to 5:

# common mistakes, measured
n, k, t = 100, 5, 1
print("wrong: n x cycle =", n * t, "ns   right: (k + n - 1) x cycle =", (k + n - 1) * t, "ns")

stages, latch = [4, 6, 5, 3, 2], 1
avg_cycle = sum(stages) / len(stages)
print("wrong cycle (average) =", avg_cycle, "ns   right cycle (max + latch) =", max(stages) + latch, "ns")

# speedup with the non-pipelined time wrongly computed as n x k x cycle
cycle = max(stages) + latch
wrong = (n * k * cycle) / ((k + n - 1) * cycle)
right = (n * sum(stages)) / ((k + n - 1) * cycle)
print(f"wrong speedup = {wrong:.2f}   right speedup = {right:.2f}")

# CPI with branches: adding the penalty for ALL branches when most are predicted right
f, p, acc = 0.2, 3, 0.9
print(f"wrong CPI = {1 + f * p:.2f}   right CPI = {1 + f * (1 - acc) * p:.2f}")

Output:

wrong: n x cycle = 100 ns   right: (k + n - 1) x cycle = 104 ns
wrong cycle (average) = 4.0 ns   right cycle (max + latch) = 7 ns
wrong speedup = 4.81   right speedup = 2.75
wrong CPI = 1.60   right CPI = 1.06

Mini project: count the cycles of a program, with and without forwarding

A small model of a 5-stage pipeline. Each instruction lists its destination register, its source registers, and whether it is a load. Without forwarding, a result can be used in EX only 4 cycles after the producer's EX (after its WB, then the consumer's ID). With forwarding, an ALU result is usable in the very next cycle, and a load's result one cycle later (the load-use stall).

# mini project: count cycles for a short program on a 5-stage pipeline,
# with and without operand forwarding. Each instruction: (dest, sources, is_load)
prog = [
    ("r1", ["r2", "r3"], False),   # ADD r1 = r2 + r3
    ("r4", ["r1"], False),         # SUB r4 = r1 - 1      (RAW on r1)
    ("r5", ["r6"], True),          # LW  r5 = mem[r6]
    ("r7", ["r5"], False),         # ADD r7 = r5 + 1      (load-use on r5)
    ("r8", ["r9"], False),         # independent
]

def cycles(forwarding):
    ex = {}            # instruction index -> its EX cycle
    ready = {}         # register -> first cycle a consumer's EX (or ID) may use it
    stalls = 0
    prev_ex = 0
    for i, (dest, srcs, load) in enumerate(prog):
        want = max(prev_ex + 1, i + 3)          # EX cycle with no hazard
        for r in srcs:
            if r in ready:
                want = max(want, ready[r])
        stalls += want - max(prev_ex + 1, i + 3)
        ex[i] = prev_ex = want
        if forwarding:
            ready[dest] = want + (2 if load else 1)   # ALU: next cycle; load: after MEM
        else:
            ready[dest] = want + 4                    # WB = EX + 2; ID after WB, EX one later
    total = prev_ex + 2                               # last instruction: MEM, WB
    return total, stalls

for fw in (False, True):
    total, st = cycles(fw)
    print(f"forwarding={fw!s:5}: {total} cycles, {st} stalls")

Output:

forwarding=False: 15 cycles, 6 stalls
forwarding=True : 10 cycles, 1 stalls

The ideal is k + n − 1 = 5 + 5 − 1 = 9 cycles. With forwarding, only the load-use stall remains. Try it: move the independent r8 instruction between the load and its use (instruction scheduling, which compilers do), and the forwarding version drops to 9 cycles with 0 stalls.

Practice

  1. Stages of 3, 5, 4, 4 ns, pipeline register 1 ns, 200 instructions. Cycle time, both total times, speedup?
  2. 25% of instructions are branches, 80% are predicted correctly, the misprediction penalty is 2 cycles. CPI?
  3. Run the predictor demo on a branch that alternates T, N, T, N ... (100 times). Which predictor does worst, and why?
  4. A 6-stage pipeline, 2 ns per stage, 50 instructions, no hazards. Total time with and without the pipeline?
  5. k = 4, n = 1000, 2 ns per stage. Pipelined time, speedup, efficiency?
  6. What is the maximum speedup of a 5-stage pipeline, and what is the speedup for only 10 instructions?
  7. 30% of instructions are loads, and 40% of loads are immediately followed by an instruction that uses the loaded value (1 stall each, with forwarding). CPI?
  8. Classify the dependencies: I1: r1 = r2 + r3; I2: r2 = r4 + 1; I3: r1 = r5 − r6; I4: r7 = r1 + r2.
  9. Draw the space-time diagram for I1 to I4 when I2 depends on I1 and there is no forwarding (3 stalls).
  10. Why can't pipelining make a single instruction faster?
  11. Which hazard does a split instruction/data cache remove?
  12. What is the delay slot, and what does the compiler put there?
Solutions

Numbers computed with a Python 3.13 script; its output:

Q1 cycle 6 ns, non-pipelined 3200 ns, pipelined 1218 ns, speedup 2.63
Q2 CPI = 1.10
Q4 (6 + 50 - 1) x 2 = 110 ns; non-pipelined 600 ns
Q5 k=4, n=1000, 2 ns: time 2006 ns, speedup 3.988, efficiency 99.7%
Q6 max speedup as n grows = k = 5; for n = 10: 3.57
Q3 T N T N ... always taken: 50  1-bit: 1  2-bit: 50 out of 100
Q7 CPI with 30% loads, 40% of them followed by a use (1 stall): 1.12
  1. Cycle = 5 + 1 = 6 ns; non-pipelined = 200 × 16 = 3,200 ns; pipelined = (4 + 200 − 1) × 6 = 1,218 ns; speedup 2.63.
  2. 1 + 0.25 × 0.2 × 2 = 1.10.
  3. 1-bit: 1/100. It always predicts the last outcome, and the outcome always changes. The 2-bit counter and "always taken" each get 50/100: the counter bounces between 2 and 3 and keeps predicting taken.
  4. 110 ns pipelined, 600 ns without.
  5. 2,006 ns, speedup 3.988, efficiency 99.7%.
  6. Maximum = 5 (= k, as n → ∞). For n = 10: 50 ÷ 14 = 3.57.
  7. 1 + 0.3 × 0.4 × 1 = 1.12.
  8. I1→I4 on r1: no, I3 writes r1 later, so I3→I4 RAW on r1; I2→I4 RAW on r2; I1→I2 WAR on r2 (I1 reads r2, I2 writes it); I1→I3 WAW on r1.
  9. I1: IF1 ID2 EX3 MEM4 WB5. I2: IF2, then stalls in cycles 3, 4, 5, ID6 EX7 MEM8 WB9. I3: IF6 ID7 EX8 MEM9 WB10 (it waits behind I2). I4: IF7 ID8 EX9 MEM10 WB11. Total 11 cycles instead of 8.
  10. Each instruction still passes through every stage; pipelining overlaps different instructions (throughput), it doesn't shorten one (latency). Latch delays even add a little.
  11. The structural hazard between IF (fetching instructions) and MEM (reading data) on one memory.
  12. The instruction slot right after a branch that always executes. The compiler fills it with a useful instruction that doesn't depend on the branch, or a NOP.

Quick quiz

A 6-stage pipeline with 2 ns per stage runs 50 instructions with no hazards. Total time?

  • A. 100 ns
  • B. 110 ns
  • C. 300 ns
  • D. 600 ns
Answer

B, 110 ns. (k + n − 1) × cycle = (6 + 50 − 1) × 2 = 55 × 2 = 110 ns. Without the pipeline: 50 × 6 × 2 = 600 ns.

Interview questions

  • What is pipelining? Splitting instruction execution into stages and overlapping different instructions in different stages, like an assembly line. It raises throughput, not single-instruction latency.
  • Name the classic 5 stages. IF (fetch), ID (decode + register read), EX (ALU), MEM (data memory), WB (register write back).
  • Why are pipeline registers needed? To hold each instruction's intermediate results between stages at each clock edge, so stages can work on different instructions independently.
  • Formula for pipelined time and speedup? (k + n − 1) × cycle; speedup = n·k ÷ (k + n − 1) for equal stages, approaching k.
  • What limits the clock of a pipeline? The slowest stage plus the pipeline register delay.
  • Types of hazards? Structural (resource conflict), data (dependence on an unfinished result), control (branches).
  • What is forwarding? Feeding a result from a later pipeline register straight into the ALU input of a following instruction, avoiding the wait for WB.
  • Why does a load-use hazard still stall with forwarding? The loaded value exists only after MEM, one cycle too late for an immediately following EX.
  • RAW vs WAR vs WAW? True dependency vs anti-dependency vs output dependency; WAR and WAW are name clashes removed by register renaming.
  • What is branch prediction? Static vs dynamic? Guessing a branch's direction to keep fetching; static uses a fixed rule, dynamic learns from history (1-bit, 2-bit counters).
  • Why is a 2-bit predictor better than 1-bit for loops? It misses once per loop exit instead of twice.
  • What is a delayed branch? An architecture where the instruction after a branch always executes; the compiler fills that slot usefully.
  • Superscalar vs pipelined? Pipelined overlaps stages of one stream; superscalar adds multiple pipelines to issue several instructions per cycle.
  • What does out-of-order execution do? Executes instructions as soon as their operands are ready, then commits results in program order.
  • What is SMT / Hyper-Threading? One core running two (or more) threads at once, sharing execution units; Intel's version presents two logical processors per core.
  • Explain Flynn's taxonomy. SISD, SIMD, MISD, MIMD by number of instruction and data streams.
  • SMP vs NUMA? SMP: uniform shared memory. NUMA: each processor has local memory; remote memory is slower.

Glossary

Term Plain meaning Example
Instruction pipeline Overlapping the stages of many instructions, like an assembly line the dosa counter with 5 cooks
Stage One step of instruction processing, one clock cycle long IF, ID, EX, MEM, WB
IF Instruction fetch: read the instruction at the PC cook 1 takes the order
ID Instruction decode: work out the instruction, read its registers
EX Execute: the ALU computes r2 + r3
MEM Memory access: loads read and stores write data memory LW r5
WB Write back: store the result in a register r1 = 5
Pipeline register (latch) Flip-flops between stages that hold an instruction's partial results the plate passed on
Space-time diagram Table of which instruction is in which stage in each cycle the IF/ID/EX printout
Latency Time for one instruction (or dosa) from start to finish 5 cycles
Throughput Work finished per unit time 0.96 instructions/ns
Speedup Old time ÷ new time 4.81
Efficiency Speedup ÷ number of stages: how busy the stages are 96%
Fill time The k − 1 extra cycles before the pipeline is full the "k − 1" in k + n − 1
Cycle time Length of one clock cycle = slowest stage + latch delay 7 ns
Hazard Anything stopping the next instruction entering its stage on time
Structural hazard Two stages need the same hardware at once one tawa, two cooks
Data hazard An instruction needs a result not produced yet r4 = -1
Control hazard A branch changes which instruction comes next the changed order
Stall / bubble An empty slot inserted so an instruction waits 3 stalls
Operand forwarding / bypassing Passing a result straight from a pipeline register to a later instruction's ALU forwarding, 0 stalls
Load-use hazard Using a loaded value in the very next instruction; 1 stall even with forwarding LW r5; ADD r7 = r5 + 1
RAW Read after write: true dependency r1 written, then read
WAR Write after read: anti-dependency r1 read, then overwritten
WAW Write after write: output dependency r1 written twice
Register renaming Giving clashing instructions different hidden registers removes WAR/WAW
Branch penalty Cycles lost when a branch isn't handled in time or is mispredicted 3 cycles
Flush Discarding wrongly fetched instructions throwing away the chai
Branch prediction Guessing a branch's direction so fetching can continue
Static prediction A fixed rule chosen before running always taken, BTFN
Dynamic prediction A rule that learns from each branch's history 1-bit, 2-bit
Branch history table Small table of prediction bits, one entry per branch
1-bit predictor Predicts the branch's last outcome 180/200
2-bit predictor (saturating counter) Counter 0–3, predicts taken at 2–3; needs two misses to flip 189/200
Delayed branch / delay slot The instruction after a branch always executes compiler fills it
NOP "No operation": an instruction that does nothing fills an empty delay slot
Superscalar processor Has multiple pipelines; issues several instructions per cycle more toll lanes
Out-of-order execution Runs ready instructions first, commits in program order chai before biryani
ILP Instruction-level parallelism: instructions that can run at the same time
Thread One independent sequence of instructions in a program
SMT Simultaneous multithreading: one core runs several threads at once one cook, two orders
Hyper-Threading Intel's SMT; two logical processors per core introduced on Xeon, Feb 2002
Flynn's taxonomy Classifying computers by instruction and data streams SISD, SIMD, MISD, MIMD
SISD / SIMD / MISD / MIMD Single/multiple instruction streams × single/multiple data streams tutor / PT teacher / examiners / whole school
Vector unit Hardware that applies one instruction to many numbers at once adds 8 pairs at once
GPU Graphics processing unit: thousands of simple cores doing the same work on lots of data graphics, AI
SMP Symmetric multiprocessing: processors share one uniform memory one fridge for the house
NUMA Non-uniform memory access: each processor has faster local memory a fridge on every floor

Summary

  • Pipelining overlaps the 5 stages (IF, ID, EX, MEM, WB), separated by pipeline registers. Time = (k + n − 1) × cycle; speedup → k; efficiency = speedup ÷ k. 500 ns → 104 ns.
  • The slowest stage + latch sets the cycle: unequal stages gave only 2.75× speedup.
  • Hazards: structural (more hardware), data (stalls, forwarding; load-use still 1 stall), control (branches). RAW is real; WAR/WAW are name clashes fixed by register renaming.
  • Branches: CPI = 1 + f × miss × penalty (1.60 → 1.06). Static rules vs dynamic 1-bit and 2-bit predictors (90 → 180 → 189 out of 200); delayed branch.
  • Beyond: superscalar, out-of-order, ILP, SMT / Hyper-Threading; Flynn's taxonomy; GPU; SMP vs NUMA.

Next episode: OOP 1: classes, objects and encapsulation. Why procedural code breaks as programs grow, and how classes, constructors, this, private fields and static fix it.