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
- Stages of 3, 5, 4, 4 ns, pipeline register 1 ns, 200 instructions. Cycle time, both total times, speedup?
- 25% of instructions are branches, 80% are predicted correctly, the misprediction penalty is 2 cycles. CPI?
- Run the predictor demo on a branch that alternates T, N, T, N ... (100 times). Which predictor does worst, and why?
- A 6-stage pipeline, 2 ns per stage, 50 instructions, no hazards. Total time with and without the pipeline?
- k = 4, n = 1000, 2 ns per stage. Pipelined time, speedup, efficiency?
- What is the maximum speedup of a 5-stage pipeline, and what is the speedup for only 10 instructions?
- 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?
- Classify the dependencies:
I1: r1 = r2 + r3; I2: r2 = r4 + 1; I3: r1 = r5 − r6; I4: r7 = r1 + r2. - Draw the space-time diagram for I1 to I4 when I2 depends on I1 and there is no forwarding (3 stalls).
- Why can't pipelining make a single instruction faster?
- Which hazard does a split instruction/data cache remove?
- 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
- Cycle = 5 + 1 = 6 ns; non-pipelined = 200 × 16 = 3,200 ns; pipelined = (4 + 200 − 1) × 6 = 1,218 ns; speedup 2.63.
- 1 + 0.25 × 0.2 × 2 = 1.10.
- 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.
- 110 ns pipelined, 600 ns without.
- 2,006 ns, speedup 3.988, efficiency 99.7%.
- Maximum = 5 (= k, as n → ∞). For n = 10: 50 ÷ 14 = 3.57.
- 1 + 0.3 × 0.4 × 1 = 1.12.
- 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.
- 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.
- Each instruction still passes through every stage; pipelining overlaps different instructions (throughput), it doesn't shorten one (latency). Latch delays even add a little.
- The structural hazard between IF (fetching instructions) and MEM (reading data) on one memory.
- 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.