I am working on practice problems to study for an upcoming exam. I am given the following piece of code:

#define LEAP 4
#define SIZE 64
int foo[SIZE];
// Assume foo has been initialized to contain values.
// Assume the cache starts empty at this point.
for (int i = 0; i < SIZE; i += LEAP) { // Loop 1
  foo[i] = foo[i] + i * (i + 2);
for (int j = 1; j < SIZE; j += (LEAP * 2)) { // Loop 2
  foo[j] = foo[j] + j * 5;

I have a direct-mapped cache containing 128 bytes with a cache block size of 32 bytes. The cache uses LRU replacement and write-allocate and write-back policies. I also need to assume i and j are stored in registers, the array foo starts at address 0x0, and the cache starts out empty. I already determined the hit rate for both Loop 1 and Loop 2, however, I am exploring more into this problem than what is asked as an exercise.

Assuming that all factors remain the same as shown in the original code, how would changing cache size (say from 128 bytes to 256 bytes) affect the hit rate of both loops? Similarly, how would changing the block size (say from 32 bytes to 16 bytes) affect the hit rate of both loops?

My initial assumption would be that if we increased the cache size, then that would increase the hit rate of both loop 1 and loop 2 because it would reduce misses. For decreasing block size, then the hit rate would increase for both loop 1 and loop 2 because if block size was increased, then there would be a decreased number of entries in the cache and it will take more time to fetch block size from memory.

Is my logic incorrect? If so, can someone explain what would happen in terms of the hit rate in both loops by implementing the changes I am suggesting. I am still a little unsure of what I claim would be true. Any feedback or suggestion in helping me answer this conceptual question would be greatly appreciated.

  • $\begingroup$ exploring more into this problem way to go! increased [cache size of 256] would increase the hit rate of [loop 1] please argue: what prior hits turn into misses, what misses turn into hits(, what is the effect on transfers between next memory level and cache)? $\endgroup$
    – greybeard
    May 28 '21 at 6:41

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.