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

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

Кеш

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

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

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

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

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

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

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

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

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

Попадание (cache hit) — однократный доступ к закешированному элементу

Промах (cache miss) — однократный доступ к незакешированному элементу

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

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

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

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

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

Принцип: каждая строка кеширует одну из нескольких фиксированных областей памяти:

Pic_5.png

Размер тега зависит от количества областей, кешируемых одной и той же строкой. В примере таких области 4 (количество линий, исходящих из каждой строки), значит, тег займёт всего 2 бита.

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

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

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

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

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

Pic_4.png

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

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

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

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

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

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

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

Pic_6.png

В таком кеше

Кеш на запись

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

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

Когерентность кеша — соответствие данных, находящихся в кеше, данным в памяти

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

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

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

MARS

Примеры:

  1. Гладкое чтение: 
       1 .eqv    START   0x10010000
   2 .eqv    SZ      512
   3 .text
   4         li      $t9 0
   5 loop:   lw      $t0 START($t9)
   6         addiu   $t9 $t9 4
   7         blt     $t9 SZ loop
  2. Чтение вразбивку (с двойным вытеснением): 
       1 .eqv    START   0x10010000
   2 .eqv    SZ      512
   3 .eqv    HSZ     256
   4 # Direct mapping burns out
   5 # Associative captures
   6 .text
   7         li      $t9 0
   8         li      $t8 HSZ
   9 loop:   lw      $t0 START($t9)
  10         lw      $t1 START($t8)
  11         addiu   $t9 $t9 4
  12         addiu   $t8 $t8 4
  13         blt     $t9 HSZ loop
  3. Чтение с шагом (поэкспериментировать с размером шага): 
       1 .eqv    START   0x10010000
   2 .eqv    SZ      256
   3 .eqv    GAP     3               # Попробуйте 5, 11
   4 .text
   5         li      $t8 0
   6         li      $t7 GAP
   7         sll     $t7 $t7 2
   8 loopg:  sll     $t9 $t8 2
   9 loop:   lw      $t0 START($t9)
  10         addu    $t9 $t9 $t7
  11         blt     $t9 SZ loop
  12         addiu   $t8 $t8 1
  13         blt     $t8 GAP loopg
  4. Чтение с небольшим вытеснением: 
       1 .eqv    START   0x10010000
   2 .eqv    SZ      144
   3 .eqv    GAP     4
   4 .text
   5         li      $t8 0
   6         li      $t7 GAP
   7         sll     $t7 $t7 2
   8 loopg:  sll     $t9 $t8 2
   9 loop:   lw      $t0 START($t9)
  10         addu    $t9 $t9 $t7
  11         blt     $t9 SZ loop
  12         addiu   $t8 $t8 1
  13         blt     $t8 GAP loopg

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

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

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

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

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

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

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

Вот как BHT отрабатывает наш третий пример 

   1 .eqv    START   0x10010000
   2 .eqv    SZ      256
   3 .eqv    GAP     11
   4 .text
   5         li      $t8 0
   6         li      $t7 GAP
   7         sll     $t7 $t7 2
   8 loopg:  sll     $t9 $t8 2
   9 loop:   lw      $t0 START($t9)
  10         addu    $t9 $t9 $t7
  11         blt     $t9 SZ loop
  12         addiu   $t8 $t8 1
  13         blt     $t8 GAP loopg

с размером истории 2 и политикой по умолчанию «NOT TAKE» (переход не произойдёт, если статистика отсутствует или 1:1): BHT2_NOT.png

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

Стоит попробовать все варианты (размер 1/2 и политика TAKE/NOT TAKE). Заметим, что стиль написания программы влияет на эффективность предсказания (как?)

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

LecturesCMC/ArchitectureAssembler2019/11_CacheBPT (последним исправлял пользователь FrBrGeorge 2019-05-17 17:56:44)