Saumil_HW05_CS514-1

Saumil Trivedi CS514(HW05) CWID: 20011349 1. (16 Points) Exercise B.1 Parts a and b (cache hit, 1 cycle; cache miss, 110 cycles; main memory access with cache disabled, 105 cycles) a. [10] <B.1> When you run a program with an overall miss rate of 3%, what will the average memory access time (in CPU cycles) be? Answer: Average memory-access time = Hit time + Miss rate *Miss penalty = 1+ 0.03*110 = 4.3 b. [10] <B.1> Next, you run a program specifically designed to produce completely random data addresses with no locality. Toward that end, you use an array of size 1 GB (all of which fits in the main memory). Accesses to random elements of this array are continuously made (using a uniform random number generator to generate the elements indices). If your data cache size is 64 KB, what will the average memory access time be? Answer: Average memory-access time = Probability of hit * Hit time + Miss rate * Miss penalty So now Prob. Of heat = 64KB/1 GB =0.00006104 Now, 0.00006104*1 + 0.99993896 * 110 = 109.99334664 cycles

2. (28 Points) Exercise B.5 Appendix B. Assume L1 cache Write-through with no write- allocate and L2 cache Write-back with write-allocate. Hint: A useful tool for solving this type of problem is to extract all of the available information from the problem description. It is possible that not all of the information will be necessary to solve the problem, but having it in summary form makes it easier to think about. Answer: CPU: The CPU runs at 1.1 GHz, resulting in a cycle time of approximately 0.909 ns. The CPU's CPI, excluding memory accesses, stands at 1.35. Instruction Mix: The system's instructions consist of 20% loads, 10% stores, and 70% non- memory access instructions. Caches: The system employs a split L1 cache without bit penalties. L1 Instruction Cache: With a 2% miss rate, it operates using 32-byte blocks and imposes a miss penalty of 15 ns plus 2 cycles when a miss occurs. L2 Data Cache: Featuring a 5% miss rate, it uses 16-byte blocks and follows a write- through policy. The miss penalty for L2 cache misses is 15 ns plus 1 cycle. L1/L2 Bus: The connection between L1 and L2 caches is on a 128-bit bus running at 266 MHz. L2 Unified Cache: The L2 cache has a size of 512KB, operates in write-back mode, maintains an 80% hit rate, and records that 50% of replaced cache blocks are dirty. It uses 64-byte blocks, and the miss penalty for L2 cache misses is 67.52 ns. Memory: The memory system is 128 bits wide (16 bytes) with a first access time of 60 ns and subsequent accesses requiring 1 cycle at 133 MHz on a 128-bit bus. a) L1 Cache Miss Time in L2: - L1_miss_time_in_L2 = 15 ns (access time) + 2 L2_cycles = 15 + (32 * 3.75 / 16) = 2.5 ns - L2_miss_time_in_memory = 60 ns (access time) + 4 memory_cycles = 60 + (64 / 16 * 7.5) = 90 ns - Average_memory_access_time = 0.02 * L1_miss_time_in_L2 + 0.02 * 0.2 * L2_miss_time_in_memory + 0.02 * 0.5 * access_time_for_L2_write_back = 0.99 ns b) L1 Read Cache Miss Time in L2: - L1_read_miss_time_in_L2 = 15 + 3.75 = 18.75 ns - L2_miss_time_in_memory = 90 ns

executes, assuming the cache is direct mapped, with write through and no write allocate. b) Repeat Part (a) assuming cache is a 2-way set associative, with FIFO replacement policy, and write back, and write allocate. A) The cache has 4 entries. Therefore, N MOD 4 Instruction Memory Access Cache Status Cache Content fld f0, 0(x0) Load M[0] Miss 0: 4.0 fld f2, 0(x2) Load M[16] Miss 0: 4.0, 16: 7.0 fsd f2, 0(x2) Store M[16] Hit 0: 4.0, 16: 28.0 fld f2, 0(x2) Load M[24] Hit 0: 4.0, 16: 28.0 fsd f2, 0(x2) Store M[24] Hit 0: 4.0, 16: 36.0 fld f2, 0(x2) Load M[32] Miss 0: 4.0, 32: 5.0 fsd f2, 0(x2) Store M[32] Hit 0: 4.0, 32: 20.0 fld f2, 0(x2) Load M[40] Hit 0: 4.0, 32: 20.0 fsd f2, 0(x2) Store M[40] Hit 0: 4.0, 32: 12.0 fld f2, 0(x2) Load M[48] Miss 0: 4.0, 48: 1.0 fsd f2, 0(x2) Store M[48] Hit 0: 4.0, 48: 4.0 fld f2, 0(x2) Load M[56] Hit 0: 4.0, 48: 4.0 fsd f2, 0(x2) Store M[56] Hit 0: 4.0, 48: 8.0 fld f2, 0(x2) Load M[64] Miss 8: 5.0, 24: 9.0 fsd f2, 0(x2) Store M[64] Hit 8: 20.0, 24: 9.0 fld f2, 0(x2) Load M[72] Hit 8: 20.0, 24: 9.0 fsd f2, 0(x2) Store M[72] Hit 8: 32.0, 24: 9.0 fld f2, 0(x2) Load M[80] Miss 8: 32.0, 80: 7.0 fsd f2, 0(x2) Store M[80] Hit 8: 32.0, 80: 28.0 B) N MOD 2 Instruction Memory Access Cache Status Cache Content fld f0, 0(x0) Load M[0] Miss 0: 4.0 fld f2, 0(x2) Load M[16] Miss 0: 4.0, 16: 7.0 fsd f2, 0(x2) Store M[16] Hit 0: 4.0, 16: 28.0 fld f2, 0(x2) Load M[24] Hit 0: 4.0, 16: 28.0 fsd f2, 0(x2) Store M[24] Hit 0: 4.0, 16: 36.0 fld f2, 0(x2) Load M[32] Miss 0: 4.0, 32: 5.0 fsd f2, 0(x2) Store M[32] Hit 0: 4.0, 32: 20.0 fld f2, 0(x2) Load M[40] Hit 0: 4.0, 32: 20.0

fsd f2, 0(x2) Store M[40] Hit 0: 4.0, 32: 12.0 fld f2, 0(x2) Load M[48] Miss 0: 4.0, 48: 1.0 fsd f2, 0(x2) Store M[48] Hit 0: 4.0, 48: 4.0 fld f2, 0(x2) Load M[56] Hit 0: 4.0, 48: 4.0 fsd f2, 0(x2) Store M[56] Hit 0: 4.0, 48: 8.0 fld f2, 0(x2) Load M[64] Miss 8: 5.0, 24: 9.0 fsd f2, 0(x2) Store M[64] Hit 8: 20.0, 24: 9.0 fld f2, 0(x2) Load M[72] Hit 8: 20.0, 24: 9.0 fsd f2, 0(x2) Store M[72] Hit 8: 32.0, 24: 9.0 fld f2, 0(x2) Load M[80] Miss 8: 32.0, 80: 7.0 fsd f2, 0(x2) Store M[80] Hit 8: 32.0, 80: 28.0 4. (8 Points) A computer has a L1 data cache and a L1 instruction cache. The latencies of the different kinds of accesses are as follows: cache hit 1cycle, cache miss 16 cycles. If the miss rate for instructions is 5% and the miss rate for data is 6%, what is the average memory access time in cycles? Answer: AMAT = Hit Time + Miss Rate * Miss Penalty For data accesses: AMAT_data = 1 + (0.06 x 16) = 1 + 0.96 = 1.96 cycles For instruction accesses: AMAT_instruction = 1 + (0.05 x 16) = 1 + 0.8 = 1.8 cycles So now the Average will be (1.96 + 1.8) / 2 = 1.88 cycles 5. (16 Points) Assume we have a 512 byte cache with 64 byte blocks. We also assume that the main memory is 2KB large. We can regard the memory as an array of 64- byte memory blocks M0, M1, M2, ...M31. The table below displays the memory blocks that can reside in different cache blocks if the cache was fully associative. Cache Block Set Memory blocks that can reside in cache blocks 0 0 M0, M1, M2, .... M31 1 0 M0, M1, M2, .... M31 2 0 M0, M1, M2, .... M31 3 0 M0, M1, M2, .... M31 4 0 M0, M1, M2, .... M31 5 0 M0, M1, M2, .... M31 6 0 M0, M1, M2, .... M31 7 0 M0, M1, M2, .... M31

7. (8 Points) Let’s assume a computer with L2 cache that has a 256-byte cache block. It takes 10 clock cycles to transfer the first 8 bytes to L1, and then 1 clock cycle per 8 bytes to transfer the rest of the block. Compare the miss penalty times with and without Critical Word First? Answer: Without Critical Word First: Total miss penalty without CWF = 10 (for the first 8 bytes) + 31 (for the remaining 248 bytes) = 41 clock cycles With Critical Word First (CWF): Total miss penalty with CWF = 10 clock cycles Therefore L2 cache with Critical word first will be 41/10 =4.1 times faster than without it.