Computer Architecture & Organization

How a machine actually executes an instruction: number representation, the datapath, pipelining and its hazards, the cache hierarchy, and the arithmetic of measuring performance.

If you remember nothing else

Two's complement represents negatives so that subtraction is addition - one adder circuit serves both, which is why every machine uses it.
The von Neumann bottleneck is that instructions and data share one bus, so the CPU is limited by memory bandwidth, not by arithmetic speed.
Pipelining raises throughput, never the latency of a single instruction - one instruction still takes the same total time.
There are exactly three hazard classes: structural (resource conflict), data (operand not ready), and control (branch outcome unknown).
Cache works only because of locality - temporal (reuse soon) and spatial (neighbours used soon). Without it, a cache would be pure overhead.
Amdahl's law: speedup is capped by the fraction you cannot parallelise, so optimising 10% of the runtime can never give more than an 11% gain.

7 chapters

1Number representation
2Von Neumann architecture and the instruction cycle
3Instruction sets and addressing modes
4Pipelining and hazards
5The memory hierarchy and cache
6I/O and interrupts
7Measuring performance

Number representation

Scheme	Range for n bits	Zero	Problem
Unsigned	$0$ to $2^{n} - 1$	One	Cannot represent negatives
Sign-magnitude	$- (2^{n - 1} - 1)$ to $2^{n - 1} - 1$	Two (+0 and −0)	Needs separate add and subtract circuits
1's complement	$- (2^{n - 1} - 1)$ to $2^{n - 1} - 1$	Two	End-around carry needed
2's complement	$- 2^{n - 1}$ to $2^{n - 1} - 1$	One	Asymmetric range - that is all

Plain textTwo's complement, 8-bit

+5  = 0000 0101
-5  : invert -> 1111 1010,  add 1 -> 1111 1011

Check: 5 + (-5)
   0000 0101
 + 1111 1011
 -----------
  10000 0000   -> discard the carry out -> 0000 0000 = 0  correct

Range for 8 bits: -128 (1000 0000) to +127 (0111 1111)
Note -128 has no positive counterpart - this is the asymmetry.

OVERFLOW rule: adding two numbers of the SAME sign and getting the
opposite sign. 127 + 1 = 0111 1111 + 0000 0001 = 1000 0000 = -128.

IEEE 754 floating point

Format	Sign	Exponent	Mantissa	Bias	Approx. precision
Single (32-bit)	1 bit	8 bits	23 bits	127	~7 decimal digits
Double (64-bit)	1 bit	11 bits	52 bits	1023	~15 decimal digits

value = (- 1)^{s} \times 1. m \times 2^{(e - bias)}

The leading 1 is implicit for normalised numbers - it is never stored, which buys one extra bit of precision for free.

Exponent all zeros with a non-zero mantissa encodes a denormalised number, filling the gap around zero.
Exponent all ones with a zero mantissa encodes infinity; with a non-zero mantissa it encodes NaN.
NaN is not equal to anything, including itself - x != x is the standard NaN test.

Von Neumann architecture and the instruction cycle

The von Neumann (stored-program) architecture keeps instructions and data in the same memory, reached over the same bus. Its rival, the Harvard architecture, uses separate memories and buses for each.

	Von Neumann	Harvard
Memory	One, shared	Separate instruction and data memories
Buses	One	Two - can fetch an instruction and data simultaneously
Flexibility	Code can be treated as data - enables compilers, loaders, JITs	Rigid separation
Bottleneck	Yes - the von Neumann bottleneck	Reduced
Found in	General-purpose CPUs	DSPs, microcontrollers; modern CPUs use a modified Harvard design in their L1 caches

Fetch
The address in the PC goes to the MAR; memory returns the instruction into the MBR, which is copied to the IR. The PC is incremented.
Decode
The control unit interprets the opcode in the IR and works out which operands are needed and where they are.
Execute
The ALU performs the operation, or a memory or I/O access is initiated.
Store (write back)
The result is written to a register or to memory. The cycle then repeats, after checking for pending interrupts.

Register	Full name	Holds
PC	Program Counter	Address of the next instruction
IR	Instruction Register	The instruction currently being executed
MAR	Memory Address Register	Address being read from or written to
MBR / MDR	Memory Buffer / Data Register	Data in transit to or from memory
ACC	Accumulator	Intermediate ALU results
SP	Stack Pointer	Top of the current stack
PSW	Program Status Word	Condition flags: zero, carry, sign, overflow

Instruction sets and addressing modes

	RISC	CISC
Instruction count	Few, simple	Many, complex
Instruction length	Fixed	Variable
Cycles per instruction	Mostly one (pipelined)	Several to many
Memory access	Load/store only - arithmetic works on registers	Arithmetic may operate directly on memory
Registers	Many	Fewer
Addressing modes	Few	Many
Complexity lives in	The compiler	The hardware (microcode)
Examples	ARM, RISC-V, MIPS, SPARC	x86, x86-64, VAX

Addressing mode	Operand is	Example	Use
Immediate	In the instruction itself	`MOV R1, #5`	Constants
Register	In a named register	`MOV R1, R2`	Fastest - no memory access
Direct (absolute)	At the address given	`MOV R1, [1000]`	Global variables
Indirect	At the address stored at the given address	`MOV R1, [[1000]]`	Pointers
Register indirect	At the address held in a register	`MOV R1, [R2]`	Pointer dereference
Indexed / displacement	At base register + offset	`MOV R1, [R2+4]`	Arrays and struct fields
Relative	At PC + offset	`JMP +8`	Position-independent branches

Pipelining and hazards

Pipelining overlaps the stages of consecutive instructions, in the same way an assembly line overlaps the assembly of consecutive cars. With a k-stage pipeline, a new instruction can complete every cycle once the pipeline is full.

Plain text5-stage pipeline: IF, ID, EX, MEM, WB

Cycle:      1    2    3    4    5    6    7    8    9
Instr 1:   IF   ID   EX   MEM  WB
Instr 2:        IF   ID   EX   MEM  WB
Instr 3:             IF   ID   EX   MEM  WB
Instr 4:                  IF   ID   EX   MEM  WB
Instr 5:                       IF   ID   EX   MEM  WB

Non-pipelined: 5 instructions x 5 cycles = 25 cycles
Pipelined:     5 + (5 - 1) = 9 cycles

General:  cycles = k + (n - 1)   for n instructions, k stages
Ideal speedup approaches k as n grows large.

Hazard	Cause	Example	Remedy
Structural	Two instructions need the same hardware unit in the same cycle	One memory port serving an instruction fetch and a data load	Duplicate the resource - separate instruction and data caches
Data	An instruction needs a result not yet written back	`ADD R1,R2,R3` then `SUB R4,R1,R5`	Forwarding (bypassing); stall only when forwarding cannot help
Control	The next address is unknown until a branch resolves	`BEQ` - which instruction follows?	Branch prediction, delay slots, speculative execution

Data dependency	Pattern	Called	A problem in a simple pipeline?
Read After Write	Write then read the same register	RAW - true dependency	Yes - the real hazard
Write After Read	Read then write the same register	WAR - anti-dependency	Only with out-of-order execution
Write After Write	Two writes to the same register	WAW - output dependency	Only with out-of-order execution

WAR and WAW are naming conflicts rather than genuine data flow, and register renaming eliminates both.

Static prediction - always taken, or always not taken. Backward branches (loops) are usually taken, so "backward taken, forward not taken" is a cheap and surprisingly effective heuristic.
Dynamic prediction - a branch history table records what each branch did last time. A 2-bit saturating counter avoids flipping the prediction on a single anomalous iteration, which matters for the last iteration of a loop.
A mispredicted branch costs the whole pipeline depth - every speculatively fetched instruction must be discarded. In a deep modern pipeline that is 15–20 cycles.

The memory hierarchy and cache

Level	Typical size	Typical latency	Managed by
Registers	~1 KB	0 cycles	Compiler
L1 cache	32–64 KB	~4 cycles	Hardware
L2 cache	256 KB–1 MB	~12 cycles	Hardware
L3 cache	8–32 MB	~40 cycles	Hardware
Main memory (DRAM)	8–64 GB	~200 cycles	OS
SSD	256 GB–4 TB	~100 μs	OS
Hard disk	1–20 TB	~10 ms	OS

Each level down is roughly 10× larger, 10× slower and cheaper per byte. Note the gap between L3 and DRAM - that is the cliff caches exist to avoid.

Mapping	A memory block may go	Lookup cost	Conflict misses
Direct mapped	In exactly one line	Cheapest - check one line	Frequent - two hot blocks mapping to one line thrash
Fully associative	In any line	Most expensive - compare all tags	None
N-way set associative	In any of N lines within one set	Compare N tags	Rare; the practical compromise (typically 4–16 way)

AMAT = hit time + miss rate \times miss penalty

Average Memory Access Time. Note that reducing the miss rate is only one of three levers - hit time and miss penalty matter equally.

Write policy	On a write hit	Trade-off
Write-through	Write to cache and memory simultaneously	Memory always consistent; higher write traffic. Usually paired with a write buffer
Write-back	Write only to cache; mark the line dirty and flush on eviction	Much less memory traffic; memory is temporarily stale, which complicates multiprocessor coherence

I/O and interrupts

Technique	How data moves	CPU involvement	Suits
Programmed I/O (polling)	The CPU repeatedly checks a status register	Total - the CPU is fully occupied waiting	Very simple or very fast devices
Interrupt-driven I/O	The device signals when ready; the CPU handles it then	Per transfer unit	Moderate-rate devices - keyboard, mouse
DMA	A DMA controller moves data directly between device and memory	Only at start and finish	High-throughput devices - disk, network, GPU

Measuring performance

CPU time = Instruction count \times CPI \times Clock cycle time

The three factors, and the three things any optimisation must move. A compiler change alters instruction count; an architecture change alters CPI; a process shrink alters cycle time.

Amdahl's law

Speedup = \frac{1}{( 1 - P ) + \frac{P}{N}}

P is the parallelisable fraction, N the number of processors. As N → ∞, speedup approaches 1/(1−P).

Plain textWhat Amdahl's law actually tells you

A program is 90% parallelisable (P = 0.9):
   4 cores:    1 / (0.1 + 0.9/4)   = 3.08x
  16 cores:    1 / (0.1 + 0.9/16)  = 6.40x
 100 cores:    1 / (0.1 + 0.9/100) = 9.17x
   infinite:   1 / 0.1             = 10.00x  <- the hard ceiling

The 10% serial portion caps you at 10x no matter how many cores
you buy. Doubling cores from 16 to 32 buys far less than doubling
from 2 to 4 - this is why "just add more cores" stops working.

Flynn's taxonomy	Instruction streams	Data streams	Example
SISD	One	One	Classic uniprocessor
SIMD	One	Many	Vector units (SSE, AVX, NEON), GPUs
MISD	Many	One	Rare - fault-tolerant redundant systems
MIMD	Many	Many	Multicore CPUs, clusters

Computer Architecture & Organization

How a machine actually executes an instruction: number representation, the datapath, pipelining and its hazards, the cache hierarchy, and the arithmetic of measuring performance.

If you remember nothing else

Two's complement represents negatives so that subtraction is addition - one adder circuit serves both, which is why every machine uses it.
The von Neumann bottleneck is that instructions and data share one bus, so the CPU is limited by memory bandwidth, not by arithmetic speed.
Pipelining raises throughput, never the latency of a single instruction - one instruction still takes the same total time.
There are exactly three hazard classes: structural (resource conflict), data (operand not ready), and control (branch outcome unknown).
Cache works only because of locality - temporal (reuse soon) and spatial (neighbours used soon). Without it, a cache would be pure overhead.
Amdahl's law: speedup is capped by the fraction you cannot parallelise, so optimising 10% of the runtime can never give more than an 11% gain.

7 chapters

1Number representation
2Von Neumann architecture and the instruction cycle
3Instruction sets and addressing modes
4Pipelining and hazards
5The memory hierarchy and cache
6I/O and interrupts
7Measuring performance

Number representation

Scheme	Range for n bits	Zero	Problem
Unsigned	$0$ to $2^{n} - 1$	One	Cannot represent negatives
Sign-magnitude	$- (2^{n - 1} - 1)$ to $2^{n - 1} - 1$	Two (+0 and −0)	Needs separate add and subtract circuits
1's complement	$- (2^{n - 1} - 1)$ to $2^{n - 1} - 1$	Two	End-around carry needed
2's complement	$- 2^{n - 1}$ to $2^{n - 1} - 1$	One	Asymmetric range - that is all

Plain textTwo's complement, 8-bit

+5  = 0000 0101
-5  : invert -> 1111 1010,  add 1 -> 1111 1011

Check: 5 + (-5)
   0000 0101
 + 1111 1011
 -----------
  10000 0000   -> discard the carry out -> 0000 0000 = 0  correct

Range for 8 bits: -128 (1000 0000) to +127 (0111 1111)
Note -128 has no positive counterpart - this is the asymmetry.

OVERFLOW rule: adding two numbers of the SAME sign and getting the
opposite sign. 127 + 1 = 0111 1111 + 0000 0001 = 1000 0000 = -128.

IEEE 754 floating point

Format	Sign	Exponent	Mantissa	Bias	Approx. precision
Single (32-bit)	1 bit	8 bits	23 bits	127	~7 decimal digits
Double (64-bit)	1 bit	11 bits	52 bits	1023	~15 decimal digits

value = (- 1)^{s} \times 1. m \times 2^{(e - bias)}

The leading 1 is implicit for normalised numbers - it is never stored, which buys one extra bit of precision for free.

Exponent all zeros with a non-zero mantissa encodes a denormalised number, filling the gap around zero.
Exponent all ones with a zero mantissa encodes infinity; with a non-zero mantissa it encodes NaN.
NaN is not equal to anything, including itself - x != x is the standard NaN test.

Von Neumann architecture and the instruction cycle

	Von Neumann	Harvard
Memory	One, shared	Separate instruction and data memories
Buses	One	Two - can fetch an instruction and data simultaneously
Flexibility	Code can be treated as data - enables compilers, loaders, JITs	Rigid separation
Bottleneck	Yes - the von Neumann bottleneck	Reduced
Found in	General-purpose CPUs	DSPs, microcontrollers; modern CPUs use a modified Harvard design in their L1 caches

Fetch
The address in the PC goes to the MAR; memory returns the instruction into the MBR, which is copied to the IR. The PC is incremented.
Decode
The control unit interprets the opcode in the IR and works out which operands are needed and where they are.
Execute
The ALU performs the operation, or a memory or I/O access is initiated.
Store (write back)
The result is written to a register or to memory. The cycle then repeats, after checking for pending interrupts.

Register	Full name	Holds
PC	Program Counter	Address of the next instruction
IR	Instruction Register	The instruction currently being executed
MAR	Memory Address Register	Address being read from or written to
MBR / MDR	Memory Buffer / Data Register	Data in transit to or from memory
ACC	Accumulator	Intermediate ALU results
SP	Stack Pointer	Top of the current stack
PSW	Program Status Word	Condition flags: zero, carry, sign, overflow

Instruction sets and addressing modes

	RISC	CISC
Instruction count	Few, simple	Many, complex
Instruction length	Fixed	Variable
Cycles per instruction	Mostly one (pipelined)	Several to many
Memory access	Load/store only - arithmetic works on registers	Arithmetic may operate directly on memory
Registers	Many	Fewer
Addressing modes	Few	Many
Complexity lives in	The compiler	The hardware (microcode)
Examples	ARM, RISC-V, MIPS, SPARC	x86, x86-64, VAX

Addressing mode	Operand is	Example	Use
Immediate	In the instruction itself	`MOV R1, #5`	Constants
Register	In a named register	`MOV R1, R2`	Fastest - no memory access
Direct (absolute)	At the address given	`MOV R1, [1000]`	Global variables
Indirect	At the address stored at the given address	`MOV R1, [[1000]]`	Pointers
Register indirect	At the address held in a register	`MOV R1, [R2]`	Pointer dereference
Indexed / displacement	At base register + offset	`MOV R1, [R2+4]`	Arrays and struct fields
Relative	At PC + offset	`JMP +8`	Position-independent branches

Pipelining and hazards

Plain text5-stage pipeline: IF, ID, EX, MEM, WB

Cycle:      1    2    3    4    5    6    7    8    9
Instr 1:   IF   ID   EX   MEM  WB
Instr 2:        IF   ID   EX   MEM  WB
Instr 3:             IF   ID   EX   MEM  WB
Instr 4:                  IF   ID   EX   MEM  WB
Instr 5:                       IF   ID   EX   MEM  WB

Non-pipelined: 5 instructions x 5 cycles = 25 cycles
Pipelined:     5 + (5 - 1) = 9 cycles

General:  cycles = k + (n - 1)   for n instructions, k stages
Ideal speedup approaches k as n grows large.

Hazard	Cause	Example	Remedy
Structural	Two instructions need the same hardware unit in the same cycle	One memory port serving an instruction fetch and a data load	Duplicate the resource - separate instruction and data caches
Data	An instruction needs a result not yet written back	`ADD R1,R2,R3` then `SUB R4,R1,R5`	Forwarding (bypassing); stall only when forwarding cannot help
Control	The next address is unknown until a branch resolves	`BEQ` - which instruction follows?	Branch prediction, delay slots, speculative execution

Data dependency	Pattern	Called	A problem in a simple pipeline?
Read After Write	Write then read the same register	RAW - true dependency	Yes - the real hazard
Write After Read	Read then write the same register	WAR - anti-dependency	Only with out-of-order execution
Write After Write	Two writes to the same register	WAW - output dependency	Only with out-of-order execution

WAR and WAW are naming conflicts rather than genuine data flow, and register renaming eliminates both.

Static prediction - always taken, or always not taken. Backward branches (loops) are usually taken, so "backward taken, forward not taken" is a cheap and surprisingly effective heuristic.
Dynamic prediction - a branch history table records what each branch did last time. A 2-bit saturating counter avoids flipping the prediction on a single anomalous iteration, which matters for the last iteration of a loop.
A mispredicted branch costs the whole pipeline depth - every speculatively fetched instruction must be discarded. In a deep modern pipeline that is 15–20 cycles.

The memory hierarchy and cache

Level	Typical size	Typical latency	Managed by
Registers	~1 KB	0 cycles	Compiler
L1 cache	32–64 KB	~4 cycles	Hardware
L2 cache	256 KB–1 MB	~12 cycles	Hardware
L3 cache	8–32 MB	~40 cycles	Hardware
Main memory (DRAM)	8–64 GB	~200 cycles	OS
SSD	256 GB–4 TB	~100 μs	OS
Hard disk	1–20 TB	~10 ms	OS

Each level down is roughly 10× larger, 10× slower and cheaper per byte. Note the gap between L3 and DRAM - that is the cliff caches exist to avoid.

Mapping	A memory block may go	Lookup cost	Conflict misses
Direct mapped	In exactly one line	Cheapest - check one line	Frequent - two hot blocks mapping to one line thrash
Fully associative	In any line	Most expensive - compare all tags	None
N-way set associative	In any of N lines within one set	Compare N tags	Rare; the practical compromise (typically 4–16 way)

AMAT = hit time + miss rate \times miss penalty

Average Memory Access Time. Note that reducing the miss rate is only one of three levers - hit time and miss penalty matter equally.

Write policy	On a write hit	Trade-off
Write-through	Write to cache and memory simultaneously	Memory always consistent; higher write traffic. Usually paired with a write buffer
Write-back	Write only to cache; mark the line dirty and flush on eviction	Much less memory traffic; memory is temporarily stale, which complicates multiprocessor coherence

I/O and interrupts

Technique	How data moves	CPU involvement	Suits
Programmed I/O (polling)	The CPU repeatedly checks a status register	Total - the CPU is fully occupied waiting	Very simple or very fast devices
Interrupt-driven I/O	The device signals when ready; the CPU handles it then	Per transfer unit	Moderate-rate devices - keyboard, mouse
DMA	A DMA controller moves data directly between device and memory	Only at start and finish	High-throughput devices - disk, network, GPU

Measuring performance

CPU time = Instruction count \times CPI \times Clock cycle time

The three factors, and the three things any optimisation must move. A compiler change alters instruction count; an architecture change alters CPI; a process shrink alters cycle time.

Amdahl's law

Speedup = \frac{1}{( 1 - P ) + \frac{P}{N}}

P is the parallelisable fraction, N the number of processors. As N → ∞, speedup approaches 1/(1−P).

Plain textWhat Amdahl's law actually tells you

A program is 90% parallelisable (P = 0.9):
   4 cores:    1 / (0.1 + 0.9/4)   = 3.08x
  16 cores:    1 / (0.1 + 0.9/16)  = 6.40x
 100 cores:    1 / (0.1 + 0.9/100) = 9.17x
   infinite:   1 / 0.1             = 10.00x  <- the hard ceiling

The 10% serial portion caps you at 10x no matter how many cores
you buy. Doubling cores from 16 to 32 buys far less than doubling
from 2 to 4 - this is why "just add more cores" stops working.

Flynn's taxonomy	Instruction streams	Data streams	Example
SISD	One	One	Classic uniprocessor
SIMD	One	Many	Vector units (SSE, AVX, NEON), GPUs
MISD	Many	One	Rare - fault-tolerant redundant systems
MIMD	Many	Many	Multicore CPUs, clusters

Computer Architecture & Organization

If you remember nothing else

Number representation

IEEE 754 floating point

Von Neumann architecture and the instruction cycle

Instruction sets and addressing modes

Pipelining and hazards

The memory hierarchy and cache

I/O and interrupts

Measuring performance

Amdahl's law

Self-check

Computer Architecture & Organization

If you remember nothing else

Number representation

IEEE 754 floating point

Von Neumann architecture and the instruction cycle

Instruction sets and addressing modes

Pipelining and hazards

The memory hierarchy and cache

I/O and interrupts

Measuring performance

Amdahl's law

Self-check

Computer Architecture & Organization

If you remember nothing else

1Number representation

IEEE 754 floating point

2Von Neumann architecture and the instruction cycle

3Instruction sets and addressing modes

4Pipelining and hazards

5The memory hierarchy and cache

6I/O and interrupts

7Measuring performance

Amdahl's law

Computer Architecture & Organization

If you remember nothing else

1Number representation

IEEE 754 floating point

2Von Neumann architecture and the instruction cycle

3Instruction sets and addressing modes

4Pipelining and hazards

5The memory hierarchy and cache

6I/O and interrupts

7Measuring performance

Amdahl's law

Number representation

Von Neumann architecture and the instruction cycle

Instruction sets and addressing modes

Pipelining and hazards

The memory hierarchy and cache

I/O and interrupts

Measuring performance

Number representation

Von Neumann architecture and the instruction cycle

Instruction sets and addressing modes

Pipelining and hazards

The memory hierarchy and cache

I/O and interrupts

Measuring performance