# 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
lbu t2 0(t2) #t2 = arr[t0]
lw t3 0(t3)  #t3 = A[t2]
lw t4 0(t4)  #t4 = B[t2]
sw t3 0(t4)      # C[t0] = t3 + t4
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