Увеличение быстродействия с помощью дополнительных устройств

Отступление про внешние устройства.

Прямой доступ к памяти

Базовая статья на Хабре

⇒ Пускай само устройство научится есть из тарелчитать из оперативной памяти и записывать в неё

Прямой доступ к памяти

Возможные проблемы:

🛞 Отступление про шины 🛞

На Википедии

Кеш

Некоторые частые и медленные операции можно убыстрить за счёт аппаратного сбора и хранения дополнительной информации. Например, самые частые обращения в медленную память можно кешировать в быстрой памяти, а адрес следующей инструкции в условном переходе предсказывать (это также актуально при упреждающих вычислениях).

Кеширование как идея

Базовая статья: Что такое кэш процессора, и как он работает

Кеш — механизм аккумуляции части данных медленного устройства большого объёма с помощью быстрого устройства малого объёма.

  1. Повышение быстродействия за счёт скорости обмена, т. к. большинство требуемых данных оказываются на быстром устройстве

  2. Повышение эффективности за счёт агрегации (укрупнения единиц обмена), предзагрузки и отложенной выгрузки данных

Пример: дисковый кеш в памяти

  1. Быстродействие памяти на несколько порядков выше быстродействия диска

    • Активным приложениям нужны не все файлы с диска, а только несколько (тысяч?) штук

    • Даже если диск очень быстрый (NVME), он всё равно оптимизирован для последовательного доступа

  2. Работа с кешем в памяти эффективнее работы с диском:
    • Обмен с диском поблочный, с памятью — побайтный
    • Если приложение начало читать из файла, оно скорее всего, будет читать и дальше из него — можно закешировать заранее
    • Если приложение записывает в файл, возможно, оно и дальше туда писать, а если это MMAP-файл, то — в произвольное его место, и, возможно, неоднократно. Если немного подождать с выгрузкой «грязного» кеша, можно много сэкономить

Для повышения быстродействия в кеше должны содержаться как можно более «популярные» данные

Меньший размер и увеличение быстродействия иногда связаны напрямую:

Методика заполнения и очистки кеша

Заполнение кеша

Устаревание данных в кеше

Замечание: кеш эффективен статистически: всегда можно создать алгоритм или наткнуться на класс задач, сильно понижающий актуальность кешируемых данных (например, пересылка огромных объёмов данных, расположенных в памяти в случайном порядке).

Терминология

Кеширование одного байта/ячейки невыгодно: слишком много метаинформации на один элемент кеша: 

| 00 | 10 04 00 00 | a0 78 4f 95 |

Уже тут не нужно 32 битов для адреса, т. к. адрес ячейки всегда кратен 4

Разовьём идею. Пользуясь адресной локальностью, можно эффективно кешировать непрерывные области памяти: 

| 00 | 10 04 00 | a0 78 4f 95 … 34 45|

Тег адреса в кеше — часть адреса, используемая для идентификации кешируемой области

Строка кеша — минимальная кешируемая область данных

Кеш прямого отображения

Принцип:

LecturesCMC/ArchitectureAssembler2019/11_CacheBPT/Pic_5.png

Размер тега зависит от количества областей, кешируемых одной и той же строкой.

Замечание: алгоритм «привязки» областей памяти к той или иной строке кеша может быть любым, но чаще всего используется тот, что в примере: память представляется в виде последовательно расположенных разделов (того же объёма, что и кеш), и тегом является номер раздела. Каждый раздел, в свою очередь, представлен в виде областей, соответствующих строкам кеша.

Как работает:

Согласно принципу адресной локальности такое разбиение наиболее эффективно: подряд идущие данные не вытесняют друг друга из кеша, если помещаются в нем

Прямой кеш имеет очень эффективную аппаратную реализацию, но не справляется с нарушениями принципа адресной локальности

Ассоциативный кеш

Любая строка может кешировать любую область памяти соответствующего размера (с выравниванием адреса).

LecturesCMC/ArchitectureAssembler2019/11_CacheBPT/Pic_4.png

Тег в ассоциативном кеше больше тега в прямом кеше:

Как работает:

Ассоциативный кеш требует аппаратной реализации поиска тега, следовательно, его эффективность линейно падает с увеличением количества строк. Можно воспользоваться тем, что сравнения изначально независимы, и распараллелить поиск, снизим время до логарифма — параллельное сравнение, потом параллельное сравнение результатов и т. д. — но тогда линейно возрастёт количество ключей, а следовательно, и энергопотребление.

С другой стороны, ассоциативный кеш устойчив к нарушению принципа адресной локальности, а алгоритм вытеснения из кеша позволяет повысить эффективность и за счёт локальности временной.

Множественно-ассоциативный кеш

В современных многозадачных ОС с разделением времени принципы локальности несколько видоизменились

Таким образом, востребована архитектура кеша

Естественное решение: разбить монолитный кеш прямого доступа на несколько «банков» (в соответствии с количеством ожидаемых очагов локальности), а банки объединить ассоциативно

LecturesCMC/ArchitectureAssembler2019/11_CacheBPT/Pic_6.png

В таком кеше

Мы с Википедией считаем, что множественно-ассоциативный кэш — это ассоциативно объединённые банки прямого доступа. Создатели RARS, похоже, сделали наоборот: при настройках Set size = 2 журнал «Data Cache Simulation» выглядит, как если бы сначала на основании тега выбирался банк («block range») из двух строк, а потом в банке производился ассоциативный поиск.

Кеш на запись

Всё это время разговор шёл о чтении из памяти

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

Стратегии кешировния с учётом записи:

  1. Запись не кешируется (сквозная запись, «wtite through»)
    • если данные есть в кеше, их надо обновить
    • если данных нет в кеше
      • кеш изменяется, как если бы происходило чтение (заполнение по записи)
        • заполнение по записи требует усложнения архитектуры, и не всегда эффективно
      • ⇒ (вариант) кеш не изменяется

    • Смысл: чтения этих данных могло ещё не производиться, но принцип локальности говорит, что они достаточно «горячие» (могут потребоваться)

  2. Запись кешируется (write back), т. е. вычисления продолжаются непосредственно после записи данных в кеш, без ожидания актуальной записи в память
    • Для грязных строк нужно хранить дополнительный признак: «dirty» — строка содержит акутальные данные, не синхронизованные с памятью
      • Чем дольше грязная строка закеширована, тем больше вероятность, что в неё ещё раз запишут ⇒ эффективность
      • С другой стороны, чем больше грязных кешей, тем дороже их потеря (сброс питания, например) и тяжелее операция полной выгрузки
    • Все операции с оперативной памятью (в частности, DMA) должны либо проходить через кеш (это неэффективно), либо отслеживаться кеш-контроллером
    • ⇒ возникает дополнительный признак: «недостоверная» строка (invalid), означающий, что данные в строке неактуальны (например, память была обновлена по DMA)
    • доступ на чтение в обход кеша также надо отслеживать и задерживать до синхронизации соответствующих грязных кешей

Всё это начинает крепко подгорать в многоядерных системах, которые имеют обыкновение

(см. план лекции по многоядаерным системам)

<!> В многопоточных системах (multi-HART) всё несколько проще, не ненамного.

Замечания и примеры

RARS

Примеры:

  1. Гладкое чтение: 
       1 .data
   2 start:  .space 1024
   3 end:
   4 .text
   5         la      s1 start
   6         la      s2 end
   7 loop:   lw      t0 (s1)
   8         addi    s1 s1 4
   9         blt     s1 s2 loop
    • Оба топологии­— прямое отображение и ассоциатвная — одинаково эффективны
  2. Чтение вразбивку (с вытеснением): 
       1 .data
   2 start:  .space 512
   3 middle: .space 512
   4 end:
   5 .text
   6         la      s1 start
   7         la      s3 middle
   8         la      s2 end
   9 loop:   lw      t0 (s1)
  10         lw      t1 (s3)
  11         addi    s1 s1 4
  12         addi    s3 s3 4
  13         blt     s3 s2 loop
    • Кеш прямого отображения страдает от вытеснения (нарушается принцип локальности + коллизия тегов)
    • Ассоциативный кеш эффективен
    • Поскольку «горячих» зон всего две, эффективен также множественно-ассоциативный кеш на два банка (а вот было бы этих зон больше, чем банков — выгорел бы)
  3. Чтение с шагом 
       1 .data
   2 .eqv    GAP     12
   3 start:  .space  1024
   4 end:
   5 .text
   6         la      s2 end
   7         li      s3 GAP
   8         li      s4 0
   9 loop:   la      s1 start
  10         add     s1 s1 s4
  11 loopi:  lw      t0 (s1)
  12         add     s1 s1 s3
  13         blt     s1 s2 loopi
  14         addi    s4 s4 4
  15         blt     s4 s3 loop
    • Поэкспериментировать с размером шага: 8, 16, 20?
  4. Чтение с небольшим вытеснением:
    • Поэкспериментировать с объёмом кешируемой памяти в том же примере: полтора размера кеша, два, полностью помещается в кеш

Предсказание перехода

Немного про конвейер

  1. Instruction Fetch — выборка инструкции из памяти

  2. Instruction Decode — интерпретация инструкции

  3. Execute — выполнение операции

  4. Memory access — доступ к памяти

  5. Write back — запись в регистровый блок (обновление регистров)

одну ягодку беру…

Условные переходы отрицательно влияют на эффективность выполнения программы: невозможно точно сказать, какую инструкцию следующей выбирать из памяти — следующую или по адресу перехода

Можно попробовать пособирать статистику: в каких случаях условный переход был, а в каких — не было

Для этого нужно предусмотреть специальную таблицу, в которой хранятся адреса инструкций (последних? наиболее популярных? см. политики кеширования) условных переходов и статистика по их использованию.

При выполнении такой инструкции процессор будет (в терминах RISC-V) заранее предсказывать адрес для стадии I, а в случае ошибочного предсказания оперативно заменять уже считанную инструкцию на «пузырёк»-nop (трюк со слотом задержки мы сейчас не рассматриваем).

RARS

В RARS реализована простейшая BHT (Branch History Table), собирающая статистику за один или два предыдущих вызова конкретного перехода. Даже в случае одного бита предсказания это должно повысить эффективность циклов (в которых множество переходов по одной ветке завершается единственным переходом по другой).

В случае двух битов предсказания можно ещё немного повысить эффективность классического цикла. Допустим, после серии переходов (цикл продолжался) произошёл не-переход (цикл закончился). Логично ожидать, что когда выполнение подойдёт к этому переходу в следующий раз, переход снова произойдёт (начнётся новый цикл), и однократной ошибки в предсказании недостаточно, чтобы «переменить мнение».

Вариант «2/NOT TAKE»: LecturesCMC/ArchitectureAssembler2022/10_CacheBPT/BHT2_NOT.png

Вопрос: каков метод попадания инструкции перехода в BHT RARS? ;)

Заметим, что стиль написания программы влияет на эффективность предсказания (как?)

Более глубокая статистика (например, 3), позволяет нивелировать эту зависимость эффективности от стиля, но вычислительно дороже.

TODO пример выбивания адреса из небольшой BHT (в RARS минимум 8 мест, нужна сложная программа ☹)

Д/З

  1. EJudge: VarCache 'Разные кеши'

    Написать подпрограмму acache, которая вводит два числа: A (некоторый адрес в памяти), и T — тип эксплуатации кеша. Затем программа читает произвольные адреса в диапазоне A … A + 1024 (разумеется, не все) таким образом, чтобы:

    • При T < 0 самым эффективным алгоритмом кеширования оказался бы кеш прямого доступа (Direct Mapping) со стандартными настройками (LRU / 1 / 8 / 4 / 128)

    • При T > 0 самым эффективным алгоритмом кеширования оказался бы ассоциативный кеш (Fully Associative) с теми же настройками

    • При T == 0 самым эффективным алгоритмом кеширования оказался бы множественно-ассоциативный кеш (N-way Set Associative) с теми же настройками и количеством ассоциативных элементов в банке (Set size) 2

    К программе будет приписан такой footer: VarCacheFooter.asm, а его вывод проверен программой моделирования кеша. Для проверки из RARS GUI вместо 0 в тесте можно использовать 268468224 (это $gp)

    Input: 

    0
1
    Output: 

    <ассоциативный кеш эффективнее>

<!> Бонус. Написать программу, которая делает предсказание переходов (с конкретной настройкой и глубиной истории 2) анти-эффективной, т. е. существенно ниже 50%.

LecturesCMC/ArchitectureAssembler2024/11_CacheBPT (последним исправлял пользователь FrBrGeorge 2024-07-26 14:47:40)