I'm doing some practice problems to study and came across this one:
Consider a 8-way set associative cache with 64 B blocks, and 64 total blocks as part ofa 16 bit physical address.
Imagine we use the cache for the below assembly (RISC-V) code:
.data:arr: .byte 0, 1, 2 , ... 255 # All values from 0 to 255 .text: #ASSUME A WORKING PROLOGUE la a0 arr li a1 256 #Scramble randomizes the elems of arr jal scramble #Assume t0 = 0, t1 = 256, s0 = A, s1 = B, s2 = C #START OF HIT RATE Start: beq t0 t1 End #Iterate 256 times add t2 a0 t0 lbu t2 0(t2) #t2 = arr[t0] add t3 s0 t2 lw t3 0(t3) #t3 = A[t2] add t4 s1 t2 lw t4 0(t4) #t4 = B[t2] add t3 t3 t4 add t4 s2 t0 sw t3 0(t4) # C[t0] = t3 + t4 addi t0 t0 1 j Start #END OF HIT RATE End: #ASSUME A WORKING EPILOGUE
Let scramble a function that randomly sorts the elements of an array. Additionally assume that:
- A is located at 0x1000
- B is located at 0x2000
- C is located at 0x3000
- arr is located at 0x4000
- Our cache is empty when reaching #START OF HIT RATE
The question asks:
What is the best and worse case hit rate for this code? Write your answer as a fraction.
It says the answer are both 63/64. But how? the best case one especially doesn't make sense, because in the best case you only swap a few elements in scramble. In any case, how do you compute that number?