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

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

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

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

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

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

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

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

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

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

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

Очевидная схема —

1. выбрать очередную инструкцию из памяти,
2. декодировать,
3. выполнить

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

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

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

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

Могут ли эти операции происходить одновременно? Хватит ли на них одного такта? К. О. спешит на помощь: (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер) нет

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

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

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

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

Начнём с конца ☺. В RISC-V микропрограммный цикл устроен так:

1. (F, Istruction Fetch)

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

2. (D, Instruction decode)

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

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

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

3. (E, Execute operation)

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

4. (M, Memory access)

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

5. (W, Write back)

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

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

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

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

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

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

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

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

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

  • Так сначала адрес надо вычислить (E → M)

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

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

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

  • Да! В этом и была идея!

Конвейер

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

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

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

Эмуляция конвейера

Конвейер (и другие компоненты спецификации процессора) есть и в «полных» эмуляторах, наподобие QEMU и во всяких учебных моделях. Только в RARS его нет ☹.

На 2024-05-07 я нашёл два наглядных инструмента — Ripes и QtRvSim. Оба проекта написаны на Qt/C++ и имеют (экспериментальную) WebASM-реализацию.

QtRvSim выглядит удобнее и полнее (хотя в нём нет FPU), но Ripes больше подходит для сегодняшней лекции.

TODO подробнее свойства проектов

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

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

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

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

Воспользуется экспериментальной Web-версией Ripes

Конвейер в Ripes

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

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

   1     li    a1 1
   2     li    a2 2
   3     li    a3 3
   4     li    a4 4
   5     add   a5 a1 a2

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

Базовый текст Мы используем «неполноценную» модель процессора — «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

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

• Найти на вкладке с процессором большие блоки IF/ID, ID/EX, EX/MEM и MEM/WB. В них (кажется) нет собственных элементов (количество входов всегда совпадает с количеством выходов), но зато отражаются все данные, необходимые для работы следующего уровня конвейера

  • (да, если досок в заборе пять, то дырок в заборе четыре ☺)

• Включить показ данных, подготовленных для очередной стадии конвейера — выставить правой кнопкой «Ports → Show output values» на каждом блоке

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

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

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

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

     • Нет, если разделять память инструкций и памяти данных (Гарвардская архитектура).
       • Классическая модель памяти RARS позволяет просто проверить наличие 28-го бита (0x10000000).

     • Нет, если различать доступ к инструкциям (только на чтение, и только на этапе F) и к данным,

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

1. Зависимость по данным: одни значения вычисляются на основании других

   •    1         addi    t0 t0 5
        2         mv      t1 t0
     

   • Дойдём до стадии EX второй инструкции

   • Содержимое блока операндов обновляется только на последней стадии (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
   

   • Дойдём до стадии EX условного перехода

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

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

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

Можно попробовать заставить компилятор определять зависимости между инструкциями, переупорядочивать их и/или добавлять пузырьки. Пузырьки также можно добавлять аппаратно, для этого придётся отслеживать готовность стадий (вот тогда в блоках IF/ID, ID/EX, EX/MEM и MEM/WB появится какая-то схемотехника).

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

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

Пример зависимости по данным:

• Инструкция 1 вычисляет значение регистра X на третьем шаге, E, но заполняет блок операндов Registers только на пятом шаге, 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 (результату auipc), и получится 0x1000001 ☹

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

Задержка

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

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

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

        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ии на 2024-05-07 оно не работало ☹

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

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) — подменяет двумя пузырьками.

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

Мы можем попробовать увеличить быстродействие процессора, добавляя в него всевозможные дополнительные устройства. Грубо говоря, есть три направления:

1. Повышение эффективности конвейера (минимизация количества простоев и «пузырей»)
2. Параллельное вычисление
3. Кеширование результатов медленных операций

Кеш

• Обращение к оперативной памяти нагружает несколько устройств и в целом работает существенно медленнее, чем обращение, например, к регистру. Можно предусмотреть относительно небольшой блок «быстрой» памяти и применять классические алгоритмы кеширования для хранения в этом блоке наиболее востребованных данных.

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

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

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

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

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

Внеочередное исполнение

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

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

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

HART-ы

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

Д/З

TODO