edu-csa

# Архитектура компьютера

## Лекция 12-13

### Иерархия памяти. Кеш

Пенской А.В., 2025

---

## Иерархия памяти

Задачи хранения:

1. Исходные данные, необходимые для запуска системы.
1. Рабочие данные, создаваемые и изменяемые в процессе работы системы.

**Проблема**: с ростом скорости памяти растёт её стоимость (производство и размещение).

*Почему она нерешаема?*

</div><div class="col">

Выше — быстрее и дороже.

![*Memory Hierarchy*](/fig/memory-hierarchy.jpg)

`+` Сетевые хранилища.

Ниже — больше и дешевле.

</div></div>

----

### Визуализация примечательных задержек

![](/fig/latency-visualization.png)

----

### Иерархия памяти для разработчика

#### Явная иерархия (Expose Hierarchy)

1. Регистры, SRAM, DRAM, диски доступны как альтернативные хранилища.
1. Посыл: используйте с умом.

</div><div class="col">

![](/fig/memory-cpu-and-hierarchy-expose.png)

</div></div>

Scratchpad-based Memory Scheme (by developer)

#### Скрытая иерархия (Hide Hierarchy)

1. Модель: одна память, одно адресное пространство.
1. Зависит от использования. Определяется прозрачно.
1. Посыл: мы всё сделаем за тебя.

</div><div class="col">

![](/fig/memory-cpu-and-hierarchy-hide.png)

</div></div>

Cache-based Memory Scheme by Hardware (mostly)

----

### Типовая работа с памятью

![](/fig/memory-translations.png)

План: устройство памяти $\longrightarrow$ устройство кешей

---

## Типы доступа к памяти

1. C **произвольным доступом**, Random-Access Memory (RAM). Задержка доступа не зависит от истории запросов.

1. C **последовательным доступом** (жёсткие диски, магнитные ленты, [AWS Tape Gateway](https://aws.amazon.com/storagegateway/vtl/)).
    - Длительная задержка при смене адреса.
    - Часто, высокая скорость последовательной записи/чтения.

1. **Гибридные**: библиотека магнитных лент, векторные операции.

Наша область: от процессора до основной памяти.

----

## Память с произвольным доступом (RAM). Принцип работы

![Memory array](/fig/memory-array.png)

Массив ячеек памяти $4\times3$ <br/> (4 слова по 3 бита)

</div><div class="col">

- `Address` — адрес ячейки памяти шириной 2 бита.
- `Decoder` — [дешифратор](https://ru.wikipedia.org/wiki/Дешифратор), активирует линию (1 из 4 шт.).
- `wordline_i` — линия, активирующая ячейки требуемого машинного слова.
- `bitline_i` — линия, на которую выставляется/читается значение бита определённой позиции.
- `stored_bit` — ячейка памяти.

</div></div>

----

### Технология реализации битовых ячеек

Существует много вариантов реализации ячейки памяти. Типовые:

| Memory Type | Transistors*Bit | Latency | Capacity | Cost/GB |
|---------------------|-----------------|-----------|------------------|-----------------|
| Flip-flop (Триггер) | $\sim 20$ | 20 ps | $\sim 1-5kB$ | a lot of $ |
| ROM | $\leq 1$ | - | - | - |
| SRAM | 6 | $1-10 ns$ | $\sim 10kB-10MB$ | $\sim \\$ 1000$ |
| DRAM | $\frac{1}{2}-1$ | 80 ns | $\sim 10GB$ | $\sim \\$ 10$ |

Notes: <https://computationstructures.org/lectures/caches/caches.html>

----

### Read Only Memory (ROM) Cell

Память только для чтения.

Способы реализации:

- Физическое [не]размещение транзисторов (на производстве).
- Пережигание перемычек при однократном программировании (см. [PROM](https://ru.wikipedia.org/wiki/PROM)).

</div><div class="col">

![*ROM*](/fig/rom.png)

</div></div>

---

### Static Random Access Memory (SRAM)

Хранение данных при помощи **состояния группы транзисторов** (4 — инверторы, 2 — доступ):

1. быстрый доступ на чтение и запись;
1. значение хранится до отключения питания;
1. требует довольно большое количество транзисторов (низкая плотность ячеек).

Далее — примеры чтения и записи.

</div><div class="col">

![](/fig/memory-sram-cell-1.png)
![](/fig/memory-sram-cell-2.png)

</div></div>

----

#### SRAM Array

![](/fig/memory-sram-array.png)

----

#### SRAM Read

![](/fig/memory-sram-read.png)

----

#### SRAM Write

![](/fig/memory-sram-write.png)

----

#### SRAM Multiport

![](/fig/memory-sram-multi-port.png)

---

### Dynamic Random Access Memory (DRAM)

Динамическая память, состояние хранится **в конденсаторе**.

1. состояние конденсатора можно считать лишь раз;
1. состояние конденсатора утекает;
1. требуется контроллер памяти для *регенерации*;
    - увеличивает длительность доступа;
    - блокирует доступ к памяти во время регенерации.
1. один транзистор и конденсатор на ячейку памяти.

</div><div class="col">

![](/fig/dram-a.png) 
![](/fig/dram-b.png)

</div></div>

----

#### DRAM Read/Write

![](/fig/memory-dram-read-write.png)

---

## Кеш. Назначение. Предпосылки

<dl>
  <dt> Кеш </dt>
  <dd>  промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. </dd>
</dl>
 
--------------------

1. Малый объём быстрой памяти для текущих данных.
1. Целесообразен, если доступ к памяти неравномерный.
1. (реже) Смена интерфейса: процессор — кеш — память.

</div><div class="col">

Временная и пространственная локальность данных

![](/fig/memory-access-patterns.png)

</div></div>

----

### Кеши в компьютерных системах

Кеши применяются на всех уровнях компьютерных систем, но мы обсуждаем процессоры.

Противоречие:

1. Много данных, низкая локальность. Нужен очень большой кеш.
1. Мало данных, высокая локальность. Нужен очень маленький кеш.

</div><div class="col">

![](/fig/caches-everywhere-meme.png)
![](/fig/caches-everywhere.png)

</div></div>

---

### Кеш. Функционирование

1. Кеш состоит из набора кеш-линий (блоков кеша, записей).
1. Кеш-линия ассоциирована с элементом в медленной памяти.
1. Кеш-линия имеет идентификатор (тег), определяющий соответствие.
1. Доступ к памяти реализуется прозрачно для программиста.
1. Память может быть изменена вне зависимости от кеша: DMA, другое ядро.

</div><div class="col">

![](/fig/cache-basic.png)
![](/fig/memory-direct-vs-via-cache.png)

</div></div>

----

#### Кеш. Чтение данных

1. **Тег найден** $\rightarrow$ **кеш-попадание (cache hit)**. Данные читаются в процессор из кеш-линии.
1. **Тег не найден** $\rightarrow$ **кеш-промах (cache miss)**. Запрашиваем данные из памяти или следующего кеша. Выбираем линию для замещения:
    - Есть пустая — подходит.
    - Все заняты — принимаем решение о вытеснении линии.
    - Длительность получения данных — произвольна, т.к.:
        - возможен многоуровневый кеш;
        - возможна блокировка памяти (восстановление памяти, DMA).

**Уровень попадания (hit rate)** — основная характеристика эффективности кеша.

</div><div class="col">

![](/fig/cache-hit-and-cache-size.png)

</div></div>

----

#### Кеш. Запись данных (кеш попадание)

1. **Немедленная запись** (write-through). Изменение вызывает синхронное обновление памяти. Иногда медленнее, чем без кеша.
2. **Отложенная запись** (write-back). Обновление памяти при вытеснении кеш-линии, периодически, или по запросу.
    - Требует хранения признака модификации ("грязный").
    - Группировка изменений, сокрытие промежуточных состояний.
    - Возможно неконсистентное состояние кеша и памяти. Для процессора — невидимое, для других устройств (DMA) — требуется принудительная запись.
3. **Гибридные варианты**. Пример: немедленная запись с буферизацией.

----

#### Кеш. Запись данных (кеш промах)

1. **Запись с размещением** (Write Allocate, Fetch on Write).
    - Данные загружаются в кеш, после в них вносится исправление.
    - Два обращения: запись вытесняемого и чтение необходимого.
    - Поведение аналогично промаху по чтению.

1. **Запись без размещения** (No-Write Allocate, Write Around).
    - Запись производится напрямую в память или через буфер (группировка изменений).

----

#### Кеш-промахи. Разная информация и операции

1. **Чтение данных**. <br/> Средняя задержка. Может компенсироваться параллелизмом уровня инструкций (см. суперскаляр).
1. **Запись данных**. <br/> Минимальная задержка. Запись может быть отложена.
1. **Чтение инструкций** <br/> Большая задержка. Процессор простаивает в ожидании инструкции.

</div><div class="col">

![](/fig/cache-miss-meme.jpg)

</div></div>

----

## HyperThreading

For each processor core that is physically present, the operating system addresses two virtual (logical) cores and shares the workload between them when possible. The main function of hyper-threading is to increase the number of independent instructions in the pipeline.

![HyperThreading](/fig/hyper-threading.png)

---

## Кеш. Внутреннее устройство

Кеш — это память и логика. Логика реализует:

1. Поиск кеш-линии по тегу (компараторы).
1. Вытеснение, replacement (определение ненужной кеш-линии).
1. Предзагрузка (prefetch) данных и инструкций.
1. Взаимодействие с памятью (группировка операций и т.п.).
1. Синхронизации кешей разных уровней.

Больше данных $\longrightarrow$ больше логики.

Масштабирование по времени или по площади:

- 2 линии, 2 компаратора $\longrightarrow$ 1 такт,
- 2 линии, 1 компаратор $\longrightarrow$ 2 такта.

---

### Кеш. Ассоциативность

Политика размещения данных памяти в кеше для оптимизации поиска.

Аналогия: поиск в `array` $O(n)$, `btree` $O(log(n))$, `hashmap` $\Theta(1)-O(n)$.

```text
address, 32 bit
011001010101101001101001010101010
^ high                      low ^
|                               |
|                               |
+-- 2 Gb step     1 byte step --+
```

</div><div class="col">

![*Отображение кеша на память*](/fig/cache-basic.png)

</div></div>

Тег — идентификатор области памяти, сохранённой в кеш-линии:

1. **Полный** адрес — много памяти, много больших компараторов.
1. **Младшие биты**. Не нужны, если работать блоками, а не байтами.
1. **Средние биты**. Циклически повторяются в адресах памяти.
    - Принцип временной и пространственной локальности.
1. **Старшие биты**. Относительно уникальны (если используются).

----

#### Полностью ассоциативный кеш <br/> (Fully Associative Cache)

Любая строка памяти может быть отображена в любую кеш-линию.

1. Лучшая эффективность.
1. Очень много логики:
    - компараторы,
    - вытеснение.

![](/fig/cache-full-assoc.jpg)

</div><div class="col">

![](/fig/cache-fully-associative.png)

</div></div>

----

#### Кеш с прямым отображением (Direct Mapping)

Каждая ячейка может быть отображена только в 1 кеш-линию. <br/> (одна кеш-линия — много ячеек)

Средняя часть — номер линии.

1. Меньше памяти для tags.
1. Один меньший компаратор.
1. Нет вытеснения (однозначно).
1. Коллизия и техническая выгрузка.

![](/fig/cache-direct-assoc.png)

</div><div class="col">

![](/fig/cache-direct-mapped.png)

</div></div>

----

#### Множественно-ассоциативный кеш <br/> (N-Way Set Associative Cache)

Кеш с прямым отображением (1 банк), воспроизведённый N раз.

1. Больше ассоциативность, ниже скорость, выше эффективность.
1. Выбор банка осуществляется на основе алгоритма вытеснения.

![](/fig/cache-missrate.png)

</div><div class="col">

![](/fig/cache-set-associative.png)

</div></div>

---

### Кеш. Вытеснение и замещение

1. Ключевой механизм: эвристика выбора более не требующейся кеш-линии среди доступных.

1. В процессорах применяются достаточно простые алгоритмы (скорость и площадь):

- Least Recently Used (LRU)
    - Pseudo-LRU

1. Возможные модификации:

- Victim Cache — сперва отделить, потом вытеснить
    - Запрет кеширования

</div><div class="col">

#### Least Recently Used

Маркировка записей временем последнего доступа

Пример:  `A B C _D_ E _D_ F`

| | | | |
|:--------:|:--------:|:--------:|:--------:|
| **A(0)** | | | |
| A(0) | **B(1)** | | |
| A(0) | B(1) | **C(2)** | |
| A(0) | B(1) | C(2) | **D(3)** |
| | | | |
| **E(4)** | B(1) | C(2) | D(3) |
| E(4) | B(1) | C(2) | **D(5)** |
| E(4) | **F(6)** | C(2) | D(5) |
| | | | |

</div></div>

----

#### Pseudo-LRU

1. Бинарное дерево:
    - вершины хранят путь: `left(0) / right(1)`;
    - листья: кеш-линии.
1. Поиск записи для вставки или вытеснения:
    - спуск по дереву согласно значениям в вершинах;
    - инверсия всех пройдённых вершин.
1. Кеш попадание — инверсия пути от корня до листа.
1. Значительно "легче" LRU.

</div><div class="col">

![](/fig/plru-example.png)

`A B C _D_ E _D_ F`

</div></div>

---

### Многоуровневый кеш

![](/fig/memory-cpu-and-hierarchy-hide.png)

Свойства кеша определяются:

- технологией ячеек памяти,
- устройством кеша (размер, ассоциативность, и т.д.).

</div><div class="col">

Задачи кеша:

1. Повышение скорости доступа.
1. Синхронизация проц. ядер.
1. Оптимизация интерфейсов.

</div></div>

Способы организации многоуровневых кешей:

1. Разделённый/унифицированный
1. Включающие/исключающие
1. Частные/общие

----

#### Разделённый (Banked)<br/>/Унифицированный (Unified)

Кеш-память может быть реализована одним или несколькими банками памяти. Иметь один канал доступа, или несколько.

Принцип разделения:

- По типу данных:
    - Кеш данных.
    - Кеш инструкций.
    - Trace cache (микрокод).
- По процессорному ядру.

![](/fig/cache-l1-unified.png) 
![](/fig/cache-l1-banked.png)

</div><div class="col">

1. Достоинства разделённого кеша:
    - Повысить скорость доступа (больше каналов).
    - Адаптировать устройство кеша под специфику использования.
1. Недостатки разделённого кеша:
    - Усложнение процессора.
    - Конфликты между банками кеш-памяти.

</div></div>

----

#### Включающие (Inclusive)<br/>/Исключающие (Exclusive)

Должен ли кеш одного уровня включать кеш другого уровня?

1. **Инклюзивная** — данные кеш-линий дублируются. Доступ происходит быстрее (выгрузка `L1` не может привести к выгрузке `L2`), но часть памяти "теряется".
2. **Эксклюзивная** — данные не дублируются. Память используется эффективнее.
3. Гибридный вариант <br/> (**Non-Inclusive, Non-Exclusive** — NINE) — гибридные варианты.

</div><div class="col">

![](/fig/cache-inclusive-exclisive.png)

(О когерентности позднее)

</div></div>

----

#### Частный (Private)/Общий (Shared)

Характеризует доступ процессорных ядер к кешу.

1. **Частный** кеш — ядро имеет эксклюзивный доступ к кешу.
    - Скорость доступа ядра.
    - Дублирование и конфликты.
1. **Общий** кеш — несколько ядер имеет доступ к кешу.
    - Меньше кеш промахов.
    - Нет дублирования.
    - Постоянная синхронизация доступа.

</div><div class="col">

![](/fig/cache-hierarch-example.png)

</div></div>

---

#### Уровни кеширования в процессорах

- **L0** (опция) — специальный кеш для: стека, int/float чисел. Обычно доступен за такт.
- **L1** — быстрый, неотъемлемая часть процессора. Обычно разделён (Banked).
- **L2** — обычно часть процессора. От 128 Кбайт до 1-12 Мбайт. Обычно общий (Shared).
- **L3** до 24 Мбайт и более. Синхронизация данных в многоядерных процессорах.
- **L4** (экзотика для серверов и мейнфреймов). Оптимизация интерфейса доступа к памяти.

</div><div class="col">

![](/fig/proc-cache-hierarchy.jpg)

</div></div>

---

### Кеш. Когерентность

Целостность данных в кешах процессора и памяти.

**Проблема**: параллельный доступ к данным (чтение/запись) множеством акторов (процессорные ядра, DMA).

![](/fig/cache-coherency-generic.jpg)

</div><div class="col">

![](/fig/multicore-cache.png)

</div></div>

----

#### Пример состояний кеш-линий (MOESI)

1. **Модифицировано** (**M**odified). `L` — свежие уникальные данные.
    - Модификация возможна без запросов.
    - `L` $\rightarrow$ `Exclusive` (запись в память).
1. **Владелец** (**O**wned). Только одна запись в состоянии.
    - `L` — свежие данные, `C` — возможны, `M` — может устареть.
    - `L` $\rightarrow$ `Modified` ($\forall$ `C` $\rightarrow$ `Invalid`) или $\rightarrow$ `Shared` (запись в память).
1. **Эксклюзивное** (**E**xclusive). `L`, `M` — свежие данные, `C` — нет.
    - `L` $\rightarrow$ `Modified` (запись в кеш) или `L` $\rightarrow$ `Invalid` в любой момент.
1. **Разделяемое** (**S**hared). Содержит свежие данные, могут быть копии.
    - Запись запрещена, требуется `L` $\rightarrow$ Exclusive, $\forall$ `C` $\rightarrow$ `Invalid`.
    - `L` $\rightarrow$ `Invalid` в любой момент.
1. **Не актуальное** (**I**nvalid). Не содержит корректных данных.

(`L` — кеш-линия, `C` — копия(-ии) кеш-линии в другом процессоре, <br/> `M` — запись в памяти)

----

#### Обмен информацией о состоянии кеш-линий

##### Справочник (Directory)

Общий справочник с информацией о разделяемых данных.

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

</div><div class="col">

![](/fig/cache-coherence-directory.jpg)

</div></div>

- Достоинство: масштабирование, количество процессоров может быть велико.
- Недостаток: задержка запроса к справочнику.

----

##### Отслеживание (Snooping)

![](/fig/cache-coherence-snooping.jpg)

</div><div class="col">

Отслеживание операций других процессоров с памятью.

- Кеши отслеживают **адресные линии** на предмет обращений к данным своих кеш-линий.
- Если наблюдается запись — кеш помечает линию как "не актуальную".

</div></div>

- Достоинство: скорость.
- Недостаток: ограниченная масштабируемость.

##### Перехват (Snarfing)

- Кеши отслеживают **адресные линии** и **линии данных** на предмет обращений к данным своих кеш-линий.
- Если наблюдается запись — кеш обновляет кеш-линию.

----

#### CAP-теорема. То же, но в большем масштабе

В распределённых системах нельзя одновременно обеспечить:

![](/fig/cap-theorem.png)

</div><div class="col">

1. **Согласованность** (Consistency) — каждое чтение получает последнюю запись или ошибку.
1. **Доступность** (Availability) — каждый запрос получает ответ (без ошибок), но и без гарантии, что он содержит последнюю запись.
1. **Устойчивость к разбиению** (Partition Tolerance/Brainsplit) — система продолжает работать, несмотря на произвольное количество потерь в сети между узлами.

</div></div>

---

### Кеш. Непрозрачность

1. В теории, кеш-память прозрачна для программиста. Он не должен ожидать неприятностей от неё.
1. На практике:
    - Meltdown.
        - Кеш и недостатки спекулятивных вычислений <br/> $\rightarrow$ утечка по стороннему каналу.
        - Смотрите в докладах по лаб. 1.
    - Кеш и перемножение матриц.
    - Array of Structures (AoS) vs. Structure of Arrays (SoA).

[Экспериментальное определение характеристик кеш-памяти](https://habr.com/ru/post/148839/)

----

#### Перемножение матриц

$c_{ij} = \sum_{r=1}^m a_{ir}b_{rj} \left(i=1, 2, \ldots l ; \\; j=1, 2, \ldots n \right)$

где:

- A ($l\times m$), B ($m \times n$) — исходные матрицы.
- C — результирующая матрица.
- Хранение матриц: `int**` (двумерный массив).

</div><div class="col">

![*Длительность перемножения матриц от их размера*](/fig/matrix-multiplication-diagram.png)

</div></div>

----

##### Наивное перемножение

```c
for (int i = 0; i < size; i++) {
  for (int j = 0; j < size; j++) {
    C[i][j] = 0;
    for (int k = 0; k < size; k++) {
      C[i][j] += A[i][k] * B[k][j];
    }
  }
}
```

##### Транспонированное умножение

```c
B2 = transpose(size, B);
// ...
for (int i = 0; i < size; i++) {
  for (int j = 0; j < size; j++) {
    C[i][j] = 0;
    for (int k = 0; k < size; k++) {
      C[i][j] += A[i][k] * B2[j][k];
    }
  }
}
```

</div><div class="col">

![](/fig/matrix-multiplication-diagram.png)
![](/fig/matrix-transponent.png)

</div></div>

----

##### Результаты эксперимента

![](/fig/matrix-mul-memory-access-pattern.png) 
![](/fig/matrix-mul-time.png)

----

#### Array of Structures (AoS) <br/>vs. Structure of Arrays (SoA)

```C
struct point3D {
    float x;
    float y;
    float z;
};

struct point3D points[N];

float get_point_x(int i) {
    return points[i].x;
}
```

</div><div class="col">

```C
struct pointlist3D {
    float x[N];
    float y[N];
    float z[N];
};

struct pointlist3D points;

float get_point_x(int i) {
    return points.x[i];
}
```

</div></div>

1. Эффективность работы кеша.

1. Поддержка адресации групповых операций с точки зрения ISA.

1. Колоночные базы данных.

---

### Виртуальная память и Кеш

С какими адресами работает кеш, физическими или виртуальными?

----

### Кеш-память с виртуальными адресами

#### Преимущества (ВА)

- **Быстрота доступа**. Доступ к памяти минуя трансляцию адреса.
- **Простота реализации**. Простота кеш памяти. Не требуется трансляция адресов перед проверкой кеш попадания.

</div><div class="col">

#### Недостатки (ВА)

- **Проблемы совместимости процессов**. Требуется различать контексты из-за коллизий виртуальных адресов.
- **Неэффективность при смене контекста**. Смена контекста может потребовать очистку кеша для предотвращения конфликтов данных.

</div></div>

----

### Кеш-память с физическими адресами

#### Преимущества (ФА)

- **Универсальность**. Физические адреса уникальны в рамках системы.
- **Консистентность данных**: Физические адреса упрощают поддержание консистентности кешей и памяти.

</div><div class="col">

#### Недостатки (ФА)

- **Задержки из-за трансляции адресов**: Доступ к данным в кеше по физическому адресу требует предварительной трансляции виртуального адреса.
- **Сложность реализации**: Необходимость поддержки трансляции адресов увеличивает сложность управления кешем.

</div></div>

Возможны смешанные варианты:

- `L1` — виртуальные адреса для минимизации задержек,
- `L2`, `L3` — физические для универсальности и консистентности.

---

### Кеш. Доведём до абсурда, или нет?

#### Типичный маршрут работы приложения

![](/fig/phantom-os-classical-program.png)

----

#### Маршрут работы приложения, если память персистентна

![](/fig/phantom-os-modern-process.png)

----

#### PhantomOS

![](/fig/phantom-os.jpg)

1. Unix: "Всё есть файл" $\longrightarrow$ Фантом: "Всё есть объект".
1. Единое глобальное виртуальное пространство — доступ по ссылке.
1. Snapshots всей системы.
1. [Дмитрий Завалишин — ОС «Фантом» и Java: сборка мусора](https://www.youtube.com/watch?v=DHCrUADYlJc) — с техническими деталями.
1. [Smalltalk. Pharo](https://www.pharo.org): Объектный язык (никакой не "ориентированный"). IDE и OS — одно целое. Файлы не нужны (даже для кода).