Конвейерный процессор обладает большей производительностью, чем однотактная и многотактная реализация, при прочих равных условиях. Для достижения максимальной производительности необходимо, чтобы конвейер не простаивал и был полностью заполнен инструкциями, что является нетривиальной задачей, так как в таком устройстве могут возникать конфликты.
Говорят, что возник структурный конфликт, если конвейер пришлось приостановить из-за нехватки какого-то ресурса. Как правило это связано либо с недостаточной конвейеризированностью операционных устройств, либо из-за ожидания доступа к памяти при одновременном обращении к ней с нескольких ступеней.
Говорят, что возник конфликт по данным, если порядок чтения или записи операндов отличается от порядка в неконвейерной машине. Проще говоря, если возникает ситуация, что какая-то команда пытается считать операнд, который еще не записан или записать на то место, откуда ещё не успели считать.
Конфликт по управлению возникает, когда приходит команда условного перехода и пока эта команда не выполнится, сохраняется неопределенность какую команду загружать следующей на исполнение (как будто условие сработало или нет?).
Производительность конвейера напрямую зависит от блока устранения конфликтов — части устройства управления, которая следит за ходом выполнения программы и оперативно определяет и устраняет образовавшиеся конфликты.
Для того, чтобы обнаружить конфликт по данным применяются так называемые критерии Бернштейна — для двух подряд идущий инструкций k и k+1 проверяются адреса считываемых входных операндов и адреса записываемых выходных результатов, если существует пересечение этих множеств, то можно заключить, что существует зависимость (конфликт) по данным.
output(k) & input(k+1) != 0 -> Конфликт чтение после записи (RAW) input(k) & output(k+1) != 0 -> Конфликт запись после чтения (WAR) output(k) & output(k+1) != 0 -> Конфликт запись после записи (WAW)
Для того, чтобы минимизировать влияние подобного конфликта применяются различные методы, среди которых:
- Метод пузырька (то есть, обнулять стадии конвейера, которые приводят к конфликту, пока он не будет разрешён)
- Пересылка результата (то есть, при возникновении конфликта не дожидаться, когда данные дойдут до стадии записи в память, а пересылать их на более ранние стадии конвейера, где они требуются, с более поздних стадий, где эти данные уже получены)
- Внеочередное исполнение команд (то есть, ввести специальную аппаратуру, которая в автоматическом режиме будет менять последовательность инструкций так, чтобы конфликты разрешались, но при этом логика работы программы не была нарушена)
- Переименовывание регистров (то есть, ввести дополнительные теневые регистры, которые не доступны программисту, но в которых будут сохраняться некоторые результаты операций, чтобы устранить конфликты WAR и WAW)
- Сортировка команд на этапе компиляции (статический метод разрешения конфликта, при котором компилятор пытается расположить максимально далеко друг от друга инструкции, которые могут вызвать конфликт)
Конфликты по управлению влияют на производительность конвейера больше всего, так как по статистике, примерно, каждая седьмая инструкция является инструкцией условного перехода. Другими словами, в среднем, такой конфликт будет возникать раз в семь тактов.
Для сокращения задержек, вызванных появлением условного перехода применяют следующие подходы:
- Вычисление исполнительного адреса перехода на ступени декодирования команды, с целью максимально быстрой загрузки инструкции по этому адресу
- Использование буфера адресов переходов (branch target buffer – BTB), специальной памяти в которой сохраняются адреса переходов уже вычисленных инструкций условного перехода, чтобы при повторном их исполнении адрес перехода уже был известен и его не надо было вычислять
- Кэш-память для хранения команд, расположенных в точке перехода (BTBI). То же самое, что и BTB, но сохраняется не адрес перехода, а инструкция, располагающаяся по целевому адресу
- Использование буфера цикла (специальная аппаратура, запоминающая количество итераций цикла, для успешного предсказания результата условного перехода, реализующего выход из цикла)
Для минимизации конфликтов по управлению, при считывании очередной инструкции условного перехода, делается предположение о том, произойдёт переход или нет. В случае успешного предсказания в конвейер загружается правильная инструкция, тогда производительность не падает. В случае неуспешного предсказания все стадии конвейера, куда успели попасть инструкции из неправильной ветки, очищаются — производительность конвейера снижается.
Можно выделить два основных подхода к предсказанию условного перехода: статический (предположение делается ещё до исполнения программы) и динамический (предположение делается автоматически, прямо во время исполнения программы, на основе собранной статистики переходов).
Эффективность статических методов колеблется в больших диапазонах от 50 до 90% успешных предсказаний. Среди таких методов:
- Переход происходит всегда
- Переход не происходит никогда
- Предсказание определяется по результатам профилирования (компилятор запускает программу с сырыми данными и фиксирует направления переходов, размещая в специальных полях инструкции результат предсказания)
- Предсказание зависит от направления перехода
Обычно статические методы используются в связке с динамическими, которые собирают статистику переходов в реальном времени и на основе этой статистики делают предположение о переходе. В основе динамических методов лежат несколько подходов к накоплению информации (статистики) о совершенных переходах.
PHT (pattern hystory table) — специальная память, состоящая из двухбитных ячеек памяти, доступ к которым происходит по некоторому паттерну. Если условный переход происходит, то значение ячейки памяти из PHT закреплённой за этим условным переходом, увеличивается на 1 (но не больше максимального значения 11). Если переход не происходит, то уменьшается на 1 (но не меньше минимального значения 00). Предсказанием является старший из этих двух бит, если он 1, то делается предсказание, что переход произойдёт, если он равен 0, то делается предположение, что он не произойдёт.
GHR (global history register) — регистр глобальной истории, являющийся сдвиговым регистром некоторой длинны, сдвигающий данные каждый раз, когда поступает на исполнение инструкция условного перехода, при этом в регистр задвигается 1, если переход произошёл, и 0, если нет. Таким образом регистр хранит историю результатов переходов последних n (разрядность регистра) инструкций условного перехода.
LHR (local history register) — регистр локальной истории. По сути, то же самое, что и GHR, только таких сдвиговых регистров много и они хранят историю конкретных условных переходов.
PHT, GHR и LHR применяются в устройствах предсказания переходов (branch predictor unit). Все многообразие реализаций предсказателей переходов можно условно разделить на 4 категории:
- Одноуровневые (бимодальные). Такие устройства используют в качестве паттерна (адреса) для PHT значение счётчика команд PC. Тогда для каждого условного перехода будет накапливаться статистика, по принципам заложенным в PHT. Чаще используется только часть адреса, чтобы была не очень большая PHT. В таком случае статистика может накладываться друг на друга от разных переходов, это называется alliassing, как показывают исследования он положительно влияет на результаты предсказания.
- Двухуровневые (коррелированные). В таких устройствах тоже используется PHT, но в качестве паттерна (адреса) используется GHR или часть его бит. Либо один из регистров LHR может быть паттерном для PHT. Так же хорошо зарекомендовали себя коррелированные предсказатели, использующие в качестве паттерна для PHT объединение GHR и PC, например, операцией конкатенации (объединения части бит из одного, и части бит от другого) или Исключающего ИЛИ.
- Гибридные. Такие устройства объединяют в себе несколько предикторов (предсказателей) с разной архитектурой и разными характеристиками. Выбор итогового предсказания из всех предсказателей осуществляется по мажоритарной схеме — кто меньше ошибался, тому и верим.
- Ассиметричные. Тоже самое, что и гибридные, но для каждого из предикторов используются собственные PHT, то есть ведётся независимая статистика между всеми предсказателями. Выбор также ведётся по мажоритарной схеме.
Для обеспечения приемлемого снижения производительности при ошибочном предсказании перехода и, как следствие — очищение конвейера, эффективность предсказания должна соответствовать порядка 97%.
- Ссылка на видеозапись лекции
- Один из немногих и пожалуй самый объёмный материал по этому вопросу на русском языке, так что выбирать не приходится. Разбираются методы минимизации конфликтов конвейера на уровне структурной организации и на уровне лежащих в решении этой задачи идей [Орлов и Цилькер. Организация ЭВМ и систем — Глава 9. начиная с параграфа 'Конфликты в конвейере команд', до параграфа (и включая его) 'Динамическое предсказание переходов']
- Более краткий вариант предыдущего источника можно найти в старых лекциях [Кафедра ВТ. Микропроцессорные средства и системы — Лекция 2.3 и 2.4]
- Несколько примеров устранения конфликтов по данным и управлению в контексте архитектуры RISC-V, правда на английском языке, можно найти в этой книге [Patterson и Hennessy. Computer organization and design RISC-V edition — параграфы 4.7, 4.8]
- Ещё один источник для заинтересованных, тоже на английском языке, но с более академическим подходом и большим объёмом полезной информации [Shen и Lipasti. Modern processor design — Глава 2]