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

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

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

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

• Многие устройства (например, жёсткие диски, сетевые карты и т. д.) обмениваются с компьютером большими объёмами данных.

  • Пословное чтение/запись этих данных через MMIO-регистры крайне неэффективно
  • обмен малыми объёмами
  • всю работу делает процессор
• Отображение части памяти устройства на оперативную память само по себе тоже неэффективно
  • либо это то же MMIO, только адреса разные

  • либо кто-то должен отвечать за заполнение этой области и актуальность находящихся там данных — опять процессор?

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

• Не понадобится массовый MMIO (регистры управления удобнее оставить)
• Обмен теперь выглядит так:
  • Записываем адрес в регистр адреса
  • Записываем размер в регистр размера
  • Записываем команду (скажем, чтения) в регистр команд
  • Устройство начинает складывать данные прямо в память в указанное место
  • …складывает
  • …складывает
  • а программа тем временем работает
• Когда устройство всё сложит, возникнет прерывание типа «Окончание операции В/В»

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

• Устройств несколько, а шина данных одна
• Арбитраж (кому первому предоставить доступ к памяти)
• Многоканальность

• Устройство (например, сетевой интерфейс) готово прислать результаты операции чтения, а его забыли спросить (или не успели), потому что много и части
  

  • Bus mastering («захват шины»: устройство само может начать операцию В/В и инициировать прерывание, т. е. реализует часть ПДП контроллера)

• Область обмена такая большая, что непрерывного куска в памяти прост не найти

  • Вместо одной области устройству передаётся список, и оно должно уметь раскладывать данные во все элементы списка

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

На Википедии

• Исторически: пучок проводов к устройствам (название предположительно из немецкого)

• Прерывания и MMIO: контроллер шины памяти

• DMA, быстрые и медленные устройства: шина памяти отдельно, шины устройств отдельно, приоритизация и т. п.
• Bus mastering — управление шиной со стороны устройства (а не процессора)
• …

Кеш

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

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

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

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

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

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

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

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

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

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

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

• Временная локальность: доступ к некоторому ограниченному фрагменту «большой» памяти востребован много раз в течение небольшого промежутка времени (когда выполняется работающий с ним фрагмент программы)

• Адресная локальность: соседние ячейки памяти часто востребованы вместе (например, при работе с массивами)

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

• чтение из памяти: выставление адреса → доступ к ячейке по адресу → чтение данных → запись во внутренний блок
• чтение из регистра: непосредственная запись из регистра (определяется на стадии разбора инструкции) во внутренний блок

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

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

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

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

• Случайные
  • эффективная аппаратная реализация
  • невысокая эффективность кеширования
• Редко используемые (LFU, less frequently used)
  • требуется хранить счётчик использования
  • требуется поиск самого низкого значения счётчика

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

• Давно не используемые (LRU, less recently used)
  • в чистом виде требуется хранить возраст
• Очередь (FIFO)
  • в чистом виде — эффективная аппаратная реализация
  • невысокая эффективность кеширования
• FIFO+LRU

  • самый свежий элемент всегда ставится в начало очереди (или переставляется в начало, если он был в ней)

  • удаляется самый последний элемент (он и есть самый старый)

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

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

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

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

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

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

• 8 битов — счётчик возраста
• 30 битов — адрес
• 32 бита — содержимое ячейки

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

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

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

• 8 битов — счётчик возраста

• 24 бита — тег адреса

• 8192 бита — содержимое ячеек (строка кеша)

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

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

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

Принцип:

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

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

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

• Адрес внутри области в случае прямого отображения для каждой строки кеша задан заранее

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

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

• При обращении к памяти через кеш вычисляются:
  • тег адреса — целая часть деления адреса на размер кеша

  • номер строки — целая часть деления смещения относительно начала раздела на длину строки

• Если тег адреса совпадает с записанным в строку кеша, засчитывается попадание, и данные передаются из кеша
• Если тег адреса не совпадает с записанным в строку кеша, засчитывается промах, и происходит непосредственное обращение к памяти с обязательным заполнением строки

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

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

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

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

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

• он также зависит от числа возможных кешируемых областей, а их столько, сколько строк умещается в памяти
• В примере строк 16, следовательно, размер тега — 4 бита

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

• При обращении к памяти через кеш вычисляется тег — целая часть деления адреса на размер строки
• Если строка с таким тегом содержится в кеше, засчитывается попадание, и данные передаются из кеша
• Если строки с таким тегом в кеше нет, засчитывается промах
  • происходит непосредственное обращение к памяти
  • выбирается строка-кандидат на вытеснение из кеша
  • считанные данные помещаются в строку кеша

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

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

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

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

• Временная локальность либо обеспечена только на один квант работы процесса, либо захватывает данные всех активных процессов систем
• Адресная локальность демонстрирует не один очаг «горячих» данных, а несколько, по количеству активных процессов системы

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

• большего по объёму
• поддерживающего более одного очага локальности

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

В таком кеше

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

Кеш на запись

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

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

• Грязный кеш (dirty cache) — ситуация, когда содержимое кеша более новое, чем содержимое медленного устройство

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

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

• Некогерентное состояние кеша возникают в двух случаях:

  • Наличие нескольких независимо обновляемых кешей на запись одного и того же места в памяти

  • Запись в память мимо кеша, после которой данные в памяти актуальны, а в кеше — нет

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

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

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

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

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

• Иметь отдельный кеш на каждом ядре

• Лезть в память одновременно

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

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

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

• Кеш данных и кеш инструкций удобно разделять:
  • инструкции не кешируются на запись
  • инструкции и данные могут образовывать два очага локальности
  • для инструкций и для данных методы упреждения различны
• Кеш часто делают двухуровневым
  • большой относительно медленный общий кеш L2 (скорее всего, прямого отображения + несколько ассоциативных банков)
  • два маленьких совсем быстрых кеша (отдельно — инструкций L1I, отдельно — данных L1D; скорее всего, ассоциативные)
• В зависимости от архитектуры, L1 может быть подмножеством L2 или дополнением к нему. В последнем случае данные, вытесняемые из L1, помещаются в L2, а данные, закешированные в L1, вытесняются из L2 («остывание» / «разогрев»)

RARS

• Открыть в Rars «Tools → Data Cache Simulator»
• Открыть в Rars «Tools → Memory Reference Visualization»

  • 

• Изучить эффективность работы кешей (2×2=4 варианта)
  • Организация: Direct Mapping (прямое отображение) / Fully Associative (ассоциативный)
  • Вытеснение: LRU (давно не использованная строка) / Random (случайная строка)

Примеры:

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 — запись в регистровый блок (обновление регистров)

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

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

• в архитектурах с конвейером это приводит к появлению в конвейере «пузырька»-nopа прямо на этапе F (мы ещё не вычислили, какую именно, а выбирать вроде бы уже надо, пропускаем ход)

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

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

• Количественную (сколько раз был переход, сколько — не было)

• Количественную с устареванием

• С учётом значений используемых регистров (например, ra, sp и *epc)

• ...

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

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

RARS

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

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

• Сделаем в третьем примере GAP побольше (скажем, 68), чтобы количество внутренних и внешних циклов было примерно одинаково.

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

  • Проверим

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

  • Проверим
• Установим размер истории 2 и политику по умолчанию «TAKE»
  • Проверим

Вариант «2/NOT TAKE»:

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

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

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

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

Д/З

TODO

1. Написать пример шаблона работы с памятью, для которого кеш прямого отображения эффективен, а ассоциативный — нет

   • Спойлер: Читаем некоторый объём памяти несколько раз вразбивку. Количество различных строк памяти, к которым по очереди обращается эта программа, должно быть больше количества строк в кеше — это гарантирует выгорание ассоциативного кеша. Если у некоторых из этих строк тег прямого доступа уникален, они успешно останутся в кеше прямого доступа и останутся актуальными при повторном чтении.

2. Проверить гипотезу о том, что если активно использовать стек и кучу, кеш прямого доступа может быть неэффективен, а множественно-ассоциативный кеш «подхватит» две горячие области в разных местах памяти
   • Подсказка: либо на стек надо довольно много класть, либо обращаться к такому адресу на куче, чтобы теги прямого доступа у них совпадали
3. Написать программу, которая делает неэффективным предсказание переходов с глубиной историии 2

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