Кратко о внутренней структуре и практиках оптимизации кэша.
1) Уровни кэша и их свойства
- Современные CPU имеют иерархию: L1 → L2 → L3 (возможны L0 или L4). Типичные размеры/латентности: L1 — около $32\text{KB}$ на ядро (очень быстро), L2 — около $256-512\text{KB}$ на ядро, L3 — несколько мегабайт общей памяти ($8\text{MB}-32\text{MB}$), задержки растут по уровням.
- L1 обычно разделён на инструкционный и данных (I/D). L3 часто общий для нескольких ядер.
2) Линии кэша, разбиение адреса
- Кэш оперирует линиями (cache lines), типичный размер линии $64\text{B}$.
- Адрес разбивается на три части: tag | index | offset.
- offset bits = ${\log }_2(\text{line size})$ (например для $64\text{B}$ это ${\log }_2(64)=6$ бит),
- число наборов (sets) = $\frac{\text{cache size}}{\text{line size}\times \text{associativity}}$,
- index bits = ${\log }_2(\#\text{sets})$; оставшиеся старшие биты — tag.
3) Ассоциативность и замещение
- Типы: direct-mapped ( $1$-way), $n$-way set-associative (например $4$-way, $8$-way), fully associative. Более высокая ассоциативность уменьшает конфликты, но усложняет логику.
- Политики замещения: LRU или аппроксимации (pseudo-LRU), random и пр.
- Политики записи: write-back (часто) vs write-through; write-allocate vs no-write-allocate.
- Инклюзивность: кэши могут быть inclusive, exclusive или non-inclusive — это влияет на поведение при вытеснении.
4) Причины кэш-промахов
- Compulsory (cold) miss — первая загрузка линии.
- Capacity miss — рабочая область превышает объём кэша (не помещается).
- Conflict miss — несколько адресов конкурируют за один набор из-за ассоциативности/индексации.
- Coherence/False-sharing — разные ядра пишут в разные данные на одной линии; приводит к лишним переотправкам/инвалидациям.
- Другие: большие страйды (шаг доступа > размер линии), pointer-chasing (слабо предсказуемые переходы), невыверенная выравнивание структуры.
5) Практические методы оптимизации (практические и легко применять)
- Повышайте пространственную локальность:
- Используйте последовательный (строчно-линейный) доступ по массивам, избегайте больших шагов (stride).
- Отдавайте предпочтение contiguously allocated arrays перед распределёнными звеньями списков.
- Повышайте временную локальность:
- Повторно используйте недавно доступные данные; уменьшайте рабочее множество, чтобы оно помещалось в L1/L2.
- Кэшируйте часто используемые значения в локальные массивы/память стека.
- Структура данных:
- Если обращаетесь к одному полю структуры часто и к другим редко — используйте SoA (Structure of Arrays) вместо AoS (Array of Structures).
- Выравнивайте и паддите объекты до размера линии, чтобы избежать false sharing: выравнивание и паддинг к $64\text{B}$.
- Блочное (tiling) и перестановки циклов:
- Для матричных операций и свёрток используйте блочное разбиение так, чтобы блок данных помещался в L1 или L2. Практическое правило: выбирайте блок так, чтобы суммарный объём активных массивов < размер целевого кэша (учтите ассоциативность и доп. буферы).
- Применяйте loop interchange, fusion, unrolling по необходимости, чтобы сделать доступы более последовательными.
- Уменьшайте конфликтные промахи:
- Меняйте размеры буферов/смещения/выравнивание, если наблюдаются регулярные конфликты (иногда простое смещение массива на несколько байт решает).
- Избегайте доступа, чей адрес всегда одно и то же индексное поле (период равный числу наборов).
- Многопоточность и NUMA:
- Пиннинг потоков к ядрам и локальные (first-touch) аллокации для правильного распределения на NUMA-узлах.
- Избегайте false sharing, разбивая часто модифицируемые переменные по разным линиям.
- Префетчинг:
- Используйте аппаратный префетчер через последовательный доступ; при необходимости вставляйте software prefetch (\_\_builtin_prefetch или intrinsics) для скрытия задержек при предсказуемых больших переходах. Не злоупотребляйте префетчингом.
- Компилятор и код:
- Используйте restrict/плоские указатели, профиль оптимизации компилятора, векторизацию, оптимизируйте горячие функции.
- Минимизируйте ветвления и тяжёлые системные вызовы в горячих путях.
- Проверка и измерение:
- Профайлируйте: счётчики производительности (perf, VTune) показывают промахи по уровням и причины (TLB/LLC misses). Оптимизируйте по результатам, не по предположениям.
Короткая проверочная памятка:
- Последовательный доступ > случайный; ступень доступа < $\text{line size}$ для эффективного использования spatial locality.
- Рабочий набор должен помещаться в целевой кэш (L1/L2) при возможности.
- Выравнивание и паддинг по $64\text{B}$ убирает false sharing.
- Блокирование/tiling и SoA часто дают большой выигрыш в численных алгоритмах.
Если нужно — могу привести конкретные примеры трансформаций циклов или шаблоны блочного разбиения для вашей задачи.