Логическая организация кэш-памяти процессора

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

Кэш память процессора используется для уменьшения времени простоя процессора при обращении к RAM.

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

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



Так вот суть кэширования состоит в разбиении RAM на кэш-линии и отображении их на кэш-линии кэш-памяти. Возможно несколько вариантов такого отображения.


DIRECT MAPPING


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



Блоки RAM из разных сегментов, но с одинаковыми номерами в этих сегментах, всегда будут отображаться на одну и ту же кэш-линию кэша:



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

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

b — размер кэш-линии.
m — количество кэш-линий в кэше.

Для адресации b байт внутри каждой кэш-линии потребуется: log2b бит.
Для адресации m кэш-линий внутри каждого сегмента потребуется: log2m бит.

m = Объем кэш-памяти/Размер кэш линии.

Для адресации N сегментов RAM: log2N бит.

N = Объем RAM/Размер сегмента.

Для адресации байта потребуется: log2N + log2m + log2b бит.

Этапы поиска в кэше:
1. Извлекается средняя часть адреса (log2m), определяющая номер кэш-линии в кэше.
2. Тэг кэш-линии с данным номером сравнивается со старшей частью адреса (log2N).

Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.

FULLY ASSOCIATIVE MAPPING


Основная идея полностью ассоциативного отображения (fully associative mapping) RAM на кэш-память состоит в следующем: RAM делится на блоки, размер которых равен размеру кэш-линий, а каждый блок RAM может сохраняться в любой кэш-линии кэша:



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

Тэг (tag) каждой кэш-линии хранит старшую часть адреса первого байта в данной кэш-линии.

b — размер кэш-линии.
m — количество кэш-линий, умещающихся в RAM.

Для адресации b байт внутри каждой кэш-линии потребуется: log2b бит.
Для адресации m кэш-линий: log2m бит.

m = Размер RAM/Размер кэш-линии.

Для адресации байта потребуется: log2m + log2b бит.

Этапы поиска в кэше:
1. Тэги всех кэш-линий сравниваются со старшей частью адреса одновременно.

Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.

SET ASSOCIATIVE MAPPING


Основная идея наборно ассоциативного отображения (set associative mapping) RAM на кэш-память состоит в следующем: RAM делится также как и в прямом отображении, а сам кэш состоит из k кэшей (k каналов), использующих прямое отображение.



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

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



Структура адреса байта в точности такая же, как и в прямом отображении: log2N + log2m + log2b бит, но т.к. set представляет собой k различных кэш-линий, то поиск в кэше немного отличается.

Этапы поиска в кэше:
1. Извлекается средняя часть адреса (log2m), определяющая номер сэта в кэше.
2. Тэги всех кэш-линий данного сета сравниваются со старшей частью адреса (log2N) одновременно.

Если было совпадение по одному из тэгов, то произошло кэш-попадание.
Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.

Т.о количество каналов кэша определяет количество одновременно сравниваемых тэгов.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 10

    +1
    Очень интересно. А есть информация, какие варианты отображения у конкретных современных процессоров?
      +4
      В линуксе это можно посмотреть тут
      /sys/devices/system/cpu/cpuX/cache/indexY/Z
      где Х — интересующее ядро
      Y интересующий кеш (L1 instruction, L1 data, L2, L3)
      Z — что конкретно интересует
      У меня под рукой, например, xeon X5650, посмотрим как устроен L1 data кеш
      cat /sys/devices/system/cpu/cpu0/cache/index0/size
      32K — его размер
      cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
      8 — ассоциативность сета
      cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
      64 — кол-во этих сетов
      cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
      64 — размер кеш линии

      0
      Топик интересный с точки зрения теории. А практически как можно использовать эту информацию?
        +1
        С точки зрения оптимизации — cache obvious / conscious алгоритмы. Борьба с false sharing.
          0
          Можете расшифровать?
            +1
            Cache obvious — алгоритмы, принимающие во внимание абстрактный кеш (приблизительно размер линеек, выравнивание)
            Cache conscious — плюс нюансы работы конкретного железа
            False sharing — несколько хардворных нитей состязаются за данные в одной линейке, в результате все идут прямиком в рамять

            Как-то так.
        0
        Выравнивать данные на границу кэш линии, например.
        Статические данные;
        Структуры;
        Динамические данные.
        Для разных типов у вас будет разные приемы для выравнивания.
        К тому же стоит иметь виду — если у вас массив структур, и вы работаете только с одним элементом структуры в цикле, то процессор всегда будет загружать кеш линию целиком — и ваша ПСП просядет соответственно. Поэтому массивы структур переделывают в структуры массивов.
          0
          Буквально сегодня утром смотрел лекцию на coursera об этом. Курс супер, так что в продолжение статьи — рекомендую!
            +1
            Вы забыли упомянуть cache aliasing и связанный с ним cache coloring — бич систем с MMU и кешем большого размера с малым количеством веев.
              +2
              Что касается практического использования данного материала…
              Код можно оптимизировать на уровне алгоритма, а можно и на уровне архитектурных особенностей конкретного процессора. Знания принципов работы кэша позволяют оптимальнее размещать данные в памяти.

              В качестве примера я написал тестовую программу. Ключевой в этой программе является функция: void xchg (uint8_t slow_factor, uint32_t step). slow_factor — количество сегментов памяти, step — разнос адресов между обрабатываемыми байтами. Увеличивая slow_factor — мы смоделируем ситуацию, когда для обработки одного байта будет считываться новая кэш-линия целиком.

              Результаты:
              root@proliant:~/cahe# gcc cache.c -O3 -o cache

              root@proliant:~/cahe# ./cache
              xchg() complited in 3 sec, k = 1400000000.
              xchg() complited in 3 sec, k = 1400000000.
              xchg() complited in 14 sec, k = 1400000000.
              xchg() complited in 13 sec, k = 1400000000.

              Отсюда видно что при использовании функции xchg() со slow_factor большим, чем 1, производительность сильно проседает, хотя количество итераций постоянно и не зависит от slow_factor!

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

              #include <stddef.h>
              #include <inttypes.h>
              #include <sys/types.h>
              #include <stdlib.h>
              #include <stdio.h>
              #include <stdlib.h>
              #include <sys/time.h>
              
              #define WAY_N 8U				// number of ways
              #define LINE_SIZE 64U				// cache line size
              #define LINE_N 64U				// number of cache line
              
              #define SPARSE WAY_N*LINE_SIZE*LINE_N
              #define DENSE  LINE_SIZE*LINE_N
              
              #define AREA 29U*WAY_N*LINE_SIZE*LINE_N		// allocated memory size
              
              static uint8_t *p, *el, tmp;
              
              
              void xchg (uint32_t slow_factor, uint32_t step) {
              	uint32_t i, j, k;
              	struct timeval start, end, diff;
              
              	gettimeofday(&start, NULL);
              
              	for (i = 0U, k = 0U, el = p; i < 200000000U/slow_factor; ++i) {
              		for (j = 0U; j < 7U*slow_factor; ++j, el += step, ++k) {
              			tmp = *el;
              			*el = *(el + step);
              			*(el + step) = tmp;
              		}
              		el = p;
              	}
              
              	gettimeofday(&end, NULL);
              
              	diff.tv_sec  = end.tv_sec - start.tv_sec;
              
              	printf (" xchg() complited in %ld sec, k = %u.\n", diff.tv_sec, k);
              }
              
              
              int main(int argc, char const **argv) {
              	uint32_t i;
              	
              	p = el = calloc (1, AREA);
              
              	for (i = 0U; i < AREA; ++i) {
              		*el++ = (uint8_t) rand();
              	}
              
              	xchg (1U, SPARSE);
              	xchg (1U, DENSE);
              	xchg (4U, SPARSE);
              	xchg (4U, DENSE);
              
              	return 0;
              }
              

              Only users with full accounts can post comments. Log in, please.