Skip to content
Tutorials Center
My learning

Topics

Lesson 65 of 67 ยท Practice and Interview

Practice: CPU, Pipeline, Cache and Virtual Memory

Work through exercises on CPI, Amdahl's law, pipeline stalls, cache mapping, AMAT, page tables and page replacement, with solutions you can verify in Python.

Exams and interviews on computer organization are mostly calculations: how long does this program take, how many bits are in the tag, how many page faults will this string cause? The formulas are short, but they are easy to misapply under pressure. This lesson gives you a set of exercises in four groups, each with a worked solution and a Python program that recomputes every answer.

Try each problem on paper first. The ideas come from Measuring Performance, Instruction Pipelining, Pipeline Hazards, Cache Memory Basics, Direct, Associative and Set-Associative Mapping and Virtual Memory and Paging.

Part 1: Performance equations

Exercise 1.1. A program executes 1 billion instructions on a 2 GHz processor with an average CPI of 1.5. How long does it take?

Exercise 1.2. An instruction mix is 50% ALU operations (CPI 1), 30% loads and stores (CPI 3) and 20% branches (CPI 2). What is the average CPI?

Exercise 1.3. 40% of a program's run time can be sped up by a factor of 5. What is the overall speedup? What is the best possible speedup, however fast that part becomes?

Solutions.

  • 1.1: Time = instructions x CPI / clock rate = 10^9 x 1.5 / (2 x 10^9) = 0.75 s.
  • 1.2: CPI = 0.5 x 1 + 0.3 x 3 + 0.2 x 2 = 0.5 + 0.9 + 0.4 = 1.8.
  • 1.3: Amdahl's law gives 1 / (0.6 + 0.4/5) = 1 / 0.68 = 1.47. If that part took zero time, the limit is 1 / 0.6 = 1.67. The remaining 60% caps the gain no matter what.
Python Check Part 1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 2: Pipelines and hazards

Exercise 2.1. A 5-stage pipeline runs 100 instructions with no stalls. How many cycles does it need, and what is the speedup over a non-pipelined machine that spends 5 cycles per instruction?

Exercise 2.2. Trace this sequence on a 5-stage pipeline (IF, ID, EX, MEM, WB) with and without forwarding. Assume a register can be written in the first half of a cycle and read in the second half.

Text
lw  r1, 0(r2)
add r3, r1, r4
sub r5, r3, r1
sw  r5, 8(r2)

Exercise 2.3. 25% of instructions are loads, and 40% of loads are immediately followed by an instruction that uses the loaded value. With forwarding, each such case costs one bubble. What is the CPI?

Exercise 2.4. 20% of instructions are branches, 60% of them are taken, and a taken branch costs 2 extra cycles (the machine always predicts "not taken"). What is the CPI?

Solutions.

  • 2.1: The first instruction needs 5 cycles; each later one finishes one cycle after the previous. Total = 5 + 99 = 104 cycles. The non-pipelined machine needs 500, so the speedup is 500 / 104 = 4.81, close to but below the ideal 5.
  • 2.2: Without forwarding, a consumer must wait until the producer has written its result back. add needs r1 from the load, sub needs r3 from add, sw needs r5 from sub, so each of those three steps waits 2 bubbles: 8 ideal cycles become 14. With forwarding, an ALU result goes straight to the next EX stage with no delay. Only the load-use pair (lw then add) still costs one bubble, so the total is 9 cycles.
  • 2.3: Stalls per instruction = 0.25 x 0.40 x 1 = 0.10, so CPI = 1.10.
  • 2.4: Stalls per instruction = 0.20 x 0.60 x 2 = 0.24, so CPI = 1.24.
Python Check Part 2: count bubbles in a tiny pipeline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 3: Cache

Exercise 3.1. A 16 KB direct-mapped cache has 32-byte blocks and 32-bit addresses. How many bits are in the offset, index and tag? Repeat for 4-way set-associative.

Exercise 3.2. Hit time is 2 ns, the miss rate is 5% and the miss penalty is 80 ns. What is the AMAT?

Exercise 3.3. L1 has a 1-cycle hit time and a 4% miss rate. L2 has a 10-cycle hit time and a 25% local miss rate. Memory takes 100 cycles. What is the AMAT?

Exercise 3.4. A small cache has 4 blocks. The block-address trace is 0 4 0 4 1 0 4 1. Mark each access as a hit (H) or miss (M) for (a) direct-mapped, (b) 2-way set-associative with LRU.

Solutions.

  • 3.1: The offset has log2(32) = 5 bits. The cache holds 16 KB / 32 B = 512 blocks. Direct-mapped: 512 sets, so the index has 9 bits, and the tag has 32 - 9 - 5 = 18 bits. 4-way: 512 / 4 = 128 sets, so index 7 bits, tag 20 bits. More ways means fewer index bits and a longer tag.
  • 3.2: AMAT = 2 + 0.05 x 80 = 6 ns.
  • 3.3: The L1 miss penalty is itself an AMAT: 10 + 0.25 x 100 = 35. So AMAT = 1 + 0.04 x 35 = 2.4 cycles.
  • 3.4: In (a) there are 4 sets and set = block mod 4. Blocks 0 and 4 both map to set 0 and keep evicting each other: M M M M M M M H (7 misses, only the last access to block 1 hits). In (b) there are 2 sets of 2 ways; blocks 0 and 4 both go to set 0 and fit together, block 1 goes to set 1: M M H H M H H H (3 misses, all compulsory). The same capacity does much better because associativity removes the conflict.
Python Check Part 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Part 4: Virtual memory

Exercise 4.1. A system has 32-bit virtual addresses and 4 KB pages. How many bits are the page offset and the virtual page number (VPN)? How large is a single-level page table with 4-byte entries?

Exercise 4.2. The page table maps VPN 0x00403 to frame 0x1A. What physical address does the virtual address 0x00403ABC translate to?

Exercise 4.3. A TLB lookup takes 1 ns and a memory access takes 100 ns. The TLB hit rate is 98%. A TLB miss needs one extra memory access to read the page table entry. What is the effective access time?

Exercise 4.4. Count page faults for the reference string 1 2 3 4 1 2 5 1 2 3 4 5 with FIFO replacement using 3 frames and using 4 frames.

Solutions.

  • 4.1: 4 KB = 2^12, so the offset is 12 bits and the VPN is the remaining 20 bits. The table has 2^20 entries of 4 bytes = 4 MB per process, which is why real systems use multi-level tables.
  • 4.2: The offset is the low 12 bits, 0xABC. The VPN is 0x00403. The frame number 0x1A is placed above the offset, so the physical address is 0x1AABC.
  • 4.3: A hit costs 1 + 100 = 101 ns. A miss costs 1 + 100 + 100 = 201 ns. EAT = 0.98 x 101 + 0.02 x 201 = 98.98 + 4.02 = 103 ns.
  • 4.4: With 3 frames FIFO gives 9 faults. With 4 frames it gives 10 faults: more memory made things worse. This is Belady's anomaly, and it only happens with algorithms like FIFO that are not stack algorithms. LRU gives 10 faults with 3 frames and 8 with 4, so it never gets worse.
Python Check Part 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a calculation involves "bits", write down the three numbers that must add up (offset + index + tag for caches, offset + VPN for pages) and check the sum equals the address width. That single check catches most mistakes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A 64 KB direct-mapped cache has 64-byte blocks and 32-bit addresses. How many index bits are there?

    64 KB / 64 B = 1,024 blocks, and one set per block in a direct-mapped cache, so the index needs log2(1024) = 10 bits (the offset is 6 bits and the tag is 16 bits).
  2. 2. Why can a load followed immediately by an instruction that uses its result still stall when forwarding is available?

    An ALU result exists at the end of EX and can be forwarded to the next EX stage. A load's data comes out of memory in MEM, one stage later, so one bubble remains.
  3. 3. FIFO page replacement with a reference string causes 9 faults with 3 frames and 10 with 4 frames. What is this called?

    Belady's anomaly is the counter-intuitive rise in faults when memory grows, possible with FIFO but impossible with LRU or optimal replacement.
  4. 4. An instruction mix has CPI 1 for 80% of instructions and CPI 6 for the other 20%. What is the average CPI?

    0.8 x 1 + 0.2 x 6 = 0.8 + 1.2 = 2.0. Weight each CPI by the fraction of instructions, not by the number of classes.

Summary

  • CPU time = instructions x CPI / clock rate; average CPI is a weighted sum over the instruction mix.
  • Amdahl's law: speedup = 1 / ((1 - p) + p / s); the unimproved part sets the ceiling.
  • A pipeline finishes n instructions in (stages + n - 1) cycles; hazards add bubbles, and a load-use pair still costs one with forwarding.
  • Cache address bits: offset = log2(block size), index = log2(sets), tag = the rest; AMAT = hit time + miss rate x penalty, nested for multiple levels.
  • Page translation replaces the VPN with a frame number and keeps the offset; effective access time weights the TLB hit and miss paths.
  • FIFO can show Belady's anomaly; LRU cannot.

Continue with Computer Organization Interview Questions.