Instruction set
The opcodes, encodings, and operations the processor can execute.
Instructions to memory
Computer Organization
Follow one instruction from its software-visible contract through the datapath, cache hierarchy, address translation, and physical memory.
Reason cycle by cycle, calculate the cost of misses and stalls, and explain why each implementation choice changes performance or correctness.
Updated July 20266 connected chaptersInteractive labs + worked examples
One instruction, every layer
Trace a load from opcode to physical data.
Cold-path lensTLB miss + L1 miss
- ISSUE
- LW x5,24(x2)
- BASE
- x2 = 0x00008130
- VA
- 0x00008148
- VPN / OFFSET
- 0x8 / 0x148
- L1 SET / BYTE
- 05 / 08
- PPN
- 0x1A3
- PA
- 0x001A3148
- REFILL LINE
- 0x001A3140
Core · cycles 1–4
MEM · parallel lookup
The trace assumes a 4 KiB page, 32 KiB 8-way VIPT L1, 64-byte lines, and a 40-bit physical address. The set read begins with page-offset bits while translation proceeds. Candidate data remains unusable until the physical tag and permissions arrive.
Latency note: a cold four-level walk plus DRAM refill can cost hundreds of cycles. Exact latency depends on cached PTEs, lower-level hits, memory-level parallelism, and the machine's miss machinery.
Instruction set architecture
The contract software sees.
An ISA defines program-visible behavior. Microarchitecture decides how a particular processor fulfills that contract.
Visible registers
General-purpose and special registers software can name and manipulate.
Addressing modes
Immediate, register-relative, PC-relative, and other ways to identify operands.
Data types
Supported widths and formats, such as bytes, words, integers, and floating point.
RISC
Regular operations, pipeline-friendly control.
- Smaller set of simpler instructions
- Often fixed-length encodings
- Explicit load/store memory operations
- More sequencing responsibility for compilers
CISC
Expressive instructions, more complex decode.
- Larger and more varied instruction repertoire
- Often variable-length encodings
- Some instructions combine memory and computation
- Complex work may be translated into internal micro-operations
End-to-end system map
Follow one load from instruction bits to returned data.
The ISA defines what LW means. The pipeline calculates its virtual address, translation supplies a physical address, the hierarchy locates the line, and WB makes the loaded value visible in the destination register.
Instruction and control
ISA contractLW r1, 0(r2)→IFPC → instruction→IDdecode + read r2→EXr2 + immediate→MEMtranslate + load→WBwrite data to r1
Address and data
Virtual addressVPN | offset→TLB / MMUVPN → PPN + permissions→Physical addressPPN | offset→L1 data cachetag + set lookup→L2 / L3next-level lookup→DRAMline refill on miss
Branch feedback EX redirects the next-PC mux when prediction is wrong.Operand feedback EX/MEM/WB forwarding can bypass the register file.Miss behavior A blocking core holds the pipe; a non-blocking cache tracks the request in an MSHR.
Classic datapath
Overlap work without changing program meaning.
A classic MIPS-style pipeline partitions instruction work across five stages. Pipeline registers hold each instruction's control and data between stages.
Instruction fetch
Read the instruction at the program counter and choose the next PC.
Decode and register read
Decode the opcode, identify operands, and read the register file.
Execute
Run the ALU, compare a branch, or calculate an effective address.
Memory
Access the data cache for a load or store.
Write back
Commit an ALU or load result into the architectural register file.
IFPC + instruction memoryIF / ID→IDControl + register file + sign extendID / EX→EXALU + branch compareEX / MEM→MEMData cacheMEM / WB→WBResult mux + register write
Control signals travel with the instruction. Forwarding paths return fresh EX or MEM results to ALU inputs; branch resolution redirects the PC; WB closes the loop at the register file.
Next-PC muxPC + 4 or resolved branch targetALU-input muxRegister value or sign-extended immediateBranch decisionCompare result gates the target selectionWrite-back muxALU result or loaded memory data
Interactive pipeline timeline
See overlap, bubbles, bypasses, and flushes cycle by cycle.
Independent instructions enter on consecutive cycles. Latency remains five cycles, but steady-state throughput reaches one completed instruction per cycle.
Instruction
ADD r1,r2,r3IFIDEXMEMWB
AND r4,r5,r6IFIDEXMEMWB
OR r7,r8,r9IFIDEXMEMWB
XOR r10,r11,r12IFIDEXMEMWB
Cycle 1ADD r1,r2,r3: IF
No dependency or resource conflict requires a bubble.
Active stageForwarded valueStall or resource conflictFlushed work
Pipeline hazards
When the next instruction cannot safely advance.
A hazard is a timing condition, not automatically a bug. The interlock, bypass, and recovery machinery must preserve architectural behavior.
Structural hazard
Two stages request hardware that cannot serve both in the same cycle.
Resolve with replication, multi-porting, arbitration, or a stall.Data hazard
A consumer reaches its operand-use point before the producer's result is available.
Forward when timing permits; otherwise interlock and inject a bubble.Control hazard
A branch or exception makes already-fetched instructions potentially incorrect.
Predict to stay busy, then flush and redirect when the guess is wrong.RAW dependency
ADD r1, r2, r3
SUB r4, r1, r5Load-use boundary
LW r1, 0(r2)
ADD r3, r1, r4The ADD result exists after EX and can bypass to the next EX. The load result exists only after MEM, so an adjacent consumer needs one bubble in this five-stage timing model.
Register-file edge case
Instruction i writes while i+3 reads.
IFi+4IDSUB i+3read R1EXi+2MEMi+1WBADD iwrite R1
The ISA only requires the SUB to observe the ADD result. The register-file circuit decides whether that same-cycle read is write-first, read-first, or unsupported. A half-cycle convention or WB-to-ID bypass avoids a bubble; a read-first single-port implementation must interlock.
Interview reasoning
Locate the boundary before naming the fix.
- 1
Produce: At which stage and edge does the value or decision become valid?
- 2
Consume: At which stage and edge must the younger instruction sample it?
- 3
Transport: Is there a bypass or port connecting those two points in time?
- 4
Hold: Which pipeline registers freeze, and where is the bubble inserted?
- 5
Recover: Which younger side effects must be killed after a redirect?
Common implementation failuresForwarding from the wrong producer when two older instructions target the same registerFreezing the PC but not IF/ID, which duplicates an instructionFlushing data while a wrong-path store-enable or register-write control bit survives
Reason aloud
Questions that expose the timing model
Why can forwarding not completely remove a load-use hazard?+
A load receives its data at the end of MEM, while the following instruction needs the operand at the beginning of EX in that same cycle. The value arrives after the consumer's sampling boundary, so the pipeline stalls once and then forwards it.
What this tests: Stage timing, not merely the definition of a RAW dependency.How do pipeline latency and throughput differ?+
Latency is the time for one instruction to pass from IF through WB. Throughput is the completion rate across many overlapped instructions. A five-stage pipeline can retain five-cycle latency while approaching one instruction per cycle after filling.
What this tests: Whether the candidate separates per-item delay from system rate.Can ID read and WB write the same register in one cycle?+
Instruction i can write r1 in WB while instruction i+3 reads r1 in ID. This is not an architectural WAR hazard. It is a same-cycle register-file timing or port conflict if the implementation returns old data or cannot perform both operations. A write-first array, first-half write plus second-half read, or explicit WB-to-ID bypass removes the stall; otherwise ID waits one cycle.
What this tests: The difference between an ISA dependency and a microarchitectural resource constraint.Where does a one-port unified L1 cache create a structural hazard?+
When a load or store reaches MEM, a younger instruction simultaneously needs the only port for IF. The processor must choose one request, normally the older data access, and hold the PC and fetch stage until the port becomes free.
What this tests: Resource occupancy across stages.Pipeline performance
2.5 GHz benchmark
40% ALU, 25% branch, 20% load, 15% store.
Branch cost0.25 × 0.20 × 3 = 0.15 CPI
Load-use cost0.20 × 0.30 × 1 = 0.06 CPI
Effective resultCPI 1.21 · 2,066 MIPS
Memory hierarchy
Keep the common case close to the core.
Registers, SRAM caches, DRAM, and storage trade capacity for latency and cost. Caches work because access patterns exhibit temporal and spatial locality.
Registerssmallest · fastestL1SRAM · core localL2 / L3larger · slowerDRAMmain memorySSD / storagelargest · slowest
Recently used data is likely to be used again. Loops and accumulators are common examples.
Nearby addresses are likely to be used. A cache line fetches a neighborhood, often 64 bytes.
Identifies which memory block currently occupies the selected way.
Selects a set, reducing the number of tag comparisons.
Selects the byte or word within the cache line.
Cache address explorer
Split a physical address and size the tag array.
Tag17 bitsSet index11 bitsBlock offset6 bits
Cache lines16,384
Sets2,048
Tag + valid storage288 Kibit
Storage in bytes36 KiB
Address 0x1234ABCD selects set 687 of 2,048, byte offset 13, and compares tag 0x91A against 8 ways.
Accuracy note: PIPT tags use the physical address width. The source gives a 32-bit virtual address but not the physical width. Its requested 17-bit tag and 288 Kibit tag array imply a 34-bit physical address. If the physical address is 32 bits, the correct result is a 15-bit tag and 256 Kibit, or 32 KiB, including one valid bit per line.
Placement
Associativity chooses how many homes a block may use.
Direct mapped
One possible line per index. Fast and compact, but vulnerable to conflicts.
Set associative
N candidate ways in one set. Parallel tag checks trade power for fewer conflicts.
Fully associative
Best placement freedom, but every tag may need comparison. Practical for small structures.
Compulsory miss
Cause: The block has never been fetched.
Response: Prefetch useful streams or use a larger line when spatial locality justifies it.
Larger lines can waste bandwidth and pollute the cache.Conflict miss
Cause: Active blocks compete for the same set even while other sets have space.
Response: Increase associativity or improve placement and indexing.
More ways add tag comparisons, power, mux delay, and replacement state.Capacity miss
Cause: The working set exceeds the cache's usable capacity.
Response: Increase cache capacity or reduce the software working set.
A larger cache costs area and can lengthen hit latency.Coherence miss
Cause: Another agent's write invalidates the local copy.
Response: Reduce writable sharing and false sharing; use an appropriate coherence protocol.
This miss reflects inter-core communication, not only local placement.| Parameter | Choice | Performance benefit | Cost and complexity |
|---|---|---|---|
| Capacity | Small ↔ large | Larger capacity reduces capacity misses and holds a bigger working set. | More area and leakage; longer wires can increase hit time. |
| Associativity | Direct ↔ N-way ↔ fully associative | More ways reduce conflict misses. | More comparators, replacement metadata, mux delay, power, and verification. |
| Line size | 16 B ↔ 64 B ↔ 128 B | Larger lines exploit spatial locality, amortize refill overhead, and need fewer tag entries. | Longer refill latency, more bandwidth, pollution, and false sharing. |
| Write policy | Write-through ↔ write-back | Write-through simplifies lower-level visibility; write-back bundles repeated writes. | Write-through needs bandwidth and usually a write buffer. Write-back needs dirty state and reliable eviction. |
VIPT L1 cache
Index while translation runs.
A virtually indexed, physically tagged cache uses page-offset bits to select a set in parallel with the TLB lookup, then compares translated physical tags. This removes serial TLB-plus-cache latency.
The synonym problem
Two virtual addresses can map to one physical page. If their index bits differ, duplicate copies could occupy different sets. Keep index plus offset within the page offset, commonly expressed as cache capacity divided by associativity no larger than page size. Page coloring and explicit alias handling cover designs that exceed this constraint.
Non-blocking cache
Keep independent work moving.
MSHRs record each outstanding line, request type, destination, and waiting consumers. They enable hit-under-miss, merge requests to the same line, and allow multiple independent misses.
Where it matters
A long DRAM miss need not block an unrelated L1 hit. Several concurrent misses can overlap until MSHRs, fill buffers, memory-level parallelism, or bandwidth become the new limit. When all MSHRs are occupied, new misses must stall.
Parallel lookup
A VIPT cache spends the page offset twice.
One branch translates the VPN. The other uses untranslated page-offset bits to start the SRAM read. They meet at the physical-tag comparison, so no data becomes valid before translation and permission checks finish.
Virtual page numberVPNPage offset, unchanged by translationset index | line offset
Translation pathVPN + ASIDTLB lookup→TLB hitPPN + permissions→From PAphysical tag
SRAM pathOffset bitschoose cache set→All waysread tags + data→Way candidatesN tags + N data lines
Translated physical tagcompare against every candidate way×Selected cache setstored tag + valid + data→Resulthit way + requested bytes
Fast hit: TLB and set read overlap.TLB miss: hold candidate data until the page walk completes.Alias risk: if set-index bits leave the page offset, synonyms may select different sets.
Design intuition
Fast structures work because a hidden invariant stays true.
Fast path
Use virtual page-offset bits to index the set while the TLB produces the physical tag.
Invariant
Every index bit used before translation must be unchanged by translation.
Failure signature
Synonyms create duplicate physical lines in different sets, producing stale copies.
Fast path
Track an outstanding line and let independent hits or misses continue.
Invariant
Every waiter links to one fill, and same-line requests merge without a duplicate refill.
Failure signature
A lost waiter never wakes; a premature free misroutes data; full MSHRs apply backpressure.
1Lookup missesline address→2Allocate or mergewaiters + destination→3Issue lower readone request per line→4Install and wakefill + replay→5Retire MSHRafter consumers resolve
AMAT calculator
Price every miss at the level where it occurs.
AMAT = tL1 + mL1 × (tL2 + mL2 × tDRAM)2 + 0.1 × (10 + 0.2 × 60)
4.2 nsAMAT is 4.2 ns. L1 contributes 2 ns, L2 contributes 1 ns, and DRAM contributes 1.2 ns. L1 lookup is the largest contribution.
What happens on a cache read miss?
Allocate miss-tracking state, select a victim, write back a dirty victim if needed, request the line from the next level, install data and tag, update replacement state, then wake or replay the waiting load.
How does associativity reduce conflict misses?
Blocks with the same index can coexist in different ways. It does not remove compulsory or capacity misses, and the extra ways increase lookup cost.
Virtual memory
Translate, protect, and share physical memory.
Each process sees a private, contiguous virtual address space. The operating system owns mappings; the MMU enforces them on every instruction fetch, load, and store.
Protection
Per-page read, write, execute, privilege, and validity bits block unauthorized access.
Contiguous view
Virtual pages map onto fragmented physical frames without changing program addresses.
Demand and sharing
Pages can be created on demand, swapped to storage, shared, or privately copied on write.
Virtual addressVirtual page numberPage offset
↓ MMU + page tablePhysical addressPhysical page numberSame page offset
Virtual pages and physical frames have equal size. The OS stores page-table entries in memory; a hardware or software walker follows the hierarchy from a per-process root to a leaf PTE. The leaf supplies the PPN, permissions, accessed/dirty state, and validity.
L4 index9 bitsL3 index9 bitsL2 index9 bitsL1 index9 bitsPage offset12 bits
Root registerpage-table base→L4 PTEnext table→L3 PTEnext table→L2 PTEnext table→L1 leafPPN + permissions
Each nine-bit index selects one of 512 entries. With eight-byte PTEs, one level's 512 entries occupy exactly one 4 KiB page. The 12-bit offset never participates in the walk and is copied unchanged into the physical address.
Virtual-address journey
Trace translation separately from the data access.
Step 1 of 4
CPU issues a virtual address
VPN | page offsetThe page offset is already final. Only the virtual page number needs translation.
TLB miss
A miss is not necessarily a fault.
The walker reads page-table levels. A valid leaf refills the TLB and retries the access. An absent, invalid, or disallowed mapping raises a page fault. The OS may allocate a page, fetch it from storage, update the PTE, and restart the instruction.
Process protection
Check permission before touching data.
The TLB caches translation and permission state. Address-space identifiers prevent mappings from different processes from matching accidentally. Privilege and R/W/X checks occur before the cache can architecturally modify memory.
Interview diagnosis
Three misses, three different meanings.
| Event | What is absent | Normal next action | Architectural visibility |
|---|---|---|---|
| TLB miss | A cached translation | Walk the page table, refill the TLB, retry | Usually a hidden performance event |
| Page fault | A valid or permitted mapping | Enter the OS; allocate, load, reject, or update policy | Precise exception at the faulting instruction |
| Cache miss | The translated data line | Fetch from the next memory-hierarchy level | Normally hidden unless a machine error occurs |
First: Did translation match?Second: Do permissions allow this access?Third: Where is the translated data?ASID reuse: Invalidate old entries or pair the ASID with a generation.
TLB coherence
Changing a PTE is only the first half of the update.
Private TLBs may retain stale permissions or a stale frame number. The OS must complete a coordinated shootdown before reusing the frame or trusting the new policy.
- 1
Lock the mapping and update or invalidate the page-table entry.
- 2
Issue inter-processor interrupts to cores that may cache the mapping.
- 3
Each target invalidates the matching TLB entry and executes required barriers.
- 4
Targets acknowledge; the initiating core can safely continue and reclaim resources.
Large and huge pages
Multiply TLB reach.
One TLB entry maps 2 MiB or 1 GiB instead of 4 KiB, reducing TLB misses and page-walk traffic for large, contiguous working sets.
- Memory utilization: internal fragmentation wastes the unused portion of a large page.
- OS management: contiguous physical allocation is harder and may require compaction.
- Operational cost: promotion, demotion, copy-on-write, migration, and swapping move more data.
- Granularity: protection and sharing decisions apply to a larger region.
Worked problems
Carry the probability through the hierarchy.
State the timing convention, convert percentages to probabilities, and multiply a penalty only by the fraction of instructions or accesses that actually pay it.
Pipeline CPI and MIPS
CPI = 1 + 0.25(0.20)(3) + 0.20(0.30)(1)Branch misses add 0.15 CPI. Load-use stalls add 0.06 CPI.
CPI = 1.21MIPS = 2,500 MHz / 1.21 = 2,066.12Three-level AMAT tradeoff
2 + 0.10(10 + 0.20 × 60) = 4.2 nsWith the proposed slower but higher-hit L2:
2 + 0.10(12 + 0.05 × 60) = 3.5 nsThe proposal improves AMAT by 0.7 ns, or 16.7%.1 MiB, 8-way, 64-byte PIPT tag array
lines = 2²⁰ / 2⁶ = 2¹⁴
sets = 2¹⁴ / 2³ = 2¹¹
offset = 6 bits · index = 11 bitsFor the source's implied 34-bit physical address, tag = 34 − 11 − 6 = 17 bits. Including one valid bit per line:
(17 + 1) × 2¹⁴ = 294,912 bits288 Kibit = 36 KiBWrite-back L1, write-through L2 CPI
memory-op fraction = 0.20 + 0.10 = 0.30expected data time = 0.30 × [2 + 0.10(15 + 0.20×70 + 0.40×15)] = 1.65 ns/instructionThe prompt supplies nanoseconds but no processor clock period, so a unique CPI cannot be derived. For clock period T in ns:
CPI = 1 + 1.65 / TAt T = 1 ns, CPI = 2.65. If the base pipeline already includes the 2 ns L1 hit, count only miss overhead: CPI = 1 + 1.05/T, or 2.05 at T = 1 ns.Four-level page-table EMAT
The translated 48-bit virtual address splits into four nine-bit indexes and a 12-bit offset. A 40-bit physical address has a 28-bit PPN plus that offset. Eight-byte PTEs make each 512-entry page-table level exactly 4 KiB.
translation = 1 + 0.01(4 × 100) = 5 cyclesdata access = 1 + 0.05(100) = 6 cyclesA TLB miss pays four uncached PTE reads. The subsequent L1 lookup still occurs, and an L1 miss pays one DRAM access. This exercise uses the source's serial TLB-then-cache timing model; a VIPT implementation may overlap part of those hit paths.
EMAT = 5 + 6 = 11 cyclesReasoning checkpoints
Questions worth answering without notes.
Each answer states the mechanism first, then the consequence.01Why can forwarding not completely remove a load-use hazard?+
A load produces its value only after the memory stage, while the immediately following instruction needs that operand at the start of execute. Even a direct MEM-to-EX bypass arrives too late for the same cycle, so the dependent instruction stalls for one cycle.
02How does associativity reduce conflict misses?+
Associativity gives every index multiple candidate lines. Addresses with the same index can coexist in different ways instead of repeatedly evicting one another, at the cost of more tag comparisons, replacement state, power, and often hit latency.
03What happens on a TLB miss?+
The processor or operating system walks the page-table hierarchy using the virtual-page number. A valid leaf supplies the physical-page number and permissions, the translation is installed in the TLB, and the original access restarts. An invalid or disallowed entry raises a page fault or protection exception.
Keep practicing
Move from recognition to explanation.
These links open the existing practice bank without publishing protected solutions on this guide.Continue the system
Connect the adjacent layer.
Parallel work to precise stateComputer ArchitectureSee how a modern processor finds parallel work, predicts control flow, executes speculatively, and still presents precise sequential behavior.Open guide →Logic to reliable timingDigital DesignConnect logic behavior to its physical timing contract, then choose safe structures for paths that cross cycles, clocks, and module boundaries.Open guide →