Внеочередное исполнение - Out-of-order execution

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

История

Выполнение вне очереди - это ограниченная форма вычисления потока данных , которая была основной областью исследований в области компьютерной архитектуры в 1970-х и начале 1980-х годов.

Важное научное исследование по этой теме было проведено Йельским Паттом и его симулятором HPSm . Статья Джеймса Смита и А.Р. Плешкуна, опубликованная в 1985 году, завершила схему, описав, как точное поведение исключений может поддерживаться в вышедших из строя машинах.

Вероятно, первой машиной, использующей исполнение вне очереди, является CDC 6600 (1964 г.), которая использовала табло для разрешения конфликтов. Однако 6600 не хватало обработки конфликтов WAW , вместо этого она остановилась. Эту ситуацию Торнтон назвал «конфликтом первого порядка». Хотя у него было и разрешение конфликтов RAW (называемое «конфликтом второго порядка»), и разрешение конфликтов WAR (называемое «конфликтом третьего порядка»), всех которых было достаточно, чтобы объявить его способным к полному неупорядоченному выполнению, 6600 не имел точная обработка исключений. Ранняя и ограниченная форма предсказания ветвлений была возможна до тех пор, пока ветвление велось к местоположениям в так называемом «стеке инструкций», который был ограничен в пределах семи слов от счетчика программ.

Примерно три года спустя в IBM System / 360 Model 91 (1966) был представлен алгоритм Томасуло , который делает возможным полное выполнение вне очереди . В 1990 году IBM представила первый микропроцессор с нарушением порядка, POWER1 , хотя выполнение с нарушением порядка ограничено инструкциями с плавающей запятой (как и в случае с Model 91).

В 1990-х годах выполнение вне очереди стало более распространенным и было представлено в IBM / Motorola PowerPC 601 (1993), Fujitsu / HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) и DEC Alpha 21264 (1996). Заметными исключениями из этой тенденции являются Sun UltraSPARC , HP / Intel Itanium , Intel Atom до Silvermont Architecture и IBM POWER6 .

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

Основная концепция

Чтобы оценить OoO Execution, полезно сначала описать по порядку, чтобы иметь возможность сравнить их. Инструкции не могут быть выполнены мгновенно: они требуют времени (несколько циклов). Следовательно, результаты будут отставать от того, где они необходимы. По-прежнему необходимо отслеживать зависимости. Однако его подход довольно прост: каждый раз заглохнуть. OoO использует гораздо более сложные методы отслеживания данных, как показано ниже.

Заказанные процессоры

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

  1. Получение инструкций .
  2. Если входные операнды доступны (например, в регистрах процессора), инструкция отправляется в соответствующий функциональный блок . Если один или несколько операндов недоступны в течение текущего тактового цикла (обычно из-за того, что они извлекаются из памяти ), процессор останавливается, пока они не станут доступными.
  3. Инструкция выполняется соответствующим функциональным блоком.
  4. Функциональный блок записывает результаты обратно в регистровый файл .

Часто упорядоченный процессор имеет простой «битовый вектор», в который он записывается, который регистрирует конвейер, в который он (в конечном итоге) будет записывать. Если какой-либо из входных операндов имеет соответствующий бит, установленный в этом векторе, инструкция останавливается. По сути, вектор выполняет значительно упрощенную роль защиты от опасностей регистров. Таким образом, мы наблюдаем, что Out-of-Order использует 2D-матрицы, где In-order использует 1D-вектор для предотвращения опасности.

Вышедшие из строя процессоры

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

  1. Получение инструкций.
  2. Отправка инструкций в очередь инструкций (также называемую буфером инструкций или станциями резервирования ).
  3. Инструкция ожидает в очереди, пока не станут доступны ее входные операнды. Инструкция может покинуть очередь до более старых инструкций.
  4. Инструкция выдается соответствующему функциональному блоку и выполняется этим блоком.
  5. Результаты поставлены в очередь.
  6. Только после того, как все более старые инструкции записывают свои результаты обратно в регистровый файл, этот результат записывается обратно в регистровый файл. Это называется этапом выпуска или выхода на пенсию.

Ключевая концепция обработки OoOE состоит в том, чтобы позволить процессору избежать определенного класса остановок, которые возникают, когда данные, необходимые для выполнения операции, недоступны. В схеме выше процессор OoOE избегает остановки, которая происходит на этапе (2) обработчика очередности, когда инструкция не полностью готова к обработке из-за отсутствия данных.

Процессоры OoOE заполнить эти «слоты» во время с другими инструкциями, которые готовы, а затем повторно порядком результатов в конце , чтобы сделать вид , что инструкции были обработаны в обычном режиме. То, как команды упорядочены в исходном компьютерном коде, называется программным порядком , в процессоре они обрабатываются в порядке данных, порядке , в котором данные, операнды, становятся доступными в регистрах процессора. Для преобразования одного порядка в другой и поддержания логического порядка вывода требуется довольно сложная схема; сам процессор выполняет инструкции в случайном порядке.

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

Разделение отправки и выпуска позволяет выпускать вне очереди

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

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

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

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

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

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

Разделение выполнения и обратной записи позволяет перезапустить программу

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

Возможность отдавать инструкции после ветвей, которые еще предстоит выполнить, называется спекулятивным исполнением .

Выбор микроархитектуры

  • Отправляются ли инструкции в централизованную очередь или в несколько распределенных очередей?
Процессоры IBM PowerPC используют очереди, которые распределены между различными функциональными блоками, в то время как другие вышедшие из строя процессоры используют централизованную очередь. IBM использует термин станции резервирования для своих распределенных очередей.
  • Существует ли реальная очередь результатов или результаты записываются непосредственно в файл реестра? Для последнего функция организации очереди обрабатывается картами регистров, которые содержат информацию о переименовании регистров для каждой выполняющейся инструкции.
Ранние вышедшие из строя процессоры Intel использовали очередь результатов, называемую буфером переупорядочения , в то время как большинство более поздних вышедших из строя процессоров использовали карты регистров.
Точнее: микропроцессоры семейства Intel P6 имеют как буфер переупорядочения (ROB), так и таблицу псевдонимов регистров (RAT). ROB был мотивирован в основном восстановлением неверного предсказания ветвления.
Семейство Intel P6 было одним из первых микропроцессоров OoOE, но было вытеснено архитектурой NetBurst . Спустя годы Netburst оказался тупиком из-за своего длинного конвейера, предполагавшего возможность гораздо более высоких рабочих частот. Материалы не смогли соответствовать амбициозным целям разработки часов из-за проблем с температурой, и более поздние разработки, основанные на NetBurst, а именно Tejas и Jayhawk, были отменены. Intel вернулась к дизайну P6 как основе микроархитектур Core и Nehalem . Последующие микроархитектуры Sandy Bridge , Ivy Bridge и Haswell представляют собой отход от методов переупорядочения, использованных в P6, и используют методы переупорядочения из EV6 и P4, но с несколько более коротким конвейером.

Смотрите также

использованная литература

дальнейшее чтение

  • Смит, Джеймс Э .; Плешкун, АР (июнь 1985 г.). «Реализация точных прерываний в конвейерных процессорах». Новости компьютерной архитектуры ACM SIGARCH . 13 (3): 36–44. DOI : 10.1145 / 327070.327125 .