Каково поведение кэша L1/L2 для LUT и тому подобного?

Question

Предполагая, что LUT скажем 512 КБ 64-битных двойных типов. Вообще говоря, как процессор кэширует структуру в L1 или L2?

Например: я обращаюсь к среднему элементу, он пытается кэшировать весь LUT или только некоторые из них - скажем, средний элемент, а затем n последующих элементов?

Какие алгоритмы использует процессор, чтобы определить, что он хранит в кеше L2? Существует ли определенная стратегия прогнозирования

Примечание: я предполагаю x86, но мне было бы интересно узнать, как работают другие архитектуры POWER, SPARC и т. Д.

Answer 1

Это зависит от структуры данных, которую вы используете для LUT (справочная таблица?)

Кэши лучше всего работают с вещами, которые расположены непрерывно в памяти (например, в виде массивов или std::vectors), а не разбросаны вокруг.

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

Как правило, существует несколько уровней кеша, образующих иерархию. С каждым уровнем время доступа увеличивается, но увеличивается и емкость.

Да, есть перспектива, которая ограничена довольно упрощенными алгоритмами и невозможностью пересекать границы страницы (размер страницы памяти на x86 обычно составляет 4 КБ.)

Я предлагаю вам прочитать то, что каждый программист должен знать о памяти. Он имеет много полезной информации по этому вопросу.

Answer 2

Кэши обычно формируются как набор строк кеша. Гранулярность каждой строки кэша выравнивается по размеру строки кэша, поэтому, например, кэш со строкой кэша 128 байтов будет иметь адрес, для которого данные кэширования выровнены, до 128 байтов.

Кэш-память ЦП обычно использует некоторый механизм вытеснения LRU (используется в последнее время, например, при удалении самой старой строки кеша при пропадании кеша), а также имеет некоторое отображение адреса памяти в конкретный набор строк кеша. (Это приводит к одной из многих ложных ошибок совместного использования в x86, если вы пытаетесь читать с нескольких адресов, выровненных по границе 4k или 16M.)

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