How to count the number of hits in different types of caches?

Question

Computers

Good afternoon!

I found one task from an old session, and I don't know how to solve it.
The task sounds like this:

There is a system with the following features:
- 1 core / 1 hard thread,
- FIFO command execution,
- single-level cache hierarchy (L1, RAM),
- Cache cell size - 16 bytes,
- cache size - 2048 bytes,
- the cache at the time the program is executed is empty,
- the size of the date and address buses is 32 bits,
- there is no prefetching or any other optimizations.

on this system run the following program:

int test[512];
for (int i = 0; i < 10; i++) {
int sum = 0;
for (int j = 0; j < 512; j = j + 16) {
sum = sum + test[j];
}
}

You need to calculate:
- the total number of cache accesses,
- the number of cache accesses, if the cache is direct-mapped,
- the number of cache accesses, if the cache is fully associative.

Please tell me how this is considered. It would be great if the solution was described in as much detail as possible.
Thank you!

Answer 1

- number of cache hits if the cache is direct-mapped,
- cache hits if the cache is fully associative.
Please tell me how this is considered.

You first need to know what a "direct-mapped cache" and a "fully associative cache" are. You can read about it, for example, here .
After that, you need to look at what sequence of addresses when accessing memory is generated by the program and calculate which of these accesses go into memory, and which ones go into already loaded cache lines.
If the array int test[512];occupies 2048 bytes of memory ( sizeof(int) == 4), then it will fit entirely in the specified cache and there will be no difference between a direct mapped cache and a fully associative cache. The inner loop accesses array elements that lie in different cache lines (because16(шаг цикла) * sizeof(int) > 16(размер кэш-линии)). those. each call to the inner loop will go into memory on the first iteration of the outer loop. On the second and subsequent iterations of the outer loop, all accesses from the inner loop will go to the cache. Those. total accesses to the cache will be 9 * (512 / 16).