= Кэш-память.
_Кэш-память (Как устроена? Почему кэш-промахи не случаются часто?, инклюзивность/эксклюзивность, политики замещения, виды ассоциативности, протоколы когерентности)._

В современном мире скорость доступа к памяти значительно медленее скорости работы процессора. Решением проблемы стал концепт кэш-памяти -- добавляем какое-то количество статической памяти рядом с процессором, в которой хранитья копия каких-то данных из оперативной памяти. Менеджмент этой памяти ложиться на ОС, программист не имеет интерфейса для прямого взаимодействия с ней (проверить закэшированны какие-то данные или нет).

Доступ процессора к оперативной памяти происходит через кэш, а не напрямую через шину. В момент доступа происходит проверка на наличее необходимых данных в кэше, если данных нет в кэше то происходит _cache miss_.

#import "/commons.typ": imagebox
#grid(columns: (auto, 150pt), column-gutter: 30pt, [
    кэш делиться на несколько уровней:
    + Самый маленький, порядка 32KiB, вребя обращения \~4 такта. Чаще всего разделяется на 2 части -- отдельно для данных и для инструкций. 
    + Размер \~500KiB, время обращения \~20 тактов
    + Размер \~10MiB, время доступа \~40 тактов.
    Как правило кэш 1 и 2 уровней собственные для каждого вдра процессора, кэш 3 уровня общий для всех ядер.
  ], [
    #imagebox("l3_cache.png", height: 90pt, label: [Иллюстрация организация доступа процессора к оперативной памяти.])
])

== Чтение из кэш памяти
#columns(2)[
  === Look-aside
  При чтении оперативной памяти запрос одновременно отправляеться так же в кэш память, если данные есть в кэше, то быстро отвечаем на запрос, игнорируя данные из оперативной памяти.
  
  #imagebox("look_asight.png")
  *Плюсы:*
  - Быстрый доступ к незакэшированным данным -- не тратится время на проверку всего кэша (время сравнимо с временем доступа к оперативной памяти.
  *Минусы:*
  - Шина доступа к оперативной памяти забивается ненужными данными.
  - кэш и оперативная память подключены через одну шину (достаточно длинную, из-за чего она не может работать на слишком большой частоте).
  #colbreak()
  
  === Look-throught
  Сначала ищем данные только в кэше, если не нашли их, то только тогда отправляем запрос к оперативной памяти.

  #imagebox("look-thrught.png")
  *Плюсы:*
  - Шина не забита ненужными данными.
  - Есть возможность использования разных шин для обмена даннами между процессором и кэшем, кэшем и оперативной памятью (первая короткая, может работать на большей частоте).
  *Минусы:*
  - Время ответа на запрос получения данных может быть до двух раз больше.
]
#pagebreak()

== Запись в кэш память
#columns(2)[
  === Write-throught
  Одновременно отправляем два паралельных запроса на запись и в кэш, и в оперативную память.

  *Плюсы:*
  - Легко реализовать в железе.
  *Минусы:*
  - Постоянное перезаписывание данных при кэшировании, что забивает шину.
  #colbreak()

  === Write-back
  Сначала данные записываются в кэш, потом при необходимости в оперативную. Производительность данного подхода завсист от реализации конкретного контроллера, реализованного хардварно.
  
  *Плюсы:*
  - Нет лишних запросов к опреативной памяти.
  *Минусы:*  
  - Сложнее реализовать, контроллер занимает какое-то место.
]

== Способы размещения данных на уровнях кэша
#columns(2)[
  === Inclusive cache
  В кэше более высокого уровня _храниться копия данных_ из кэша более низкого уровня. При доступе данные ищутся в кэше от низкого до более выского уровней, при нахождении на уровне $n$, данные записываются на уровни $\[1, n\)$.

  При освобождении данные просто выкидываються из самого выского уровня, в более низких остаеться копия этих данных.
  #colbreak()

  === Exclusive cache
  Данные _храняться эксклюзивно_ на каждом уровне. При получении данных из уровня $n$, они переносяться на первый, чтение происходит всегда из кэша первого уровня.

  При необходимости освободить место на каком-то уровне, они переносяться на более низкий уровнь.
]

== Политики замещения данных
- *Random replacement* (ARM CPUs). При необъодимости перезаписать данные, перезаписываеться случайный фрагмент кэш-памяти. Очень просто в реализации, не требуеться сложных контроллеров, работает не слишком плохо.
- *LRU, Least Recently Used*. Храним возраст для каждой строчки кэша (при взаимодействии со строкой ее возраст становиться самым маленьким), выкидываются самые "старые".
- *TLRU, Time Aware LRU*. Помимо возраста храним время хранения, если оно больше какой-то константы, то данные выкидываются.
- *LFU, Least Frequently Used*. Данные выкидываются на основе частоты использования.
- *FIFO/LIFO*. Выкидываем на основе порядка добавления.
- Всевозможные комбинации вышеприведенных полиитик.

== Хранение данных кэшей
Помимо данных в кэше необходимо хранить адресс их расположения в опреативной памяти. Адрессация по байтам невыгодна (влишком много места), адрессуются блоки по 64 байта с дополнительным смещением внутри одного блока.
#imagebox("cache_addressing.png", height: 40pt, label: [Хранение блока данных в кэше, _tag_ - адресс блока в оперативной памяти.])

== Политики кэширования
Способы проверить закэшированны какие-то данные.

=== Полная ассоциативность
В любой линии кэш памяти может храниться любая линия оперативной памяти. В таком влучае если в кэш памяти $n$ линий, то проверка наличия линии опреативной памяти с заданным тегом за $O(n)$.

=== Прямая ассоциативность (прямое отображение)
Предполагаеться, что 1 линия оперативной памяти может быть отображена только в одну линию кэш памяти. В таком случае оперативная память разбивается на блоки размера $C$, время проверки -- $O(1)$. 

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

=== Групповая ассоциативность
Синтез первых двух подходов. Вся память делиться на банки (группы), внутри которых реализуется полная ассоциативность.

#columns(3)[
  #imagebox("full_association.png", label: [Полная ассоциативность.])
  #colbreak()
  #imagebox("single_association.png", label: [Прямая ассоциативность.])
  #colbreak()
  #imagebox("group_assosiation.png", label: [Групповая ассоциативность.])
]

== Когерентность кэша
При использовании многовдерных/многопроцессорных система может случиться несоглассованность кэша, в момент когда кэш 1-2 уровней одного из ядер изменился, но изменения не были перенесены в оперативную.

=== Протоколы когеренстности MSI
Каждая кэш линия каждого кэша (т.е. свое состояние на каждое ядро) имеет одно из трех состояний:
- *M (Modified)* --- линия была изменена, но изменение не было перенесено в оперативную память, во время этого состояния можно читать и писать данные. Гарантируется, что изменения будут перенесены в оперативную память, состояние из *M* измениться на *S*. Для конкретного тега оперативной памяти ровно в одном кэше может быть состояние *M*. 
- *S (Shared)* --- кэш линия не изменена и присутсвует еще в хотя бы одном кэше, данные можно свободно читать, для изменения требуется смена состояния на *M*.
- *I (Invalid)* --- кэш линия не присутсвует в конкретном кэше или не валдина (данные не согласованы с другими кэшами). Для чтения необходимо получить данные из оперативной памяти.

=== Протокол когерентности MESI
Новое состояние - *E (Exclusive)* --- данная данные с таким тегом есть только в одном кэше, можно свободно менять. Состояние активируется, в случае когда данные подгружаются из оперативной памяти (переход из *I*) и они не представлены ни в каком другом кэше. Если при подгрузке данные есть в кэш линии с состоянием *E*, то линии в обоих кэшах становяться *S*.

=== Протокол когеренстности MOESI
Новое состояние - *O (Owned)* --- при изменении данные броадкастятся в другие кэши напрямую (в обход оперативной памяти), что бы линии с таким же тегом в состоянии *S* поменяли данные. 

=== Протокол когерентности MESIF
Новое состояние - *F (Forward)* --- линия с таким состоянием может отвечать на запросы о наличии данных с определенным тегом в кэше. Благодаря этому в других кэшах можно перейти из *I* в *S* без доступа к оперативной памяти. Состояние *F* переходит к последнему кэшу, который запрашивал данные с нужным тегом (предыдущий владелец меняет состояние на *S*).

















































