Computer Architecture Interview Questions

How to use this page

This is the revision page for the Computer Architecture track. It collects the questions most commonly asked in campus placements, written tests and technical interviews for software roles, grouped by topic in the same order as the lessons. Each answer is short enough to say aloud in under a minute; each group links back to the lesson that explains the topic in depth.

The second half has 10 numerical problems of the kinds that appear in written tests and interviews: CPI and execution time, Amdahl's law, IEEE 754 conversion, cache address breakdown, AMAT, pipeline speedup and TLB effective access time. Every answer was checked with a short Python script. Work each one on paper before reading the solution.

Interviewers for software roles rarely want circuit-level detail. What they probe is whether you understand why hardware behaves as it does and can connect it to code: why a cache-friendly loop is faster, why a pipeline stalls, what a TLB miss costs, why threads that share a cache line slow down. When you answer, give the definition, the reason it exists, and one concrete example.

Fundamentals and performance

Revise with COA introduction.

Q1. What is the difference between computer architecture and computer organisation?

Architecture is what the programmer sees: the instruction set, data types, registers, addressing modes and memory model. Organisation is how that architecture is implemented: pipelines, caches, buses and control units. Two processors can share an architecture (both run x86-64) but differ greatly in organisation.

Q2. What is the von Neumann architecture, and what is the von Neumann bottleneck?

It is the stored-program design where instructions and data live in the same memory and travel over the same path to a CPU that fetches, decodes and executes them one after another. The bottleneck is that this single path between CPU and memory limits throughput, because the processor can compute much faster than memory can supply instructions and data. Caches, wider buses and prefetching all attack it.

Q3. Harvard versus von Neumann?

Harvard architecture has separate memories and buses for instructions and data, so an instruction fetch and a data access can happen at the same time. Von Neumann uses one shared memory. Modern CPUs are a modified Harvard design: split L1 instruction and data caches backed by a unified memory.

Q4. What is the iron law of performance?

CPU time = instruction count × CPI × clock cycle time. Instruction count depends on the algorithm, compiler and ISA, CPI on the microarchitecture and memory behaviour, and cycle time on the hardware. Comparing processors by clock speed alone ignores the other two factors.

Q5. What is CPI, and how do you compute average CPI for an instruction mix?

CPI is the average number of clock cycles per instruction. For a mix, weight each class's CPI by its fraction of executed instructions and sum: for example 50 percent ALU at 1 cycle and 50 percent loads at 3 cycles gives 0.5 × 1 + 0.5 × 3 = 2.

Q6. Why is MIPS a misleading metric?

MIPS (millions of instructions per second) ignores how much work each instruction does, so a machine with simpler instructions can show a higher MIPS rating while taking longer to run the same program. It also varies with the program. Execution time on real workloads is the only reliable comparison.

Q7. Why did clock frequencies stop rising around the mid-2000s?

Dynamic power grows roughly with capacitance × voltage squared × frequency, and once voltage could no longer be lowered with each process shrink (the end of Dennard scaling), higher frequencies produced more heat than chips could dissipate. Designers turned to parallelism instead: wider cores, multiple cores and vector units.

Data representation

Revise with data representation.

Q8. Why do computers use two's complement for signed integers?

It has a single representation of zero, and the same adder circuit handles addition and subtraction of signed and unsigned numbers. Negating is "invert all bits and add 1". An n-bit two's complement number ranges from −2^(n−1) to 2^(n−1) − 1, for example −128 to 127 for 8 bits.

Q9. How do you detect overflow in two's complement addition?

Overflow occurs when adding two numbers of the same sign gives a result of the opposite sign; adding numbers of different signs can never overflow. In hardware, overflow equals the carry into the sign bit XOR the carry out of the sign bit.

Q10. What is the difference between overflow and carry?

The carry flag reports an unsigned overflow: a carry out of the most significant bit. The overflow flag reports a signed overflow: the result does not fit in the signed range. For 8 bits, 200 + 100 sets carry (unsigned result too large) while 100 + 100 sets overflow (signed result exceeds 127).

Q11. Explain the IEEE 754 single-precision format.

32 bits: 1 sign bit, 8 exponent bits stored with a bias of 127, and 23 fraction bits. A normal value equals (−1)^sign × 1.fraction × 2^(exponent − 127); the leading 1 is implicit. Exponent all zeros encodes zero and denormals; all ones encodes infinity (fraction zero) or NaN (fraction non-zero).

Q12. Why does 0.1 + 0.2 != 0.3 in most languages?

0.1, 0.2 and 0.3 have no exact binary representation, just as 1/3 has none in decimal, so each is rounded to the nearest double. The rounding errors do not cancel, and the computed sum differs from the stored 0.3 in the last bit. Compare floating-point values with a tolerance, or use decimal types for money.

Q13. What is endianness?

The order in which a multi-byte value's bytes are stored in memory. Big-endian stores the most significant byte at the lowest address; little-endian stores the least significant byte first. x86 and most ARM systems run little-endian; network protocols use big-endian (network byte order), which is why htonl-style conversions exist.

Digital logic

Revise with digital logic.

Q14. Why are NAND and NOR called universal gates?

Any Boolean function can be built from NAND gates alone, or from NOR gates alone, because each can produce NOT, AND and OR. For example, NOT A = A NAND A, and A AND B = NOT (A NAND B).

Q15. Combinational versus sequential circuits?

A combinational circuit's output depends only on its current inputs (adders, multiplexers, decoders). A sequential circuit's output also depends on stored state, so it contains memory elements such as flip-flops (registers, counters, finite-state machines).

Q16. Latch versus flip-flop?

A latch is level-sensitive: while its enable is active, the output follows the input. A flip-flop is edge-triggered: it captures the input only at a clock edge. Synchronous designs mostly use flip-flops so that all state changes happen at a single, well-defined instant.

Q17. What do a multiplexer and a decoder do?

A multiplexer selects one of 2^n inputs to pass to its output using n select lines, like a hardware switch. A decoder takes an n-bit code and activates exactly one of 2^n outputs, used for example to select one memory chip or one register.

Q18. What limits how fast a ripple-carry adder can run, and how is it fixed?

Each bit's carry depends on the previous bit's carry, so the carry ripples through all n bits and delay grows linearly with width. A carry-lookahead adder computes generate and propagate signals to determine carries in parallel, reducing delay to roughly logarithmic in the width.

Instruction set architecture

Revise with instruction set architecture.

Q19. RISC versus CISC?

RISC uses a small set of simple, fixed-length instructions with a load-store design (only loads and stores touch memory), which makes pipelining easy; examples are ARM and RISC-V. CISC has many variable-length instructions, some of which do memory access and computation together; x86 is the main example. Modern x86 chips translate instructions into RISC-like micro-ops internally, so the distinction is now mostly about the ISA, not the core.

Q20. What is a load-store architecture?

An ISA in which arithmetic instructions operate only on registers, and only explicit load and store instructions access memory. It simplifies decoding and pipelining and is the defining feature of RISC ISAs.

Q21. Name common addressing modes with examples.

Immediate (the operand is in the instruction: add r1, r1, 5), register (add r1, r2, r3), direct or absolute (address in the instruction), register indirect (address in a register: load r1, [r2]), base plus displacement (load r1, [r2 + 8], used for struct fields and stack variables), indexed (base plus index register, for arrays) and PC-relative (used for branches and position-independent code).

Q22. What is the difference between a stack, accumulator and register-register (general-purpose register) ISA?

A stack ISA takes operands implicitly from the top of a stack (the JVM bytecode is an example). An accumulator ISA has one implicit register for one operand and the result. A general-purpose register ISA names its operands explicitly in registers; nearly all modern CPUs use it because registers are fast and compilers can allocate them well.

Q23. Why do ISAs have a fixed number of registers, and what happens when you run out?

Register count is part of the instruction encoding (5 bits per operand gives 32 registers) and more registers make the register file slower and larger. When a function needs more live values than registers, the compiler spills some to the stack, costing loads and stores. Out-of-order cores add many more physical registers internally via renaming.

Q24. What does a calling convention specify?

How arguments and return values are passed (which registers, then the stack), which registers the callee must preserve, how the stack frame is laid out and aligned, and who cleans up the stack. It lets separately compiled code, including libraries and the OS, call each other correctly.

Q25. What are R-type, I-type and J-type formats in MIPS-style ISAs?

R-type instructions name three registers (two sources and a destination) plus a function code, used for arithmetic. I-type instructions have two registers and a 16-bit immediate, used for immediates, loads, stores and conditional branches. J-type instructions hold a large jump target. Fixed formats keep the decoder simple and fast.

CPU datapath and control

Revise with CPU datapath and control.

Q26. What are the steps of the instruction cycle?

Fetch the instruction from memory at the PC and increment the PC; decode it and read registers; execute it in the ALU; access memory if it is a load or store; write the result back to a register. Interrupts are checked between instructions.

Q27. What do the PC, IR, MAR and MDR registers hold?

The program counter holds the address of the next instruction; the instruction register holds the instruction being decoded; the memory address register holds the address being accessed; the memory data register holds the data read from or to be written to memory.

Q28. Hardwired versus microprogrammed control?

Hardwired control generates control signals with fixed combinational logic or a finite-state machine, which is fast but hard to change. Microprogrammed control stores the control signals for each step as microinstructions in a control memory, which is slower but easier to design, modify and extend for complex instruction sets.

Q29. Single-cycle versus multi-cycle datapath?

A single-cycle datapath completes every instruction in one long clock cycle sized for the slowest instruction (usually a load), wasting time on fast ones. A multi-cycle datapath splits execution into shorter steps, letting each instruction take only as many cycles as it needs and reusing units such as the ALU across steps.

Pipelining

Revise with pipelining.

Q30. What is pipelining, and does it reduce instruction latency?

Pipelining overlaps the stages of successive instructions, like an assembly line, so ideally one instruction completes per cycle. It improves throughput, not latency: each instruction still passes through every stage, and pipeline register overhead makes its individual latency slightly longer.

Q31. What is the ideal speedup of a k-stage pipeline, and why is it not reached?

For n instructions, speedup = n × k ÷ (k + n − 1), which approaches k for large n. It is not reached because stages are unbalanced (the clock is set by the slowest), pipeline registers add delay, and hazards cause stalls.

Q32. What are the three types of hazards?

Structural hazards occur when two instructions need the same hardware resource in the same cycle. Data hazards occur when an instruction needs a result that a previous instruction has not produced yet. Control hazards occur when the next instruction to fetch depends on a branch that has not resolved.

Q33. What is forwarding (bypassing)?

Sending a result directly from the output of the stage that produces it (for example the ALU output in the pipeline register) to the input of the stage that needs it, instead of waiting for it to be written to the register file. It removes most data-hazard stalls between ALU instructions.

Q34. What is a load-use hazard, and why can forwarding not remove it completely?

When an instruction uses a register immediately after a load writes it, the loaded value is only available at the end of the memory stage, but the next instruction needs it at the start of its execute stage. Forwarding cannot send data backwards in time, so one bubble is needed in a classic 5-stage pipeline. Compilers schedule an independent instruction into that slot when they can.

Q35. Name the three data dependence types.

RAW (read after write) is a true dependence and must be respected. WAR (write after read) and WAW (write after write) are name dependences caused by reusing register names; they matter in out-of-order pipelines and are removed by register renaming.

Q36. How are control hazards handled?

By stalling until the branch resolves, by resolving branches earlier in the pipeline, by predicting the outcome (static such as "backward taken, forward not taken", or dynamic with branch history tables and BTBs) and flushing on a misprediction, or historically with delayed branches where the instruction after the branch always executes.

Q37. How does a 2-bit branch predictor work?

Each entry is a saturating counter with four states: strongly and weakly not taken, weakly and strongly taken. It predicts taken in the upper two states and changes state by one step per outcome, so a single unusual outcome (such as a loop exit) does not flip a strong prediction.

Cache memory

Revise with cache memory.

Q38. What are temporal and spatial locality?

Temporal locality: a location accessed now is likely to be accessed again soon (loop variables, hot functions). Spatial locality: locations near a recently accessed one are likely to be accessed soon (array elements, sequential code). Caches keep recent data for the first and fetch whole blocks for the second.

Q39. How do you split an address into tag, index and offset?

Offset bits = log2(block size). Index bits = log2(number of sets), where sets = cache size ÷ (block size × associativity). Tag bits = address width − index − offset. A fully associative cache has no index bits.

Q40. Compare direct-mapped, set-associative and fully associative caches.

Direct-mapped allows each block in exactly one line: fastest and simplest, but suffers conflict misses. Fully associative allows any line: no conflict misses but needs a comparator per line, so it is used only for small structures like TLBs. N-way set-associative is the practical compromise used by real L1, L2 and L3 caches.

Q41. What are the 3 Cs of cache misses?

Compulsory misses happen on the first access to a block; capacity misses happen because the working set exceeds the cache; conflict misses happen because too many blocks map to the same set. Multiprocessors add coherence misses, caused by invalidations from other cores.

Q42. Write-through versus write-back?

Write-through updates memory on every write, keeping it current but using lots of bandwidth (a write buffer hides the latency). Write-back updates only the cache and marks the line dirty, writing it to memory once when evicted. Modern data caches are write-back, usually paired with write-allocate.

Q43. What is AMAT?

Average memory access time = hit time + miss rate × miss penalty. With multiple levels, the miss penalty of one level is the AMAT of the next: AMAT = L1 hit + L1 miss rate × (L2 hit + L2 local miss rate × memory time).

Q44. Which replacement policies do caches use?

LRU evicts the least recently used line; FIFO evicts the oldest fill; random picks any way; pseudo-LRU (such as tree-PLRU with N − 1 bits per set) approximates LRU cheaply and is common in hardware. Last-level caches often use adaptive policies that resist being flushed by one-time scans.

Q45. Why is traversing a 2D C array column by column slow?

C stores arrays row-major, so consecutive column elements are a full row apart in memory. Each access lands in a different cache line and uses only a few bytes of it, defeating spatial locality and prefetching; for large arrays, nearly every access misses. Making the last index the innermost loop fixes it.

Main memory and virtual memory hardware

Revise with main memory and virtual memory hardware.

Q46. SRAM versus DRAM?

SRAM stores a bit in a six-transistor latch: fast, needs no refresh, but large and expensive per bit, so it is used for caches and registers. DRAM stores a bit as charge on one capacitor with one transistor: dense and cheap but leaky, so it needs periodic refresh, and reads are destructive and slower. It is used for main memory.

Q47. Why does DRAM need refresh?

The capacitor storing each bit leaks charge, so the value fades within milliseconds. The memory controller issues refresh commands so every row is read and rewritten within the retention window, 64 ms for DDR4 at normal temperature. Rows being refreshed cannot be accessed, which costs a little bandwidth.

Q48. What is the MMU?

The memory management unit translates virtual addresses to physical addresses on every access, using the TLB and, on a miss, page-table walks. It enforces read, write, execute and user/kernel permissions and raises page faults for missing or forbidden pages.

Q49. What is a TLB and why is it needed?

A translation lookaside buffer is a small, fast cache of recent virtual-to-physical page translations. Without it every memory access would need several extra memory reads to walk the page table; with it, most translations take no extra time.

Q50. What is TLB reach, and how do huge pages help?

TLB reach is number of entries × page size, the memory accessible without a TLB miss. 1,536 entries with 4 KiB pages cover 6 MiB; with 2 MiB pages they cover 3 GiB. Huge pages greatly increase reach and shorten page walks, at the cost of coarser allocation.

Q51. Why are page tables multi-level?

A flat page table needs an entry for every virtual page, 4 MiB per process for a 32-bit space and 512 GiB for a 48-bit space with 8-byte entries. A multi-level tree only allocates the tables covering regions actually in use. The cost is one memory access per level on a TLB miss, which caches and page-walk caches reduce.

I/O organisation

Revise with I/O organization.

Q52. Memory-mapped versus isolated I/O?

Memory-mapped I/O places device registers in the physical address space so ordinary loads and stores access them; isolated I/O uses a separate address space with special instructions such as x86 IN and OUT. Memory-mapped I/O is standard for modern devices; its registers must be uncacheable and accessed through volatile in C.

Q53. Polling, interrupts or DMA: when would you use each?

Polling for very simple systems or when a device is almost always ready and latency must be minimal. Interrupts for devices that produce data occasionally, such as keyboards, so the CPU does other work meanwhile. DMA for bulk transfers such as disk and network data, so the CPU sets up the transfer and gets one interrupt at the end.

Q54. What is DMA, and what are its modes?

Direct memory access lets a controller or device move data between I/O and memory without the CPU copying each word. Burst mode holds the bus for the whole block, cycle stealing takes one bus cycle at a time, and transparent mode uses only cycles the CPU leaves idle.

Q55. What is a vectored interrupt, and what is daisy chaining?

A vectored interrupt supplies a number that indexes a table of handler addresses, so the CPU jumps directly to the right handler. Daisy chaining connects devices in series on the interrupt-acknowledge line; the first requesting device in the chain claims the acknowledgement, so priority equals position.

Q56. Why is NVMe faster than SATA?

SATA is limited to 6 Gb/s (about 600 MB/s of data) and its AHCI interface offers one queue of 32 commands, designed for hard disks. NVMe runs over several PCIe lanes with gigabytes per second of bandwidth and supports many deep queues (one per core), matching flash's parallelism with lower software overhead.

Parallelism and modern processors

Revise with parallelism and multicore and modern processors and performance.

Q57. What is Flynn's taxonomy?

A classification by instruction and data streams: SISD (one core, one data stream), SIMD (one instruction on many data elements, as in vector units), MISD (rare) and MIMD (many independent instruction streams, as in multicore CPUs and clusters).

Q58. What does out-of-order execution do, and how does it stay correct?

It executes instructions as soon as their operands are ready instead of strictly in program order, so independent work continues during stalls such as cache misses. Register renaming removes false dependences, and the reorder buffer retires instructions in program order, which keeps exceptions precise and lets mispredicted work be discarded.

Q59. What is superscalar execution?

The ability to fetch, decode, issue and complete more than one instruction per cycle using multiple parallel pipelines and execution units, giving an IPC above 1 when enough independent instructions exist.

Q60. What is SMT (hyper-threading)?

Simultaneous multithreading lets one core hold the state of two or more threads and issue instructions from them in the same cycle, filling execution slots one thread would leave idle. The threads share caches and execution units, so the gain is usually much less than a second core.

Q61. Explain cache coherence and the MESI protocol.

Coherence ensures that all cores see a consistent value for each memory location despite private caches. MESI tags each line Modified (only copy, dirty), Exclusive (only copy, clean), Shared (clean, possibly in several caches) or Invalid. A core must invalidate other copies before writing, moving to M; a read of a line another cache holds in M makes that cache supply the data and both end in S.

Q62. What is false sharing?

When threads on different cores write different variables that share one cache line, coherence invalidations bounce the line between cores although no data is actually shared. It can slow code by several times; pad per-thread data to the line size or use thread-local accumulators.

Q63. What is a memory barrier (fence), and why is it needed?

Processors and compilers reorder memory operations to different addresses for speed, so other cores may observe a thread's writes in an unexpected order. A fence, or acquire/release ordering, forces earlier operations to become visible before later ones. Locks and atomic operations include the necessary fences, which is why correctly locked code works on weakly ordered CPUs.

Q64. State Amdahl's law and its main implication.

Speedup = 1 ÷ ((1 − p) + p ÷ N), where p is the parallelisable fraction and N the number of processors. The serial part caps the speedup at 1 ÷ (1 − p) however many processors you add, so reducing serial work often matters more than adding cores. Gustafson's law gives the more optimistic scaled-speedup view when the problem grows with the machine.

Numerical problems with solutions

Problem 1: CPI and execution time

A program executes 10^9 instructions on a 2.5 GHz processor. The instruction mix and CPI per class are: ALU 50 percent at CPI 1, loads 20 percent at CPI 4, stores 10 percent at CPI 3, branches 20 percent at CPI 2. Find the average CPI, the execution time and the MIPS rating.

Solution.

1. Average CPI = 0.5 × 1 + 0.2 × 4 + 0.1 × 3 + 0.2 × 2 = 0.5 + 0.8 + 0.3 + 0.4 = 2.0.
2. Time = instructions × CPI ÷ clock rate = 10^9 × 2.0 ÷ (2.5 × 10^9) = 0.8 s.
3. MIPS = clock rate in MHz ÷ CPI = 2,500 ÷ 2.0 = 1,250.

Problem 2: Amdahl's law

(a) An enhancement makes 40 percent of a program's run time 5 times faster. What is the overall speedup? (b) If 60 percent of a program can be parallelised, how fast must that part become for the whole program to run 2 times faster?

Solution.

(a) Speedup = 1 ÷ ((1 − 0.4) + 0.4 ÷ 5) = 1 ÷ (0.6 + 0.08) = 1 ÷ 0.68 = 1.47.

(b) We need 1 ÷ (0.4 + 0.6 ÷ s) = 2.

1. 0.4 + 0.6 ÷ s = 0.5.
2. 0.6 ÷ s = 0.1.
3. s = 6. The parallel part must run 6 times faster (for example on at least 6 processors with perfect scaling).

Problem 3: IEEE 754 encoding

Write −6.75 in IEEE 754 single precision, in binary and hexadecimal.

Solution.

1. Sign: negative, so sign bit = 1.
2. 6.75 in binary: 6 = 110, 0.75 = 0.11, so 6.75 = 110.11.
3. Normalise: 110.11 = 1.1011 × 2^2.
4. Exponent = 2 + 127 = 129 = 10000001.
5. Fraction (bits after the leading 1, padded to 23 bits) = 10110000000000000000000.

sign | exponent | fraction
  1  | 10000001 | 10110000000000000000000

1100 0000 1101 1000 0000 0000 0000 0000 = 0xC0D80000

Answer: 0xC0D80000.

Problem 4: IEEE 754 decoding

What decimal value does the single-precision pattern 0x41460000 represent?

Solution.

1. Binary: 0100 0001 0100 0110 0000 ....
2. Sign = 0 (positive).
3. Exponent = next 8 bits = 10000010 = 130, so the power is 130 − 127 = 3.
4. Fraction = 10001100...0, so the significand is 1.10001100 in binary = 1 + 0.5 + 0.03125 + 0.015625 = 1.546875.
5. Value = 1.546875 × 2^3 = 12.375.

Check: 12.375 = 1100.011 in binary = 1.100011 × 2^3. Correct.

Problem 5: Cache address breakdown

A 128 KB, 8-way set-associative cache has 32-byte blocks and 32-bit byte addresses. (a) How many bits for tag, index and offset? (b) Split the address 0xABCD1234.

Solution.

(a)

1. Offset = log2(32) = 5 bits.
2. Lines = 131,072 ÷ 32 = 4,096. Sets = 4,096 ÷ 8 = 512. Index = log2(512) = 9 bits.
3. Tag = 32 − 9 − 5 = 18 bits.

(b)

1. Offset = low 5 bits of 0x...34 (110100): the low five bits are 10100 = 20.
2. Index = (address shifted right by 5) mod 512 = 145 (0x91).
3. Tag = address shifted right by 14 = 0x2AF34.

| tag 0x2AF34 (18 bits) | index 145 (9 bits) | offset 20 (5 bits) |

Problem 6: Two-level AMAT

L1 hit time 1 ns, L1 miss rate 4 percent. L2 hit time 10 ns, L2 local miss rate 25 percent. Main memory access 80 ns. Find the AMAT and the global L2 miss rate.

Solution.

1. L1 miss penalty = 10 + 0.25 × 80 = 10 + 20 = 30 ns.
2. AMAT = 1 + 0.04 × 30 = 1 + 1.2 = 2.2 ns.
3. Global L2 miss rate = 0.04 × 0.25 = 1 percent of all accesses.

Problem 7: Pipeline speedup with balanced stages

A 5-stage pipeline with equal stages runs 1,000 instructions with no stalls. What is the speedup over a non-pipelined machine whose instruction takes the same total time as the five stages?

Solution.

1. Non-pipelined time = n × k = 1,000 × 5 = 5,000 stage-times.
2. Pipelined time = k + (n − 1) = 5 + 999 = 1,004 stage-times.
3. Speedup = 5,000 ÷ 1,004 = 4.98, close to the ideal of 5.

Problem 8: Pipeline speedup with unequal stages

Stage delays are 200, 150, 250, 100 and 200 ps, and each pipeline register adds 20 ps. Find the speedup for 1,000 instructions over a non-pipelined design (which has no pipeline registers).

Solution.

1. Non-pipelined instruction time = 200 + 150 + 250 + 100 + 200 = 900 ps; for 1,000 instructions: 900,000 ps.
2. Pipelined clock = slowest stage + register delay = 250 + 20 = 270 ps.
3. Pipelined time = (5 + 999) × 270 = 1,004 × 270 = 271,080 ps.
4. Speedup = 900,000 ÷ 271,080 = 3.32.

Unbalanced stages and register overhead cut the speedup from nearly 5 to about 3.3.

Problem 9: Pipeline with branch stalls

In a 5-stage pipeline with ideal CPI 1, 20 percent of instructions are branches, and each branch causes a 2-cycle stall. What is the effective CPI, and the speedup over an unpipelined version that takes 5 cycles per instruction at the same clock?

Solution.

1. CPI = 1 + 0.2 × 2 = 1.4.
2. Speedup = 5 ÷ 1.4 = 3.57.

Problem 10: TLB effective access time and page tables

(a) A system has a single-level page table in memory, TLB lookup 10 ns, memory access 100 ns and TLB hit ratio 90 percent. Find the effective access time. (b) For 32-bit virtual addresses, 4 KB pages and 4-byte page-table entries, how large is a flat page table, and what is the reach of a 128-entry TLB?

Solution.

(a)

1. TLB hit: 10 + 100 = 110 ns (one memory access for the data).
2. TLB miss: 10 + 100 (page-table entry) + 100 (data) = 210 ns.
3. EAT = 0.9 × 110 + 0.1 × 210 = 99 + 21 = 120 ns.

(b)

1. Pages = 2^32 ÷ 2^12 = 2^20 entries; size = 2^20 × 4 bytes = 4 MiB per process.
2. TLB reach = 128 × 4 KiB = 512 KiB.

Revision checklist

Tick each item when you can explain it aloud without notes.

Fundamentals and data

• Iron law, CPI from an instruction mix, why MIPS misleads
• Von Neumann bottleneck, Harvard versus modified Harvard
• Two's complement range, negation, overflow versus carry
• IEEE 754 single and double layouts; encode and decode by hand; special values
• Endianness and where each kind is used

Logic, ISA and datapath

• Universal gates, mux, decoder, latch versus flip-flop
• Ripple-carry versus carry-lookahead adders
• RISC versus CISC, load-store architecture, addressing modes
• Instruction formats, calling conventions
• Instruction cycle, hardwired versus microprogrammed control

Pipelining

• Speedup formula n × k ÷ (k + n − 1) and why it falls short
• Structural, data and control hazards with one example each
• Forwarding, load-use stall, branch prediction (2-bit counter)

Memory

• Hierarchy and approximate latencies at each level
• Tag/index/offset for any configuration; trace hits and misses
• Replacement and write policies; 3 Cs; AMAT with two or three levels
• SRAM versus DRAM, refresh, row buffer, DDR bandwidth
• MMU, multi-level page tables, TLB, TLB reach, EAT, VIPT

I/O and parallelism

• Memory-mapped versus isolated I/O; polling, interrupts, DMA with numbers
• Vectored interrupts, daisy chaining, bus arbitration, PCIe, NVMe versus SATA
• Flynn's taxonomy, superscalar, out-of-order, renaming, ROB, speculation, Spectre
• SIMD, SMT, MESI walkthrough, snooping versus directory, false sharing
• Memory ordering and fences; Amdahl and Gustafson calculations

Practical performance

• Row- versus column-major loops, AoS versus SoA
• Branch mispredictions and branch-free code
• Reading perf stat; loop interchange and tiling for matrix multiply

Key takeaways

• Answer conceptual questions with definition, reason and example; give orders of magnitude when unsure of exact numbers.
• Most numerical questions reduce to a handful of formulas: the iron law, Amdahl, IEEE 754 fields, tag/index/offset, AMAT, pipeline speedup and EAT.
• Write each step of a calculation; interviewers care about method as much as the final number.
• Read every numerical question for traps: local versus global miss rates, page-table levels, byte versus word addressing.
• Connect hardware to code: locality, branch predictability, data layout and false sharing are where architecture meets everyday programming.
• Use the checklist to find weak areas, then reread the matching lesson.

Next lesson

You have finished the track. Start again from the introduction to revise, or test yourself with the practice quizzes.