Архитектура компьютера
Кэш-память: Искусство предсказания
Цели урока
- Понимать структуру cache line (tag, data, valid, dirty)
- Знать типы кэша: direct, associative, set-associative
- Понимать политики замещения (LRU, FIFO, Random)
- Знать политики записи (write-through, write-back)
- Понимать когерентность кэша и MESI
Предварительные знания
- Иерархия памяти
- Locality
Кэш - это искусство предсказания. CPU угадывает, какие данные понадобятся, и загружает их заранее. Понимание кэша = понимание производительности.
- Оптимизация data layout для cache
- Избегание false sharing
- Cache-aware алгоритмы
- Профилирование с perf (cache-misses)
Структура кэша
Кэш состоит из **cache lines** - блоков памяти фиксированного размера (обычно 64 байта).
**Адрес разбивается на части:**
**Lookup:** По Index находим строку, сравниваем Tag. Если совпал и Valid=1 → Hit!
Что хранится в поле Tag cache line?
Типы кэша: Direct, Associative, Set-Associative
**Direct Mapped:** Каждый адрес может храниться только в одной строке.
**Fully Associative:** Адрес может храниться в любой строке.
**N-Way Set-Associative:** Компромисс. N строк на каждый Index.
| Тип | Гибкость | Сложность | Использование |
|---|---|---|---|
| Direct (1-way) | Низкая | Простая | Редко |
| 2-way | Средняя | Средняя | Embedded |
| 8-way | Высокая | Сложная | L1, L2 |
| 16-way+ | Очень высокая | Очень сложная | L3 |
В чём преимущество 8-way set-associative над direct mapped?
Политики замещения
Когда кэш полон, какую строку выбросить?
| Политика | Описание | Плюсы/Минусы |
|---|---|---|
| LRU | Least Recently Used - давно не использовалась | Хорошо, но дорого отслеживать |
| FIFO | First In First Out - старейшая | Просто, но не учитывает частоту |
| Random | Случайный выбор | Очень просто, на удивление неплохо |
| LFU | Least Frequently Used | Хорошо для hot data, сложно |
**Random работает:** Для L3 кэша random replacement даёт hit rate только на 1-2% хуже LRU, но проще в реализации.
LRU выбирает для замещения:
Политики записи
Когда CPU записывает данные, куда писать?
**Write-Through:** Запись сразу в кэш И в RAM.
**Write-Back:** Запись только в кэш. В RAM - при вытеснении.
**Write-Allocate vs No-Write-Allocate:**
| Политика | При write miss |
|---|---|
| Write-Allocate | Загрузить в кэш, потом записать |
| No-Write-Allocate | Записать напрямую в RAM (bypass cache) |
**Современные CPU:** Write-Back + Write-Allocate. Это минимизирует трафик к RAM.
Что означает Dirty bit = 1 в cache line?
Когерентность кэша
**Проблема:** Многоядерный CPU. Каждое ядро имеет свой L1/L2. Что если оба изменят одни данные?
**MESI Protocol:** Каждая cache line имеет состояние:
| Состояние | Описание |
|---|---|
| Modified (M) | Изменена, только у меня, RAM устарел |
| Exclusive (E) | Только у меня, но чистая (совпадает с RAM) |
| Shared (S) | Читают несколько ядер, чистая |
| Invalid (I) | Невалидна, нужно загрузить заново |
**False Sharing:** Два ядра пишут в РАЗНЫЕ переменные, но на одной cache line. Постоянный ping-pong между ядрами! Решение: разнести данные в памяти.
Кэш автоматически делает код быстрым
Кэш ускоряет только код с хорошей локальностью. Случайный доступ кэш не помогает.
Cache miss для каждого обращения = 100 нс задержки. Хуже, чем без кэша (добавляется lookup overhead).
Что делает протокол MESI?
Ключевые идеи
- Cache line: Tag + Data (64 байта) + Valid + Dirty
- Set-Associative: баланс между conflict misses и сложностью
- LRU: вытеснять давно не использованное
- Write-Back: писать в RAM только при вытеснении
- MESI: когерентность между ядрами (M/E/S/I)
- False Sharing: убийца многопоточной производительности
Связанные темы
Кэш - ключ к производительности.
- Виртуальная память — TLB - кэш трансляции адресов