Эффект кеширования кэша уменьшается при большом размере данных

Question

Я могу наблюдать эффект кеша кеша, когда применяю простые алгоритмы (умножение матриц, факторизация LU и т. Д.) К матрицам размера 2 ^ n: в основном, существуют пики времени при размерах матриц 2 ^ k.Однако при растущих значениях 2 ^ n это явление больше не проверяется (скажем, размер = 2 ^ 14x2 ^ 14 = 16384x16384).
С чем это связано?

Редактировать
Проводя несколько очень простых экспериментов в Matlab, я получаю следующее:

>> n = 1024;  
>> AA = rand(n);
>> tic; lu(AA); toc;
Elapsed time is 0.163291 seconds.
>> n = 1025;
>> AA = rand(n);
>> tic; lu(AA); toc;
Elapsed time is 0.040935 seconds.

И снова переходя к следующемуСтепень 2, очистка кэша проверена, но менее очевидно:

>> n = 4096;
>> AA = rand(n);
>> tic; lu(AA); toc;
Elapsed time is 1.208170 seconds.
>> n = 4097;
>> AA = rand(n);
>> tic; lu(AA); toc;
Elapsed time is 1.120656 seconds.

На этом ноутбуке очистка кэша больше не проверяется для размера матрицы = 2 ^ 13x2 ^ 13:

>> n = 8192;
>> AA = rand(n);
>> tic; lu(AA); toc
Elapsed time is 8.586088 seconds.
>> n = 8193;
>> AA = rand(n);
>> tic; lu(AA); toc;
Elapsed time is 8.676817 seconds.

(Я знаю, что это случайные матрицы и разница во времени невелика, но я наблюдал эту тенденцию во многих экспериментах).То же самое для реализации на C.

Answer 1

Существует три причины пропуска кэша (3C): принудительная (когда данные не были загружены в строку кэша), конфликт (когда кэш отображает данные в уже занятую строку, в то время как в кэше есть свободное место)) и емкость (когда весь кеш заполнен).

Отображение данных в кеше зависит от степени разложения адреса на две части и объясняет, почему матрицы, размер которых равен 2 ^ k, будут отображать свои строки в идентичные блоки кеша., что приводит к конфликту промахов.Современные компьютеры пытаются решить эту проблему с помощью кэшей с высокой ассоциативностью, но это все же происходит.Использование не степени двух матриц размера является способом расширения матрицы матрицы во всех блоках кеша и предотвращения этой проблемы.

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

Для разложения lu вам нужно обработать несколько n ^ 2 матриц.Если алгоритм хорошо написан, хранение одного мата в кэше может привести к некоторому повышению производительности.Но если ваша матрица имеет размер 8kx8k, то каждая матрица имеет размер 512 МБ, что намного превышает размер кэшей в современных компьютерах.Это также точно такая же ситуация с матрицами 4k (128 МБ), и небольшое различие, которое вы видите в своем тесте, незначительно.Поскольку оптимизация в данном компьютере является статистической, то запуск одной и той же программы несколько раз в настоящее время приводит к разнице во времени выполнения не менее чем на 10-20%.

Для матрицы 1k ситуацияразные.Для этого просто требуется 8 МБ, что соответствует размеру кэша L3 в современной микроархитектуре Pentium.Большинство пропусков будет вызвано конфликтом, а не пропускной способностью, и произойдет эффект очистки кэша 2 ^ k матриц.

Просто последнее замечание.Вы не должны делать тесты, просто используя rand ().Таким образом, rand не будет заполнен, и ваши данные будут случайными.Но время выполнения численных алгоритмов так или иначе зависит от значения данных, и это нарушит точность вашего теста.Используйте rng (seed), чтобы всегда иметь одинаковую последовательность и выполнить несколько тестов.