Как работают строки кэша?

169

Я понимаю, что процессор вводит данные в кеш через строки кеша, которые - например, на моем процессоре Atom - за один раз выдают примерно 64 байта, независимо от размера считываемых данных.

Мой вопрос:

Представьте, что вам нужно прочитать один байт из памяти, какие 64 байта будут занесены в кеш?

Я вижу две возможности: либо 64 байта начинаются с ближайшей границы в 64 байта ниже интересующего байта, либо 64 байта распределяются по байту некоторым заранее определенным образом (например, наполовину меньше, наполовину выше или все выше).

Что это?

Norswap
источник
22
Прочитайте это: Что каждый программист должен знать о памяти . Тогда прочитайте это снова. Лучший (pdf) источник здесь .
Андерсой

Ответы:

129

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

Современные модули памяти ПК передают 64 бита (8 байт) за раз, причем пакет из восьми передач выполняет одну операцию, поэтому одна команда запускает чтение или запись полной строки кэша из памяти. (Размер пакетной передачи DDR1 / 2/3/4 SDRAM настраивается до 64B; ЦП выбирают размер пакетной передачи, чтобы соответствовать размеру их строки кэша, но 64B обычно)

Как правило, если процессор не может предсказать доступ к памяти (и предварительно извлечь его), процесс поиска может занять ~ 90 наносекунд или ~ 250 тактов (от ЦП, знающего адрес, до ЦП, получающего данные).

Напротив, попадание в кэш L1 имеет задержку загрузки 3 или 4 цикла, а перезагрузка магазина имеет задержку пересылки магазина 4 или 5 циклов на современных процессорах x86. Вещи похожи на другие архитектуры.

Дальнейшее чтение: Ульрих Дреппер, что каждый программист должен знать о памяти . Рекомендации по программной предварительной выборке несколько устарели: современные программы предварительной выборки HW умнее, а гиперпоточность намного лучше, чем в дни P4 (поэтому поток предварительной выборки обычно является пустой тратой). Так же Tag Wiki имеет множество ссылок на производительность для этой архитектуры.

Юджин Смит
источник
1
Этот ответ не имеет абсолютно никакого смысла. Что делать с 64-битной (!) Пропускной способностью 64-битной полосы памяти (что также неправильно) в этом отношении? Кроме того, от 10 до 30 нс также совершенно неверны, если вы попали в баран. Это может быть верно для кэша L3 или L2, но не для оперативной памяти, где она больше похожа на 90 нс. То, что вы имеете в виду, - это время пакета - время доступа к следующему четверному слову в режиме пакета (что на самом деле является правильным ответом)
Мартин Керстен
5
@MartinKersten: один канал DDR1 / 2/3/4 SDRAM использует 64-битную шину данных. Пакетная передача всей строки кэша занимает восемь передач по 8B каждая, и это именно то, что происходит на самом деле. Возможно, все еще правильно, что процесс оптимизируется путем передачи блока, выровненного по 8B, содержащего вначале желаемый байт, то есть запуска пакета в нем (и обтекания, если это не были первые 8B размера передачи пакета). Современные процессоры с многоуровневыми кэшами, вероятно, больше этого не делают, потому что это будет означать раннюю ретрансляцию первого блока (блоков) в кэш L1.
Питер Кордес
2
У Haswell есть путь 64B между кэшем L2 и L1D (т. Е. Полная ширина строки кэша), поэтому передача 8B, содержащего запрошенный байт, приведет к неэффективному использованию этой шины. @Martin также правильно о времени доступа для загрузки, которая должна идти в основную память.
Питер Кордес
3
Хороший вопрос о том, попадают ли данные сразу вверх по иерархии памяти или L3 ждет полной строки из памяти, прежде чем начать отправлять ее до L2. Существуют буферы передачи между различными уровнями кэша, и каждый ожидающий промах требует один. Таким образом ( полное предположение), вероятно, L3 помещает байты из контроллера памяти в свой собственный буфер приема одновременно с помещением их в соответствующий буфер загрузки для кэша L2, который его хотел. Когда строка полностью перенесена из памяти, L3 уведомляет L2 о том, что строка готова, и копирует ее в свой собственный массив.
Питер Кордес
2
@Martin: я решил пойти дальше и отредактировать этот ответ. Я думаю, что теперь это более точно, и все еще просто. Будущие читатели: см. Также вопрос Mike76 и мой ответ: stackoverflow.com/questions/39182060/…
Питер Кордес
22

Если строки кэша имеют ширину 64 байта, то они соответствуют блокам памяти, которые начинаются с адресов, кратных 64. Наименее значимые 6 бит любого адреса являются смещением в строке кэша.

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

Хотя это делается аппаратно, мы можем показать расчеты, используя некоторые определения макросов C:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)
Kaz
источник
1
Мне трудно понять это. Я знаю, что это 2 года спустя, но не могли бы вы дать пример кода для этого? одна или две строки.
Ник
1
@Nick Причина, по которой этот метод работает, заключается в двоичной системе счисления. Любая степень 2 имеет только один установленный бит и все оставшиеся биты очищены, поэтому для 64 вы 0b1000000заметили, что последние 6 цифр являются нулями, поэтому даже если у вас есть какое-то число с любым из этих 6 наборов (которые представляют число % 64), очистка их даст вам ближайший 64-байтовый выровненный адрес памяти.
legends2k
21

Прежде всего, доступ к основной памяти очень дорогой. В настоящее время процессор с частотой 2 ГГц (самый медленный один раз) имеет такты 2 Гц (циклов) в секунду. Процессор (виртуальное ядро ​​в настоящее время) может извлекать значение из своих регистров один раз за такт. Поскольку виртуальное ядро ​​состоит из нескольких блоков обработки (ALU - арифметико-логический блок, FPU и т. Д.), Оно может фактически обрабатывать определенные инструкции параллельно, если это возможно.

Доступ к основной памяти стоит около 70 нс до 100 нс (DDR4 немного быстрее). На этот раз в основном ищем кеш L1, L2 и L3 и затем попадаем в память (посылаем команду контроллеру памяти, которая отправляет его в банки памяти), ждем ответа и все готово.

100 нс означает около 200 тиков. Таким образом, в основном, если программа всегда будет пропускать кеши, к которым обращается каждая память, центральный процессор будет тратить около 99,5% своего времени (если он только читает память) в ожидании памяти.

Для ускорения работы предусмотрены кэши L1, L2, L3. Они используют память, непосредственно размещенную на чипе, и используют различные типы транзисторных схем для хранения данных битов. Это занимает больше места, больше энергии и является более дорогостоящим, чем основная память, поскольку ЦП обычно создается с использованием более продвинутой технологии, и производственный сбой в памяти L1, L2, L3 имеет возможность сделать ЦП бесполезным (дефект), поэтому большие кэши L1, L2, L3 увеличивают частоту ошибок, что снижает выход, что напрямую снижает ROI. Таким образом, существует огромный компромисс, когда дело доходит до доступного размера кэша.

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

Чтобы дать представление о времени (источник: затраты на доступ к кешам и памяти )

  • Кэш-память первого уровня: от 1 до 2 нс (2-4 цикла)
  • Кэш-память второго уровня: от 3 до 5 нс (6-10 циклов)
  • Кэш-память третьего уровня: от 12 до 20 нс (24-40 циклов)
  • Оперативная память: 60 нс (120 циклов)

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

Таким образом, кеш существенно ускоряет доступ к памяти (60 нс против 1 нс).

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

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

Но помимо простой копии памяти другой последовательный доступ к памяти был довольно распространенным. Примером является анализ ряда информации. Наличие массива целых чисел и вычисление суммы, среднего, среднего или даже более простого нахождения определенного значения (фильтр / поиск) были еще одним очень важным классом алгоритмов, запускаемых каждый раз на любом центральном процессоре общего назначения.

Таким образом, при анализе схемы доступа к памяти стало очевидно, что данные читаются последовательно очень часто. Была высокая вероятность того, что если программа читает значение по индексу i, программа также будет читать значение i + 1. Эта вероятность немного выше, чем вероятность того, что та же программа также прочитает значение i + 2 и так далее.

Таким образом, учитывая адрес памяти, было (и остается) хорошей идеей читать вперед и извлекать дополнительные значения. Это причина, почему есть режим повышения.

Доступ к памяти в режиме повышения означает, что адрес отправляется, а несколько значений отправляются последовательно. Каждая дополнительная отправка значения занимает всего около 10 нс (или даже ниже).

Еще одной проблемой был адрес. Отправка адреса занимает время. Чтобы адресовать большую часть памяти, необходимо отправить большие адреса. В первые дни это означало, что адресная шина была недостаточно большой для отправки адреса за один цикл (тик), и для отправки адреса требовалось более одного цикла, добавляя больше задержки.

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

Другая проблема, которую решает строка кэша (помимо чтения вперед и сохранения / освобождения шести битов на адресной шине), заключается в том, как организован кэш. Например, если кэш будет разделен на 8-байтовые (64-битные) блоки (ячейки), необходимо хранить адрес ячейки памяти, для которой эта ячейка кэша содержит значение вместе с ней. Если адрес также будет 64-битным, это означает, что половина размера кэша используется адресом, что приводит к накладным расходам в 100%.

Поскольку длина строки кэша составляет 64 байта, а процессор может использовать 64 бита - 6 бит = 58 бит (нет необходимости хранить нулевые биты слишком правильно), это означает, что мы можем кэшировать 64 байта или 512 бит с объемом служебной информации 58 бит (11% служебной нагрузки). В действительности хранимые адреса даже меньше, чем это, но есть информация о состоянии (например, является ли строка кэша действительной и точной, грязной и требует обратной записи в оперативной памяти и т. Д.).

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

Особенно важно синхронизировать доступ к кэш-памяти / памяти между различными виртуальными ядрами, их независимыми несколькими процессорами на ядро ​​и, наконец, несколькими процессорами на одной материнской плате (в которой есть до 48 процессорных плат и более).

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

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

Мартин Керстен
источник
1
Ассоциативный кэш набора использует некоторые адресные биты для выбора набора, поэтому теги могут быть даже короче, чем ваш пример. Конечно, кэш также должен отслеживать, какой тег идет с каким массивом данных в наборе, но обычно в наборе есть больше наборов, чем путей. (Например, 8-канальный ассоциативный L1D-кэш 32 КБ с 64-разрядными строками в процессорах Intel x86: смещение 6 бит, индекс 6 бит. Тэги должны иметь ширину только 48-12 бит, потому что x86-64 (на данный момент) имеет только 48- битовые физические адреса. Как я уверен, вы знаете, что неслучайно, что младшие 12 бит - это смещение страницы, поэтому L1 может быть VIPT без псевдонимов.)
Питер Кордес
Удивительный ответ, приятель ... есть ли где-нибудь кнопка "Мне нравится"?
Эдгард Лима
@ EdgardLima, а не кнопка upvote?
Пейсер
6

Процессоры могут иметь многоуровневые кэши (L1, L2, L3), и они различаются по размеру и скорости.

Тем не менее, чтобы понять, что именно входит в каждый кеш, вам нужно изучить предиктор ветвления, используемый этим конкретным процессором, и то, как инструкции / данные вашей программы ведут себя против него.

Читайте о предсказателе ветки , о кеше процессора и о политиках замены .

Это не простая задача. Если в конце дня вам нужен только тест производительности, вы можете использовать такой инструмент, как Cachegrind . Однако, поскольку это симуляция, ее результат может в некоторой степени отличаться.

jweyrich
источник
4

Я не могу сказать наверняка, поскольку каждое оборудование отличается, но обычно это «64 байта начинаются с ближайшей границы 64 байта ниже», поскольку это очень быстрая и простая операция для ЦП.

bramp
источник
2
Я могу сказать наверняка. Любой разумный дизайн кэша будет иметь строки с размерами, равными степени 2, и которые естественно выровнены. (например, 64B выровнен). Это не просто быстро и просто, это буквально бесплатно: вы просто игнорируете, например, младшие 6 бит адреса. Кеши часто делают разные вещи с разными диапазонами адресов. (например, кэш заботится о тэге и индексе для определения попадания и промаха, затем использует только смещение в пределах строки кеша для вставки / извлечения данных)
Питер Кордес