Краткий анализ архитектуры кэш‑памяти в современных CPU — уровни, политики, влияние на локальность и примеры программ.
1) Уровни и их свойства
- L1: очень быстрая, малая, чаще разделена на инструкц./данные. Типично размеры $32\text{–}64\mathrm{KiB}$, задержка $\sim 1\text{–}5$ циклов.
- L2: средняя по объёму и латентности, часто приватная на ядро. Типично $256\mathrm{KiB}\text{–}1\mathrm{MiB}$, задержка $\sim 10\text{–}30$ циклов.
- L3 (или LLC): общий для нескольких/всех ядер, крупный, более медленный. Типично $2\text{–}64\mathrm{MiB}$, задержка $\sim 30\text{–}200$ циклов.
- Память (DRAM): задержка сотни циклов, пропускная способность ниже уровня кэшей.
2) Политики записи и замещения
- Запись: write‑back (обычно) vs write‑through; write‑allocate (часто) vs no‑write‑allocate. Write‑back уменьшает трафик в память, но сложнее при когерентности.
- Когерентность: протоколы MESI/ MOESI/ MSI для многопроцессорных систем.
- Замещение: идеальный LRU редко реализуется — используются LRU, pseudo‑LRU (PLRU), CLOCK, random; у повышенной ассоциативности меньше конфликтных промахов.
- Схема включения: inclusive vs exclusive vs non‑inclusive влияет на копирование линий между уровнями.
3) Типы промахов и причины
- Compulsory (cold) — первая загрузка линии.
- Capacity — рабочее множество больше объёма кэша.
- Conflict — конфликтные попадания из‑за низкой ассоциативности или плохих адресных шаблонов.
4) Среднее время доступа (AMAT)
- Обычная модель: $\mathrm{AMAT}=T_{L1}+M{R}_{L1}\cdot T_{missL1}$, где $T_{missL1}=T_{L2}+M{R}_{L2}\cdot T_{missL2}$ и т.д. Эта формула показывает экспоненциальный эффект промахов на производительность.
5) Влияние на локальность данных
- Пространственная локальность: кэш оперирует блоками (typical line size $64\mathrm{B}$), последовательный доступ эффективен. Если шаг доступа (stride) превышает размер линии, теряется пространственная локальность.
- Временная локальность: повторные обращения к тем же адресам до вытеснения — выигрывают хорошие повторные обращения.
- TLB и страничность: большие страницы (hugepages) могут уменьшить TLB‑промахи и косвенно улучшить кэш‑эффективность.
- Мультипроцессор: false sharing — разные потоки модифицируют байты одной кэш‑линии → частые межъядерные инвалидации и ухудшение производительности.
6) Практические правила оптимизации
- Выравнивание и упаковывание данных по линиям.
- Блочная (tiled) реализация для матриц: выбрать блок размер $B$ так, чтобы блоки помещались в L1: например для double (8 B) и трёх блоков (A,B,C) требование $3B^2\cdot 8<\text{L1\_size}$ => $B<\sqrt{\frac{\text{L1\_size}}{24}}$.
- Предвыборка (hardware/software prefetch) для регулярных проходов.
- Уменьшать stride: доступ по строкам в row‑major, перестроение данных или транспонирование при необходимости.
7) Примеры программ/шаблонов
- Получат существенный выигрыш:
- Плотная линейная алгебра (GEMM) с блочной реализацией — отлично использует кэш.
- Стационарные stencil/конволюции с локальным окном.
- Последовательные стримы (счётчики, суммирование) при хорошем предfetch.
- Пострадают (существенная потеря производительности):
- Ход по связанным спискам с случайными указателями (pointer chasing) — плохая пространственная и временная локальность.
- Наивный транспонирующий код для больших матриц (много промахов по кэшу).
- Проходы по большим массивам с большим stride (например, шаг равен размеру строки таблицы) — один элемент на линию.
- SpMV (разреженные матрицы) без реорганизации данных/перестановки строк‑столбцов.
- Многопоточные программы с false sharing (множественные переменные в одной линии).
8) Заключение (быстрый чек‑лист)
- Оцените рабочее множество vs ёмкость кэша.
- Минимизируйте stride > линия.
- Используйте блокирование, предвыборку, выравнивание и уменьшайте false sharing.
- Меряйте: profile/тепловые карты промахов кэша (perf, VTune) и оптимизируйте на реальные паттерны доступа.
Если нужно, могу привести короткие примеры кода (обертки для блочной матрицы или демонстрация false sharing) или оценить оптимальный блок $B$ для конкретной L1.