0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.