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

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

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

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

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

Кэш L1 — кеш первого уровня.

Самый быстрый кэш, доступ к нему происходит за 1–3 такта. Находится непосредственно в каждом ядре.

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

Обычно занимает объём 32–64 КБ на каждый экземпляр, при этом экземпляры кэша L1d чаще всего чуть больше экземпляров кэш L1i.

Кэш L2 — кеш второго уровня.

Медленнее L1, доступ к нему происходит за 10–20 тактов. Экземпляр такого кеша быть для каждого ядра свой, а может быть общий для пары ядер. Находится часто не прям в ядре, а на той же части кристала, что и ядро.

Унифицированный кэш, то есть хранит одновременно и инструкции, и данные. Служит буфером между кэшами L1 и L3.

Обычно экземпляр занимает объём 256 КБ – 1 МБ на обычных CPU и 1–2 МБ на современных мощных CPU.

Кэш L3 — кеш третьего уровня.

Значительно медленнее L2, доступ к нему происходит за 30–50 тактов. Располагается на кристале процессора, но является общим для всех ядер. Чаще всего имеет всего один экземпляр.

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

Обычно экземпляр занимает объём 4–8 МБ на обычных CPU и 8–32 МБ на современных мощных CPU.

Вся иерархия кэшей работает примерно по следующему принципу. Сначала ядро процессора ищет данные или инструкцию в кэше L1. Если в кэше L1 нет нужной информации, то есть если случился промах в кэше L1, то ядро обращается к кэшу L2. Если данных или инструкции нет и в кэше L2, то ядро обращается в L3. И только в случае промаха во всех уровнях происходит обращение к оперативной памяти. При этом найденные данные поднимаются наверх по иерархии.

Посмотреть на количество экземпляров кэшей и их размер на вашем компьютере (в linux) можно с помощью команды

Линия кэша (cache line) — минимальная единица обмена данными между уровнями кэша и оперативной памятью. Размер линии кэша у большинства процессоров составляет 64 байта.

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

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

Прямая ассоциативность или прямо отображаемый кэш (direct-mapped cache).

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

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

Полная ассоциативность (fully associative cache).

Каждая линия из памяти может быть помещена в любое место кэша.

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

Частично-ассоциативный кэш (set associative cache).

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

Здесь убираются недостатки предыдущих типов ассоциативности.

Именно такой тип ассоциативности используется в современных процессорах. Кэш L1 является 8-канальным или полностью ассоциативным. Кэш L2 может иметь 8 или 16 каналов. Кэш L3 может иметь от 12 до 32 каналов.

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

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

В моем примере программа, прибавляющая ко всем элементам массива $1$, использует оба режима доступа: сначала читает из памяти значение элемента, а потом записывает в память результат инкремента.

Давайте разграничим режимы доступа к памяти

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

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

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

Современные процессоры имеют 2–4 порта LSU, каждый порт может обрабатывать 1 операцию за такт. В случае с одновременной работы в обоих режимах каждая операция store зависит от операций load, поэтому высокой эффективность здесь добиться не получится.

Кэш L1 разделён на 6–8 банков — независимых модулей памяти, которые могут параллельно обслуживать операции доступа. Один банк может обслуживать 1 операцию за такт. Даже если в процессоре есть свободные порты LSU, они могут и не работать параллельно, если оба обращения идут в один банк памяти кэша L1.

Кэш L2. Кэш L2 находится за пределами ядра, но на том же кристале. Шины всё еще достаточно широкие и двунаправленные. Расстояние от кэша L2 до кэша L1 и до ядра приличное, но не очень большое.

В одном режиме работы заметной разницы между кэшем L2 и кэшем L1 практически нет: префетчер прекрасно обнаруживает шаблон доступа и подгружает все данные в кеш.

В смешанном режиме префетчер не может эффективно работать со смешанной нагрузкой, потому что шаблон доступа к памяти становится сложнее, когда чередуются операции чтения и записи. Также кэш L2 имеет ограниченные буферы для отслеживания шаблонов, поэтому смешанный режим в $2$ раза быстрее заполнит эти буферы.

Промахи в кеше L1, конечно, тоже играют свою роль, но их вклад незначительный из-за физической близости кешей L1 и L2.

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

При операции записи в L3 требуется инвалидировать соответствующие строки в кеши L1 и L2 других ядер, что порождает дополнительные транзакции по межядерной шине. Получается, что операция записи требует несколько транзакций (минимум invalidation request, acknowledge, write data).

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