Распределитель плит Linux и производительность кеша
Из руководства по пониманию ядра Linux 3-е издание, глава 8.2.10, Окрашивание плит
Из главы 2 мы знаем, что одна и та же строка аппаратного кэша отображает много разных блоков оперативной памяти. В этой главе мы также увидели, что объекты одинакового размера в конечном итоге хранятся с одинаковым смещением в кэше. Объекты с одинаковым смещением в разных слобах с относительно высокой вероятностью будут отображаться в одной и той же строке кэша. Следовательно, аппаратное обеспечение кеша может тратить циклы памяти, перенося два объекта из одной и той же строки кеша назад и вперед в разные места ОЗУ, тогда как другие строки кеша используются недостаточно. Распределитель плиты пытается уменьшить это неприятное поведение кэша с помощью политики, называемой окраской плиты: разные плиты называются цветами.
(1) Я не могу понять проблему, которую пытается решить окраска плиты. Когда нормальный процесс обращается к данным, если он не находится в кеше, и обнаруживается пропадание кеша, данные извлекаются в кеш вместе с данными из окружающего адреса данных, к которым процесс пытается обратиться, чтобы повысить производительность. Как может возникнуть ситуация, когда одни и те же строки кэша продолжают меняться? вероятность того, что процесс продолжает обращаться к двум разным адресам данных с одинаковым смещением в области памяти двух разных областей памяти, очень мала. И даже если это случается, политики кэширования обычно выбирают строки, которые должны быть заменены в соответствии с какой-либо программой, такой как LRU, Random и т. Д. Не существует такой политики, которая выбирает исключать строки в соответствии с соответствием в младших значащих битах адресов, к которым осуществляется доступ,
(2) Я не могу понять, как раскраска перекрытия, которая переносит свободные байты от конца перекрытия к началу и приводит к тому, что разные перекрытия с разными смещениями для первых объектов решают проблему замены кэша?
[Решено] после небольшого расследования я считаю, что нашел ответ на свой вопрос. Ответ опубликован.
2 ответа
Я думаю, что я понял, ответ связан с ассоциативностью.
Кэш может быть разделен на определенные наборы, каждый набор может кэшировать в нем только определенный тип блоков памяти. Например, set0 будет содержать блоки памяти с адресами, кратными 8, set1 будет содержать блоки памяти с адресами, кратными 12. Причина этого заключается в повышении производительности кэша, чтобы избежать ситуации, когда каждый адрес просматривается по всему кешу, Таким образом, нужно искать только определенный набор кеша.
Теперь по ссылке Понимание кеширования процессора и производительности
На странице 377 Хенесси и Паттерсона формула размещения кэша выглядит следующим образом: (Адрес блока) MOD (Количество наборов в кэше)
Давайте возьмем адрес блока памяти 0x10000008 (из slabX с цветом C) и адрес блока памяти 0x20000009 (из плиты с цветом Z). Для большинства N (количество наборов в кеше), расчет для <address> MOD <N> даст другое значение, следовательно, другой набор для кэширования данных. Если адреса были с одинаковыми младшими значащими битами (например, 0x10000008 а также 0x20000008) тогда для большинства N вычисление даст одинаковое значение, следовательно, блоки будут сталкиваться с одним и тем же набором кэша.
Таким образом, сохраняя различное смещение (цвета) для объектов в разных перекрытиях, объекты перекрытий потенциально могут достигать разных наборов в кеше и не будут сталкиваться с одним и тем же набором, а общая производительность кэша повышается.
РЕДАКТИРОВАТЬ: Кроме того, если кэш-память с прямым отображением, то в соответствии с википедией, CPU Cache, политики замены кэша не существует, и вычисление по модулю дает блок кэша, в который будет сохранен блок памяти:
Кэш с прямым отображением В этой организации кеша каждое место в основной памяти может помещаться только в одну запись в кеше. Следовательно, кэш с прямым отображением также можно назвать "ассоциативным односторонним набором". У него нет политики замены как таковой, так как нет выбора, какую часть содержимого кэша удалять. Это означает, что если два местоположения отображаются на одну и ту же запись, они могут постоянно выбивать друг друга. Несмотря на то, что кэш с прямым отображением должен быть намного больше, чем ассоциативный, чтобы обеспечить сопоставимую производительность, он более непредсказуем. Пусть x будет номером блока в кэше, y будет номером блока памяти и nbe количеством блоков в кэше, тогда сопоставление выполняется с помощью уравнения x = y mod n.
После долгого изучения и размышлений я получил объяснение, казалось бы, более разумное, не только на конкретных примерах адресов. Во-первых, вы должны изучить базовые знания, такие как кеш, тег, наборы, выделение строк.
Несомненно, что единицей colour_off является cache_line_size из кода ядра Linux. colour_off - основная единица смещения и colour это номер colour_off в структуре kmem_cache.
int __kmem_cache_create (struct kmem_cache *cachep, unsigned long flags)
cachep->align = ralign;
cachep->colour_off = cache_line_size(); // colour_off's unit is cache_line_size
/* Offset must be a multiple of the alignment. */
if (cachep->colour_off < cachep->align)
cachep->colour_off = cachep->align;
.....
err = setup_cpu_cache(cachep, gfp);
https://elixir.bootlin.com/linux/v4.6/source/mm/slab.c
Таким образом, мы можем проанализировать это в двух случаях. Первый - cache > slab. Вы видите, что slab 1, slab2, slab3... не имеет возможности столкнуться в основном из-за того, что кеш достаточно велик, за исключением slab1 vs slab5, которые могут столкнуться. Так что механизм окраски не так понятен для улучшения характеристик корпуса. Но с slab1 и slab5 мы просто игнорируем, чтобы объяснить, почему, я уверен, что вы решите это, прочитав следующее.
Второй - это slab > cache.
Пустая строка означает строку color_off или cache. Ясно, что slab1 и slab2 не имеют возможности столкнуться на линиях, подписанных галочкой, а также slab2 slab3. Мы гарантируем, что механизм раскраски оптимизирует две линии между двумя соседними плитами, а тем более slab1 по сравнению с slab3, которые оптимизируют больше линий, 2+2 = 4 линии, вы можете посчитать.
Подводя итог, механизм раскраски оптимизирует производительность кеша (детально просто оптимизируйте некоторые строки colour_off в начале и конце, а не другие строки, которые все еще могут конфликтовать), используя изначально бесполезную память, насколько это возможно.
Допустим, у вас есть кэш-память объемом 256 КБ, и он использует супер-простой алгоритм, в котором он делает строку кеша = (реальный адрес AND 0x3FFFFF).
Теперь, если у вас есть плиты, начинающиеся на границе каждого мегабайта, тогда элемент 20 в Плите 1 вытолкнет Элемент 20 из Плиты 2 из кэша, потому что они используют тот же тег строки кэша.
Благодаря смещению плит становится менее вероятно, что разные плиты будут использовать один и тот же тег строки кэша. Если Slab 1 и Slab 2 оба содержат 32-байтовые объекты, а Slab 2 смещен на 8 байтов, его метки кэша никогда не будут в точности равны меткам Slab 1.
Я уверен, что некоторые детали неверны, но примите это за то, что оно того стоит.