Как посчитать кол-во обращений в разных типах кэшей?

Question

[Ivan12344567]

Добрый день!

Я нашел одно задание из старой сессии, и не знаю, как его решить.
Задание звучит так :

Есть система с такими особенностями :
- 1 ядро / 1 хардварный поток,
- FIFO выполнение комманд,
- одноуровневая кэш-иерархия (L1, RAM),
- Размер ячейки кэша - 16 байт,
- размер кэша - 2048 байт,
- кэш на момент выполнения проги пуст,
- размер дата и адресной шин - 32 бит,
- префетчинга или любых других оптимизаций нет.

на этой системе выполняют следующую программу :

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];
}
}

Нужно посчитать :
- общее кол-во обращений к кэшу,
- кол-во обращений к кэшу, если кэш прямого отображения,
- кол-во обращений к кэшу, если кэш полностью ассоциативный.

Подскажите пожалуйста, как такое считается. Было бы отлично, если бы решение было расписано максимально подробно.
Спасибо!

Answer 1

[jcmvbkbc]

- кол-во обращений к кэшу, если кэш прямого отображения,
- кол-во обращений к кэшу, если кэш полностью ассоциативный.
Подскажите пожалуйста, как такое считается.

Нужно сначала узнать, что такое "кэш прямого отображения" и "полностью ассоциативный кэш". Об этом ожно почитать, например, здесь.
После этого надо посмотреть, какая последовательность адресов при обращении к памяти генерируется программой и посчитать, какие из этих обращений попадают в память, а какие -- в уже загруженные линии кэша.

Если массив int test[512]; занимает 2048 байт памяти (sizeof(int) == 4), тогда он полностью умещается в заданный кэш и разницы между кэшем прямого отображения и полностью ассоциативным не будет. Внутренний цикл обращается к элементам массива, лежащим в разных кэш-линиях (поскольку 16(шаг цикла) * sizeof(int) > 16(размер кэш-линии)). т.е. каждое обращение внутреннего цикла пойдёт в память на первой итерации внешнего цикла. На второй и последующих итерациях внешнего цикла все обращения из внутреннего цикла пойдут в кэш. Т.е. всего обращений в кэш будет 9 * (512 / 16).