Наборно-ассоциативный кэш

Наборно-ассоциативный кэш (англ. set-associative cache) — это тип кэш-памяти, в котором каждая строка основной памяти может быть размещена в ограниченном, фиксированном множестве строк кэша, называемом набором (set). Данный подход является компромиссом между кэшем прямого отображения (direct-mapped cache) и полностью ассоциативным кэшем (fully associative cache), обеспечивая баланс между скоростью поиска, сложностью аппаратной реализации и вероятностью промахов (cache misses).

Принцип работы

В наборно-ассоциативном кэше память делится на блоки (строки) фиксированного размера. Кэш, в свою очередь, организован в виде матрицы: строки кэша сгруппированы в наборы, каждый из которых содержит определённое число «путей» (ways). Количество путей в наборе обозначается как n и определяет ассоциативность кэша (например, 2-путевой, 4-путевой, 8-путевой кэш).

Адрес памяти, по которому происходит обращение, делится на три части:

• Смещение (offset) — указывает на конкретный байт внутри блока.
• Индекс (index) — определяет номер набора в кэше, в который может быть помещён блок.
• Тег (tag) — уникальный идентификатор, позволяющий различать блоки, хранящиеся в одном наборе.

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

Классификация по ассоциативности

Наборно-ассоциативные кэши классифицируются по числу путей в наборе:

• Кэш прямого отображения (1-путевой) — каждый набор состоит из одной строки. Это частный случай наборно-ассоциативного кэша с ассоциативностью 1. Простейший в реализации, но страдает от конфликтных промахов (когда два часто используемых блока отображаются в один и тот же набор).
• 2-путевой кэш — каждый набор содержит две строки. Уменьшает количество конфликтных промахов по сравнению с прямым отображением.
• 4-путевой, 8-путевой, 16-путевой кэш — более высокая ассоциативность. Снижает вероятность промахов, но увеличивает сложность схем сравнения тегов и энергопотребление.
• Полностью ассоциативный кэш — частный случай, когда все строки кэша образуют один набор. Максимальная гибкость, но требует сложной схемы параллельного сравнения всех тегов, что ограничивает размер кэша.

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

История и развитие

Концепция кэш-памяти была впервые предложена Морисом Уилксом в 1965 году в статье «Slave Memories and Dynamic Storage Allocation». Ранние реализации кэшей (например, в IBM System/360 Model 85, 1968 год) использовали полностью ассоциативную организацию, что было оправдано при небольших объёмах кэша (до нескольких килобайт).

С ростом размеров кэш-памяти (десятки и сотни килобайт) полностью ассоциативные схемы стали слишком дорогими из-за необходимости большого количества компараторов. В 1970-х годах начали применяться кэши прямого отображения, однако они показали высокую частоту конфликтных промахов. Наборно-ассоциативная архитектура, впервые реализованная в микропроцессорах в 1980-х годах (например, Intel 80486 использовал 8-килобайтный 4-путевой наборно-ассоциативный кэш), стала стандартом де-факто для современных процессоров.

Устройство и аппаратная реализация

Основные компоненты наборно-ассоциативного кэша:

• Массив тегов (tag array) — хранит теги для каждой строки кэша. Для каждого набора имеется n ячеек тегов.
• Массив данных (data array) — хранит собственно кэшированные блоки данных. Организован аналогично массиву тегов.
• Схема декодирования индекса — выбирает нужный набор на основе битов индекса адреса.
• Набор компараторов — параллельно сравнивает теги выбранного набора с тегом запроса. Количество компараторов равно числу путей.
• Мультиплексор — выбирает данные из того пути, где тег совпал (или из пути, выбранного алгоритмом замещения при промахе).
• Управляющая логика — реализует алгоритмы замещения (LRU, псевдо-LRU, случайный, FIFO) и обновления состояния кэша.

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

Алгоритмы замещения

При промахе кэша необходимо решить, какую из строк в выбранном наборе заместить новым блоком. Основные алгоритмы:

• LRU (Least Recently Used) — замещается строка, к которой дольше всего не было обращений. Обеспечивает хорошую локальность, но требует хранения информации о порядке использования для каждого набора (для n-путевого кэша — n! состояний, что сложно для n>4).
• Псевдо-LRU — аппроксимация LRU с меньшим числом состояний (например, с использованием битовой матрицы или дерева). Часто применяется в кэшах с ассоциативностью 8 и выше.
• Случайный (Random) — замещается случайная строка из набора. Прост в реализации, но может приводить к неоптимальной производительности.
• FIFO (First In, First Out) — замещается строка, загруженная раньше всех. Не учитывает частоту обращений.

В современных процессорах (например, Intel Core, AMD Ryzen) для кэшей L1 и L2 обычно используется псевдо-LRU, а для кэша L3 — более сложные алгоритмы, иногда с учётом частоты обращений (adaptive replacement policy).

Применение

Наборно-ассоциативные кэши используются во всех современных микропроцессорах общего назначения (x86, ARM, RISC-V), графических процессорах (GPU), микроконтроллерах, а также в системах на кристалле (SoC). Конкретные параметры кэша (размер, ассоциативность, размер строки) варьируются в зависимости от уровня иерархии:

• Кэш L1 (обычно 32–64 КБ на ядро) — часто 4–8-путевой, с размером строки 64 байта. Ориентирован на минимальную задержку (2–4 такта).
• Кэш L2 (256 КБ – 1 МБ на ядро) — 8–16-путевой, с задержкой 10–20 тактов.
• Кэш L3 (несколько мегабайт, общий для всех ядер) — 16–20-путевой, иногда с использованием кольцевой шины (ring bus) для доступа.

В процессорах Intel (начиная с архитектуры Nehalem, 2008 год) и AMD (начиная с Zen, 2017 год) кэш L3 является неинклюзивным, то есть не обязательно содержит копии данных из L1/L2, что позволяет эффективнее использовать доступную площадь кристалла.

Преимущества и недостатки

Преимущества:

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

Недостатки:

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

Интересные факты

• В процессорах ARM Cortex-A78 (2020 год) используется 32-килобайтный 4-путевой кэш L1 для данных и 32-килобайтный 4-путевой кэш L1 для инструкций.
• В суперкомпьютерах и серверных процессорах (например, Intel Xeon Platinum 9200) кэш L3 может достигать 77 МБ при ассоциативности 20–24 пути.
• В некоторых встраиваемых системах (например, на базе ARM Cortex-M) кэш отсутствует вовсе, так как программы и данные хранятся непосредственно в SRAM или Flash-памяти.
• Исследования показывают, что для большинства рабочих нагрузок увеличение ассоциативности свыше 8–16 путей даёт незначительный прирост производительности, но существенно увеличивает площадь и энергопотребление.