# Finding Worst and Best Case Hit Rate of a Cache Given Code

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?