Повышение производительности процессора: конвейер

Базовая статья: план лекции и семинарского занятия в курсе Андрея Татарникова (в первую очередь, слайды к ней; на всякий случай спас их тут).

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

• Отдельно стоит присмотреться к тому, как биты инструкции соответствуют «проводам», соединяющим микроархитектурные компоненты.

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

Итак, мы уже наизобретали в процессоре:

• Арифметико-логическое устройство
• Устройство управления
• Регистры
• Обращение к оперативной памяти посредством шины
  • Кеш этой памяти (а то слишком медленная)

Эти (и другие) компоненты

• Существуют и работают одновременно
• Не могут работать быстрее, чем одно действие за один такт работы процессора
• Пользуются друг другом при выполнении инструкций
• Для выполнения одной инструкции должны быть задействованы в определённом порядке

⇒ Одна инструкция — это несколько «шагов» взаимодействия компонентов процессора. Микропрограмма — это последовательность таких шагов во время работы процессора.

Цикл выполнения инструкции

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

1. Во-первых, нужно отдельно рассматривать обращение к памяти, потому что это целое приключение

2. Во-вторых, не вполне понятно, как, например, должна работать инструкция addi t1 t1 5: она сначала читает из регистра t1, затем вычисляет сумму, а только затем записывает результат обратно в t1 — и всё это называется «выполнение».

3. В-третьих, мы забыли про то, что адрес «очередной инструкции» надо сначала вычислить: либо прибавить 4 к предыдущему адресу, либо изготовить из pc и смещения в инструкции перехода.

Могут ли эти операции происходить одновременно? Хватит ли на них одного такта?

• Появляется новая сущность — т. н. блок операндов (register file), в который считываются значения из регистров для вычислений.

• Появляется ещё одно устройство — сумматор адреса

  • В RISC-V для двух описанных выше случаев устройства разные, и работают в разное время: прибавлятель 4 — сразу, а прибавлятель смещения из инструкции перехода — только после заполнения блока операндов, откуда это смещение и берётся

Микропрограммный цикл RISC-V

1. (F, Istruction Fetch)

   • Выборка очередной инструкции из памяти

2. (D, Instruction decode)

   • Декодирование опкода / функций

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

   • Вычисление непосредственно следующего адреса (+4)

3. (E, Execute operation)

   • Операции над регистрами (сложение, сдвиг и прочие упражнения)
   • Операции, требующие регистров (чтение, переход и т. п.)

4. (M, Memory access)

   • Работа с памятью (чтение / запись)

5. (W, Write back)

   • Обновление блока операндов и самих регистров

Часто задаваемые вопросы:

• Может ли инструкция состоять из менее, чем пяти микрокоманд?

  • Да. Например, инструкция, не меняющая регистры, не нуждается в W

• Может, тогда пропустить W — инструкция будет работать на 20% быстрее?

  • Нет, ресинхронизация строгой последовательности обойдётся дороже

• Почему W в самом конце? Вычислили — положили обратно

  • Потому что есть ещё результаты чтения из памяти, W должен быть после него.

• Тогда почему M так поздно?

  • Так сначала адрес надо вычислить

• Можно ли было учесть все разные случаи и придумать более сложный путь обработки инструкции?

  • Можно, но вариант MIPS/RISC-V, по видимому, наиболее сложный из числа лишённых логики (логику должен будет реализовывать какой-то другой, ещё более быстрый процессор?)

• Могут ли все пять стадий выполняться параллельно, за них же отвечают различные компоненты?
  • Да! В этом и была идея!

Конвейер

Вычислительный конвейер — базовая статья. С некоторых пор конвейер, изобретённый для MIPS/RISC стал восприниматься как «просто конвейер»

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

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

Отступление про Ripes

Ripes — это проект визуального эмулятора RISC-V. Главная особенность: эмулируется работа отдельных компонентов процессора (вплоть до конкретных логических цепей!), а уже из них конструируется процессор. Написан на Qt.

Сейчас в нём нет только прерываний / исключений.

Это значит, что при наличии соответствующего ресурса для него можно написать и прерывания, и MMU. Правда, у нас, скорее всего, такого ресурса пока нет.

Linux:

• Скачать и запустить Appimage

  • Сделать chmod +x скачанному файлу — это само приложение

  • Нужны права пользователя на fusermount

  • В ALT Linux задаётся настройкой control fusermoun public из-под root

• Вариант: скачать Appimage, сделать chmod +x и запустить с ключом --appimage-extract

  • Создастся каталог squashfs-root, и оттуда можно запустить программу squashfs-root/AppRun или squashfs-root/usr/bin/Ripes

• Установить пакет из репозитория, если есть (в ALT Linux довольно старый)

Конвейер в Ripes

TODO скриншоты всех вариантов примеров

Выберем по кнопке с процессором «5-stage processor w/o forwarding or hazard detection» — это самый простой вариант с конвейером.

Пример работы конвейера без конфликтов

   1 .data
   2 var:    .word 0x123
   3 .text
   4  loop:  lw    t0 var
   5         li    t1 7
   6         li    t2 8
   7         add   t3 t0 t1
   8         mul   t4 t1 t2
   9         sw    t3 var t0

Конфликты в конвейере

Базовый текст Мы используем «неполноценную» модель процессора — «5-stage processor w/o forwarding or hazard detection»: в ней нет распознавания и исправления конфликтов

Для того, чтобы в Ripes посмотреть, как это (не) работает, надо:

• Включить показ данных, подготовленных к очередной стадии конвейера. Это большие блоки IF/ID, ID/EX, EX/MEM и MEM/WB

• Выставить правой кнопкой «Show output values»
• Пройти программу пошагово

типы конфликтов

0. Структурный конфликт — различные этапы конвейера используют-таки один и тот же компонент CPU

   • Например F и M оба обращаются к памяти — это проблема?

   • Нет, если разделять память инструкций и памяти данных (Гарвардская архитектура)

   • Нет, если различать доступ к инструкциям (только на чтение, и только на этапе F) и к данным, и при этом обеспечить два разных кеша (или два канала кеша). Классическая модель памяти позволяет просто проверить наличие 27(?)-го бита (0x10000000).

   • Этого конфликта нет в базовом RISC-V (хотя, возможно, есть в более сложных конфигуациях/расширениях)

1. Зависимость по данным:

   •    1         addi    t0 t0 5
        2         mv      t1 t0
     

     • TODO скриншот с отчёркнутым местом, где в блоке ещё старое значение

   • Содержимое блока операндов обновляется только на последней стадии (W) инструкции addi.

   • Стадия E инструкции mv может выполниться только после этого

   • ⇒ Надо обеспечить пропуск двух шагов конвейера:

     • например, вставить два оператора nop между addi и mv (волшебным образом все три команды — это addi ☺); одного nop не хватит

     • процессор может делать это автоматически — это называется «добавить в конвейер пузырёк» (bubble)

2. Зависимость по управлению:

      1 loop:    li    t1 1
      2          li    t2 2
      3          bgt   t2 t1 loop
      4          li    t3 3
   

   • TODO скриншот с отчёркнутым местом, где выбралась не та инструкция

   • Возникает при условных переходах — когда вплоть до стадии E неизвестно, каким будет адрес следующей инструкции, т. е. следующая инструкция не может выйти на стадию F.

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

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

Можно попробовать заставить компилятор определять зависимости между инструкциями и переупорядочивать их.

Проброс регистров

А можно ли решить проблему зависимости по данным аппаратно?

Итак:

• Инструкция 1 вычисляет значение регистра X на третьем шаге, E, но заполняет блок операндов только на пятом шаге, W

• Следующая за ней инструкция 2 использует X на шаге E (который наступает одновременно с M инструкции 1)

Замечание. Строго говоря, X и его содержимое присутствуют в это время в процессоре, но не ячейках памяти, а в виде сигналов на «проводах».

Проброс (forwarding) регистра: доступ стадии E инструкции к данным в регистре не через блок операндов, а непосредственно путём съёма этих данных со стадий предыдущих двух инструкций

• Со стадии E, если запись в регистр происходило при вычислении

• Со стадии M, если регистр заполнялся при чтении из памяти

Загрузим этот пример в процессор с пробросом, но без определения зависимостей(в Ripes он называется «5-Stage processor w/o hazard detection»

Отличие этого (тоже всё ещё «неполноценного») процессора — в нём есть т. н. forward unit, компонент проброса:

Предыдущий пример теперь работает совсем без nop, а вот проброс регистра из M экономит только один шаг из двух:

   1 .data
   2 var:        .word 0x123
   3 .text
   4     lw      t1 var
   5     addi    t1 t1 1

• Без nop между lw и addi внезапно™ прибавит 1 к предыдущему значению t1, и получится 0x1000001 ☹

Вот это уже «не лечится» — мы не можем заглянуть в будущее и узнать, какое значение будет прочитано на стадии M. Помогает только разнесение зависимых инструкций или вставка nop.

Пузырёк

Сменим тип процессора на более «настоящий» — «5-stage processor»

Соседство двух инструкций определённого типа и зависимость между ними по данным автоматически приводит к задержке (stall) конвейера, что эквивалентно вставке «пустой инструкции» — пузырька.

В Ripes есть удобная кнопка «Show stage table» (выглядит как электронная таблица). Для нашего примера она покажет такое:

        0       1       2       3       4       5       6       7       8       
auipc x6 0x10000        IF      ID      EX      MEM     WB                                      
lw x6 0 x6              IF      ID      EX      MEM     WB                              
addi x6 x6 1                    IF      ID      -       EX      MEM     WB              

Зависимость по управлению и зачистка конвейера

C зависимостью по управлению всё ещё более печально: она чётко «из будущего». Загрузим этот пример в процессор с пробросом, но без определения зависимостей (в Ripes он называется «5-Stage processor w/o hazard detection»:

   1 loop:    li    t1 1
   2          li    t2 2
   3          bgt   t2 t1 loop
   4          li    t3 3
   5          li    t4 4

• Вечного цикла не будет — К тому моменту, когда в bgt определился адрес перехода, предпоследняя инструкция (li t3 3) уже была не только выбрана, но и декодирована (т. е. прошла стадии F и D), а последняя (li t4 4) уже прошла F.

• Ток что одного nop недостаточно, нужно два

• Кстати, именно так поначалу работали процессоры MIPS (это называлось «delay slot»), ассемблерам и программистам рекомендовалось переупорядочивать инструкции или вставлять nop самостоятельно.

Посмотрим, как с этой задачей справляется процессор с определением зависимостей (т. е. «обычный» — «5-stage processor»):

1. выбирает li t3 3,

2. выбирает li t4 4 и декодирует li t3 3

3. но когда выясняется, что реальный адрес дугой (после стадии E инструкции bgt),

   • выполняет F той инструкции, на которую произошёл переход (li t1 1)

   • а стадии теперь уже D и E ошибочно выбранных инструкций зачищает (flush) — подменяет двумя пузырьками.

Другие способы повышения быстродействия

• Предсказатель переходов

  • Может кардинально улучшить проблему зависимости по управлению: достаточно по умолчанию выбирать не следующую, а предсказанную инструкцию!

• Суперскалярность

  • Проблема формирования пакета независимых инструкций (т. н. issue)

  • Пример суперскалярного процессора «всего лишь» с двумя ALU есть в Ripes

• Упреждающие вычисления

  • Требую несколько аппаратных контекстов вычисления

• Векторные операциии

  • В действительности повышают не быстродействие, а эффективность обработки однотипных данных
  • Алгоритмы группировки данных под векторную обработку в общем случае очень сложны
• HART-ы
  • В действительности повышают не быстродействие, а эффективность реализации многозадачных систем
  • Распараллеливание произвольного алгоритма — в общем случае неразрешимая задача

Д/З

TODO