Sheet 01
Formulas:
1. Miss rate:
𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎𝑐𝑐𝑒𝑠𝑠𝑒𝑠 𝑡ℎ𝑎𝑡 𝑚𝑖𝑠𝑠 / 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑎𝑐𝑐𝑒𝑠𝑠𝑒𝑠
2. Misses per instruction:
𝑀𝑖𝑠𝑠𝑒𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 × 𝑀𝑒𝑚𝑜𝑟𝑦 𝑎𝑐𝑐𝑒𝑠𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
3. Average memory access time (AMAT):
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑚𝑒𝑚𝑜𝑟𝑦 𝑎𝑐𝑐𝑒𝑠𝑠 𝑡𝑖𝑚𝑒 = 𝐻𝑖𝑡 𝑡𝑖𝑚𝑒 + 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 × 𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
4. Average memory access time (AMAT) with multi-level cache:
𝐴𝑀𝐴𝑇 = 𝐻𝑖𝑡 𝑡𝑖𝑚𝑒𝐿1 + 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒𝐿1 × (𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦𝐿1 )
𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦𝐿1 = 𝐻𝑖𝑡 𝑡𝑖𝑚𝑒𝐿2 + 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒𝐿2 × (𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦𝐿2 )
5. CPU execution time with approximate memory stall clock cycles:
𝐶𝑃𝑈 𝑒𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑡𝑖𝑚𝑒
= (𝐶𝑃𝑈 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒𝑠 + 𝑴𝒆𝒎𝒐𝒓𝒚 𝒔𝒕𝒂𝒍𝒍 𝒄𝒚𝒄𝒍𝒆𝒔) × 𝐶𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑡𝑖𝑚𝑒
𝑀𝑒𝑚𝑜𝑟𝑦 𝑠𝑡𝑎𝑙𝑙 𝑐𝑦𝑐𝑙𝑒𝑠 = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑚𝑖𝑠𝑠𝑒𝑠 × 𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
𝑴𝒊𝒔𝒔𝒆𝒔
= 𝐼𝐶 × × 𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
𝑀𝑒𝑚𝑜𝑟𝑦 𝑎𝑐𝑐𝑒𝑠𝑠𝑒𝑠
= 𝐼𝐶 × × 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 × 𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
6. Actual memory stall clock cycles:
𝑀𝑒𝑚𝑜𝑟𝑦 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒𝑠
= 𝐼𝐶 × 𝑅𝑒𝑎𝑑𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 × 𝑅𝑒𝑎𝑑 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒
× 𝑅𝑒𝑎𝑑 𝑚𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
+ 𝐼𝐶 × 𝑊𝑟𝑖𝑡𝑒𝑠 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 × 𝑊𝑟𝑖𝑡𝑒 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒
× 𝑊𝑟𝑖𝑡𝑒 𝑚𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
Page 1 of 3
Questions:
1. Assume we have a computer where the cycles per instruction (CPI) is
1.0 when all memory accesses hit in the cache. The only data
accesses are loads and stores, and these total 50% of the
instructions. If the miss penalty is 50 clock cycles and the miss rate is
1%, how much faster would the computer be if all instructions were
cache hits?
2. To show equivalency between the two miss rate equations, let’s redo
the preceding example, this time assuming a miss rate per 1000
instructions of 30. What is memory stall time in terms of instruction
count?
3. Assume a fully associative write-back cache with many cache
entries that start empty. The following is a sequence of five memory
operations (the address is in square brackets):
Write Mem[100];
Write Mem[100];
Read Mem[200];
Write Mem[200];
Write Mem[100];
What are the number of hits and misses when using no-write
allocate versus write allocate?
4. Which has the lower miss rate: a 16 KiB instruction cache with a 16
KiB data cache or a 32 KiB unified cache? Use the miss rates in
Figure B.6 to help calculate the correct answer, assuming 36% of
the instructions are data transfer instructions. Assume a hit takes 1
clock cycle and the miss penalty is 100 clock cycles. A load or store
hit takes 1 extra clock cycle on a unified cache if there is only one
cache port to satisfy two simultaneous requests. Using the pipelining
terminology of Chapter 3, the unified cache leads to a structural
hazard. What is the average memory access time in each case?
Assume write-through caches with a write buffer and ignore stalls
due to the write buffer.
Page 2 of 3
5. Let’s use an in-order execution computer for the first example.
Assume that the cache miss penalty is 200 clock cycles, and all
instructions usually take 1.0 clock cycles (ignoring memory stalls).
Assume that the average miss rate is 2%, there is an average of 1.5
memory references per instruction, and the average number of
cache misses per 1000 instructions is 30. What is the impact on
performance when behavior of the cache is included? Calculate the
impact using both misses per instruction and miss rate.
6. Suppose that in 1000 memory references there are 40 misses in the
first-level cache and 20 misses in the second-level cache. What are
the various miss rates? Assume the miss penalty from the L2 cache
to memory is 200 clock cycles, the hit time of the L2 cache is 10
clock cycles, the hit time of L1 is 1 clock cycle, and there are 1.5
memory references per instruction. What is the average memory
access time and average stall cycles per instruction? Ignore the
impact of writes.
Page 3 of 3
