Spring 2022 ECE 6913 INET, Quiz 2 Solutions Problem 1. Your Company describes their latest Processor with the following features: 95% of all memory accesses are found in the cache. Each cache block is two words, and the whole block is read on any miss. The processor sends references to its cache at the rate of 109 words per second. 25% of those references are writes. Assume that the memory system can support 109 words per second, reads or writes. The bus reads or writes a single word at a time (the memory system cannot read or write two words at once). Assume at any one time, 30% of the blocks in the cache have been modified. The cache uses write allocate on a write miss. You are considering adding a peripheral to the system, and you want to know how much of the memory system bandwidth is already used. 1.1 Calculate the percentage of memory system bandwidth used assuming the cache is Write Back. 1.2 Calculate the percentage of memory system bandwidth used assuming the cache is Write Through. Please be sure to state your assumptions and show all work We know: * Miss rate = 0.05 * Block size = 2 words (8 bytes) * Frequency of memory operations from processor = 109 * Frequency of writes from processor = 0.25 109 * Bus can only transfer one word at a time to/from processor/memory * On average 30% of blocks in the cache have been modified (must be written back in the case of the write back cache) * Cache is write allocate So: Fraction of read hits = 0.75 0.95 = 0.7125 Fraction of read misses = 0.75 0.05 = 0.0375 Fraction of write hits = 0.25 0.95 = 0.2375 Fraction of write misses = 0.25 0.05 = 0.0125 Write through cache On a read hit there is no memory access On a read miss memory must send two words to the cache On a write hit the cache must send a word to memory On a write miss memory must send two words to the cache, and then the cache must send a word to memory Thus: Average words transferred = 0.7125 0 + 0.0375 2 + 0.2375 1 + 0.0125 3 = 0.35 Average bandwidth used = 0.35 109 Fraction of bandwidth used = [0.35 x 109] / 109 = 0.35 (1) Write back cache On a read hit there is no memory access On a read miss: 1. If replaced line is modified then cache must send two words to memory, and then memory must send two words to the cache 2. If replaced line is clean then memory must send two words to the cache On a write hit there is no memory access On a write miss: 1. If replaced line is modified then cache must send two words to memory, and then memory must send two words to the cache 2. If replaced line is clean then memory must send two words to the cache Thus: Average words transferred = 0.7125 0 + 0.0375 (0.7 2 + 0.3 4) + 0.2375 0 + 0.0125 (0.7 2 + 0.3 4) = 0.13 Average bandwidth used = 0.13 109 Fraction of bandwidth used = 0.13 x 109/109 = 0.13 (2) Comparing 1 and 2 we notice that the write through cache uses more than twice the cache-memory bandwidth of the write back cache. Problem 2. One difference between a write-through cache and a write-back cache can be in the time it takes to write. During the first cycle, we detect whether a hit will occur, and during the second (assuming a hit) we actually write the data. Let’s assume that 50% of the blocks are dirty for a write-back cache. For this question, assume that the write buffer for the write through will never stall the CPU (no penalty). Assume a cache read hit takes 1 clock cycle, the cache miss penalty is 50 clock cycles, and a block write from the cache to main memory takes 50 clock cycles. Finally, assume the instruction cache miss rate is 0.5% and the data cache miss rate is 1%. Assume that on average 26% and 9% of instructions in the workload are loads and stores, respectively. 2.1 Estimate the performance of a write-through cache with a two-cycle write versus a write-back cache with a two-cycle write. CPU performance equation: CPUTime = IC CPI ClockTime CPI = CPIexecution + StallCyclesPerInstruction We know: Instruction miss penalty is 50 cycles Data read hit takes 1 cycle Data write hit takes 2 cycles Data miss penalty is 50 cycles for write through cache Data miss penalty is 50 cycles or 100 cycles for write back cache Miss rate is 1% for data cache (MRD) and 0.5% for instruction cache (MRI) 50% of cache blocks are dirty in the write back cache 26% of all instructions are loads 9% of all instructions are stores Then: CPIexecution = 0.26 1 + 0.09 2 + 0.65 1 = 1.09 Write through StallCyclesPerInstruction = MRI 50 + MRD (0.26 50 + 0.09 50) = 0.425 so: CPI = 1.09 + 0.425 = 1.515 (1) Write back StallCyclesPerInstruction = MRI 50 + MRD (0.26 (0.5 50 + 0.5 100) + 0.09 (0.5 50 + 0.5 100)) = 0.5125 so: CP I = 1.09 + 0.5125 = 1.6025 (2) Comparing 1 and 2 we notice that the system with the write back cache is 6% slower. Problem 3. Consider the following RISC V Instruction sequence executing in a 5-stage pipeline: or x13, x12, x11 ld x10, 0(x13) ld x11, 8(x13) add x12, x10, x11 subi x13, x12, 16 3.1 Identify all of the data hazards and their resolution with NOPs assuming no forwarding or hazard detection hardware is being used Hazards identified: or x13, x12, x11 ld x10, 0(x13) EX to 1st RAW Hazard ld x11, 8(x13) EX to 2nd RAW Hazard add x12, x10, x11 MEM to 1st RAW [load-use-data] & MEM to 2nd Hazards subi x13, x12, 16 Ex to 1st RAW Hazard NOPS introduced to resolve Hazards: or x13, x12, x11 NOPS NOPS ld x10, 0(x13) EX to 1st RAW Hazard resolution with 2 NOPs ld x11, 8(x13) EX to 2nd RAW Hazard resolved as well from above 2 NOPs NOPS NOPS add x12, x10, x11 MEM to 1st RAW [load-use-data] & MEM to 2nd Hazards resolved with 2 NOPs NOPS NOPS subi x13, x12, 16 Ex to 1st only RAW Hazard resolved with 2 NOPs 3.2 If there is forwarding, for the first seven cycles during the execution of this code, specify which signals are asserted in each cycle by hazard detection and forwarding units in Figure below. Clock Cycle 1 2 3 4 5 6 7 8 9 10 1 or IF ID EX MEM WB 2 ld IF ID EX MEM WB 3 ld IF ID EX MEM WB 4 NOP mandatory NOP for which no forwarding solution possible: load-data-use 5 add IF ID EX MEM WB 6 subi IF ID EX MEM WB (1) A=x B=x (no instruction in EX stage yet) (2) A=x B=x (no instruction in EX stage yet) (3) A=0 B=0 (both operands of the or instruction: x11,x12 come from Reg File) (4) A=2 B=0 (base (RS1) in first ld (x13)taken from EX/MEM of previous instruction) (5) A=1 B=0 (base (RS1) in 2nd ld (x13)taken from MEM/WB of a previous instruction) (6) A=x B=x (no instruction in EX stage yet because NOP introduced to resolve MEM to 1st (7) A=0 B=1 (RS2 in the add instruction is x11 which is forwarded from MEM/WB of 2nd ld, the result of the 1st ld (x10) has already been written into Reg File in CC 6 – so, no forwarding necessary for first operand) (8) A=1 B=0 (RS1 of subi instruction forwarded from EX/MEM of add instruction) Problem 4. Consider the following program and cache behaviors. Data Reads per 1K instructions Data Writes per 1K instructions Instruction Cache Miss Rate Data Cache Miss Rate Block Size (Bytes) 300 150 0.5% 5% 128 Suppose a CPU with a write-through, write allocate cache achieves a CPI of 2. 4.1 What are the read and write bandwidths (measured by bytes per cycle) between RAM and the cache (Assume each miss generates a request for one block.). For a write-allocate policy, a write miss also makes a read request to RAM – please be sure to consider its impact on Read Bandwidth Instruction Bandwidth: When the CPI is 2, there are, on average, 0.5 instruction accesses per cycle. 0.5 instructions read from Instruction memory per cycle 0.5% of these instruction accesses cause a cache Read miss (and subsequent memory request). [0.5 instr/cycle] x [0.005 misses/instruction] = missed instructions/cycle Assuming each miss requests one block and each block is 128 bytes [16 words with 8 bytes (64 bits) per word] , instruction accesses generate an average of [0.5 instr/cycle] x [0.005 misses/instruction] x[128 bytes/miss] = = 0.32 bytes/cycle of read traffic Read Data bandwidth: 30% of instructions generate a read request from data memory. [0.5 instr/cycle] x [0.3 Read Data Accesses/instruction] = [0.15 Read Data Accesses / cycle] 5% of these generate a cache miss; [0.15 Read Data Accesses / cycle] x [0.05 misses / Read Data Access] = 0.0075 Read Misses/cycle Assuming each miss requests one block and each block is 128 bytes [16 words with 8 bytes (64 bits) per word] , [0.0075 Read Misses/cycle] x [128 Bytes/block] x [1 block/miss] = 0.0075 x 128 Bytes/cycle = 0.96 Bytes/cycle Write Data bandwidth: 15% of instructions generate a write request into data memory. [0.5 instr/cycle] x [0.15 Write Data Accesses/instruction] = [0.075 Write Data Accesses / cycle] All of the words written to the cache must be written into Memory: [0.075 Write Data Accesses / cycle] x [8 bytes/word] x [1 word/write-through] = 0.6 Bytes/cycle For a Write-allocate policy, a Write miss also makes a read request to RAM [0.5 inst/cycle] x [0.15 Write Data Accesses/instruction] x [0.05 misses/Write Data Access] x [128 Bytes/miss] = 0.48 Bytes/cycle Assuming each miss requests one Word (8 bytes) since this is a write-through cache with only 1 word written per miss into memory, [0.00375 Write Misses/cycle] x [8 Bytes/word] x [1 word/miss] = 0.03 Bytes/cycle Total Read Bandwidth 0.32 (Instruction memory) + 0.96 (data memory) + 0.48 (Write-miss in Write-through cache with Write Allocate) Bytes/cyle = 1.76 Bytes/cycle Total Write Bandwidth: 0.6 Bytes/cycle + 0.03 Bytes/cycle = 0.63 Bytes/cycle
