В компьютерной инженерии внеочередное выполнение (или более формально динамическое выполнение ) — это парадигма, используемая в высокопроизводительных центральных процессорах для использования циклов инструкций , которые в противном случае были бы потрачены впустую. В этой парадигме процессор выполняет инструкции в порядке, определяемом доступностью входных данных и исполнительных блоков, [1], а не их исходным порядком в программе. [2] [3] При этом процессор может избежать простоя в ожидании завершения предыдущей инструкции и может тем временем обрабатывать следующие инструкции, которые могут быть выполнены немедленно и независимо. [4]
Внеочередное выполнение — это ограниченная форма архитектуры потока данных , которая была основной областью исследований в области компьютерной архитектуры в 1970-х и начале 1980-х годов.
Первой машиной, использовавшей внеочередное выполнение, была CDC 6600 (1964), разработанная Джеймсом Э. Торнтоном , которая использует табло для избежания конфликтов. Она позволяет инструкции выполняться, если ее исходные операндные регистры (чтение) не должны быть записаны какой-либо невыполненной более ранней инструкцией (истинная зависимость), а целевой (запись) регистр не должен быть регистром, используемым какой-либо невыполненной более ранней инструкцией (ложная зависимость). У 6600 отсутствуют средства, позволяющие избежать остановки исполнительного блока из -за ложных зависимостей ( конфликтов записи после записи (WAW) и записи после чтения (WAR), соответственно названных Торнтоном конфликтом первого порядка и конфликтом третьего порядка , который назвал истинные зависимости ( чтение после записи (RAW)) конфликтом второго порядка), поскольку каждый адрес имеет только одно местоположение, на которое он может ссылаться. WAW хуже, чем WAR для 6600, потому что, когда исполнительное устройство сталкивается с WAR, другие исполнительные устройства продолжают получать и выполнять инструкции, но при WAW назначение инструкций исполнительным устройствам останавливается, и они не могут получать никаких дальнейших инструкций, пока регистр назначения инструкции, вызывающей WAW, не будет записан более ранней инструкцией. [5]
Примерно два года спустя IBM System/360 Model 91 (1966) представила переименование регистров с помощью алгоритма Томасуло [6] , который устраняет ложные зависимости (WAW и WAR), делая возможным полное выполнение вне очереди. Инструкция, адресующая запись в регистр r n, может быть выполнена до того, как будет выполнена более ранняя инструкция, использующая регистр r n , путем фактической записи в альтернативный (переименованный) регистр alt-r n , который превращается в обычный регистр r n только после того, как будут выполнены все более ранние инструкции, адресующие r n , но до тех пор r n дается для более ранних инструкций, а alt-r n для более поздних, адресующих r n .
В модели 91 переименование регистров реализовано с помощью обхода, называемого Common Data Bus (CDB), и буферов операндов источника памяти, оставляя физические архитектурные регистры неиспользованными в течение многих циклов, поскольку самое старое состояние регистров, адресуемых любой невыполненной инструкцией, находится в CDB. Еще одним преимуществом модели 91 перед 6600 является возможность выполнять инструкции вне очереди в одном и том же исполнительном блоке , а не только между блоками, как в 6600. Это достигается станциями резервирования , из которых инструкции поступают в исполнительный блок по мере готовности, в отличие от очереди FIFO каждого исполнительного блока 6600. Модель 91 также способна переупорядочивать загрузки и сохранения для выполнения перед предыдущими загрузками и сохранениями, [7] в отличие от 6600, которая имеет только ограниченную возможность перемещать загрузки после загрузок и сохранять прошлые сохранения, но не загружает прошлые сохранения и сохраняет прошлые загрузки. [8] Только регистры с плавающей точкой модели 91 переименованы, что делает ее подверженной тем же ограничениям WAW и WAR, что и CDC 6600 при выполнении вычислений с фиксированной точкой. 91 и 6600 также страдают от неточных исключений , которые необходимо было решить, прежде чем выполнение вне очереди могло бы применяться повсеместно и стать практичным за пределами суперкомпьютеров.
Чтобы иметь точные исключения , надлежащее упорядоченное состояние выполнения программы должно быть доступно при возникновении исключения. К 1985 году были разработаны различные подходы, описанные Джеймсом Э. Смитом и Эндрю Р. Плешкуном. [9] CDC Cyber 205 был предшественником, поскольку при прерывании виртуальной памяти все состояние процессора (включая информацию о частично выполненных инструкциях) сохраняется в невидимом пакете обмена , так что он может возобновить выполнение в том же состоянии. [10] Однако, чтобы сделать все исключения точными, должен быть способ отменить эффекты инструкций. CDC Cyber 990 (1984) реализует точные прерывания с помощью буфера истории, который хранит старые (перезаписанные) значения регистров, которые восстанавливаются, когда исключение требует возврата инструкций. [9] С помощью моделирования Смит определил, что добавление буфера переупорядочивания (или буфера истории, или эквивалента) к Cray-1S снизит производительность выполнения первых 14 циклов Ливермора (не векторизованных) всего на 3%. [9] Важное академическое исследование по этой теме было проведено Йелом Паттом с его симулятором HPSm. [11]
В 1980-х годах многие ранние RISC -микропроцессоры, такие как Motorola 88100 , имели неупорядоченную обратную запись в регистры, что приводило к неточным исключениям. Инструкции начинали выполняться по порядку, но некоторые (например, с плавающей точкой) требовали больше циклов для завершения выполнения. Однако выполнение большинства базовых инструкций за один цикл значительно уменьшило масштаб проблемы по сравнению с CDC 6600.
Смит также исследовал, как заставить различные исполнительные блоки работать более независимо друг от друга и от памяти, интерфейса и ветвления. [12] Он реализовал эти идеи в Astronautics ZS-1 (1988), в котором было реализовано разделение конвейера целочисленных данных/загрузки/хранения от конвейера с плавающей точкой, что позволило переупорядочивать данные между конвейерами. ZS-1 также мог выполнять загрузки перед предыдущими сохранениями. В своей статье 1984 года он высказал мнение, что принудительное применение точных исключений только на конвейере целочисленных данных/памяти должно быть достаточным для многих случаев использования, поскольку оно даже допускает виртуальную память . Каждый конвейер имел буфер инструкций, чтобы отделить его от декодера инструкций, чтобы предотвратить остановку интерфейса. Чтобы еще больше отделить доступ к памяти от выполнения, каждый из двух конвейеров был связан с двумя адресуемыми очередями , которые эффективно выполняли ограниченное переименование регистров. [7] Похожая развязанная архитектура использовалась немного ранее в Culler 7. [13] ISA ZS-1, как и последующий POWER от IBM, способствовали раннему выполнению ветвлений.
С POWER1 (1990) IBM вернулась к внеочередному выполнению. Это был первый процессор, объединивший переименование регистров (хотя снова только регистров с плавающей точкой) с точными исключениями. Он использует физический файл регистров (т. е. динамически переназначенный файл как с незафиксированными, так и с зафиксированными значениями) вместо буфера переупорядочивания, но возможность отмены инструкций нужна только в блоке ветвления, который реализует буфер истории (названный IBM стеком счетчика программ ) для отмены изменений в регистрах подсчета, связи и условий. Возможность переупорядочивания даже инструкций с плавающей точкой все еще очень ограничена; из-за неспособности POWER1 переупорядочивать арифметические инструкции с плавающей точкой (результаты стали доступны в порядке), их регистры назначения не переименовываются. POWER1 также не имеет станций резервирования, необходимых для внеочередного использования того же блока выполнения. [14] [15] В следующем году в модель 900 IBM ES/9000 было добавлено переименование регистров для регистров общего назначения. Он также имеет станции резервирования с шестью записями для двойного целочисленного блока (в каждом цикле от шести инструкций до двух можно выбрать и выполнить) и шесть записей для FPU. Другие блоки имеют простые очереди FIFO. Расстояние переупорядочения составляет до 32 инструкций. [16] A19 из серии A мэйнфреймов Unisys также был выпущен в 1991 году и, как утверждалось, имел внеочередное выполнение, и один аналитик назвал технологию A19 на три-пять лет впереди конкурентов. [17] [18]
Первые суперскалярные однокристальные процессоры ( Intel i960CA в 1989 году) использовали простое планирование табло, как и CDC 6600 четверть века назад. В 1992–1996 годах быстрое развитие технологий, ставшее возможным благодаря увеличению количества транзисторов , привело к распространению вплоть до персональных компьютеров . Motorola 88110 (1992) использовал буфер истории для возврата инструкций. [19] Загрузки могли выполняться до предшествующих сохранений. Пока сохранения и ветви ожидали начала выполнения, последующие инструкции других типов могли продолжать проходить через все этапы конвейера, включая обратную запись. 12-записная емкость буфера истории накладывала ограничение на расстояние повторного заказа. [20] [21] [22] PowerPC 601 (1993) был развитием RISC Single Chip , который сам по себе был упрощением POWER1. 601 позволял инструкциям ветвления и с плавающей точкой обгонять целочисленные инструкции, уже находящиеся в очереди извлеченных инструкций, самые нижние четыре записи которой сканировались на предмет диспетчеризации. В случае промаха кэша загрузки и сохранения могли быть переупорядочены. Переименовывать можно было только регистры ссылок и счетчиков. [28] Осенью 1994 года NexGen и IBM с Motorola переименовали регистры общего назначения в однокристальные процессоры. Nx586 от NexGen был первым процессором x86, способным выполнять команды вне очереди, и имел расстояние переупорядочения до 14 микроопераций . [29] PowerPC 603 переименовал как регистры общего назначения, так и регистры FP. Каждый из четырех блоков выполнения без ветвления может иметь одну инструкцию, ожидающую перед собой, не блокируя поток инструкций к другим блокам. Буфер переупорядочения с пятью записями позволяет не более чем четырем инструкциям обгонять невыполненную инструкцию. Благодаря буферу хранения загрузка может получить доступ к кэшу раньше, чем предыдущее сохранение. [30] [31]
PowerPC 604 (1995) был первым однокристальным процессором с переупорядочением на уровне исполнительных блоков , так как три из шести его блоков имели двухзаходную станцию резервирования, что позволяло более новой записи выполняться перед старой. Емкость буфера переупорядочения составляет 16 инструкций. Четырехзаходная очередь загрузки и шестизаходная очередь сохранения отслеживают переупорядочение загрузок и сохранений при промахах кэша. [32] HAL SPARC64 (1995) превзошел емкость переупорядочения модели ES/9000 900, имея три восьмизаходных станции резервирования для целочисленных, с плавающей точкой и блока генерации адресов , а также двенадцатизаходную станцию резервирования для загрузки/сохранения, что обеспечивает большую переупорядоченность доступа к кэшу/памяти, чем у предыдущих процессоров. Одновременно в переупорядоченном состоянии может находиться до 64 инструкций. [33] [34] Pentium Pro (1995) представил унифицированную станцию резервирования , которая при емкости 20 микро-OP допускала очень гибкое переупорядочивание, поддерживаемое буфером переупорядочивания на 40 записей. Загрузки могут быть переупорядочены перед загрузками и сохранениями. [35]
Практически достижимая скорость выполнения за цикл возросла еще больше, поскольку полное внеочередное выполнение было дополнительно принято SGI / MIPS ( R10000 ) и HP PA-RISC ( PA-8000 ) в 1996 году. В том же году Cyrix 6x86 и AMD K5 принесли передовые методы переупорядочивания в основные персональные компьютеры. С тех пор как DEC Alpha получила внеочередное выполнение в 1998 году ( Alpha 21264 ), самые производительные внеочередные процессорные ядра не имели себе равных среди ядер с последовательным выполнением, кроме HP / Intel Itanium 2 и IBM POWER6 , хотя последний имел внеочередной блок с плавающей точкой . [36] Другие высокопроизводительные процессоры с последовательным выполнением значительно отстали, а именно UltraSPARC III / IV от Sun и мэйнфреймы IBM , которые потеряли возможность внеочередного выполнения во второй раз, оставаясь в поколении z10 с последовательным выполнением . Позднее процессоры с большим порядком выполнения были ориентированы на многопоточное выполнение, но в конечном итоге серии SPARC T и Xeon Phi перешли на внеочередное выполнение в 2011 и 2016 годах соответственно. [ необходима цитата ]
Почти все процессоры для телефонов и других недорогих приложений оставались с последовательным выполнением вплоть до 2010 года . Сначала Scorpion от Qualcomm (расстояние переупорядочения 32) поставлялся в Snapdragon , [37] а немного позже A9 от Arm сменил A8 . Для недорогих персональных компьютеров x86 микроархитектура Bonnell с последовательным выполнением в ранних процессорах Intel Atom сначала была оспорена микроархитектурой Bobcat от AMD , а в 2013 году на смену ей пришла микроархитектура Silvermont с внеочередным выполнением . [38] Поскольку сложность внеочередного выполнения исключает достижение минимального энергопотребления, стоимости и размера, выполнение с порядком по-прежнему распространено в микроконтроллерах и встраиваемых системах , а также в ядрах телефонного класса, таких как Arm A55 и A510 в конфигурациях big.LITTLE .
Исполнение вне очереди более сложно по сравнению с базовым исполнением в порядке. В процессорах конвейерного исполнения в порядке выполнение инструкций перекрывается конвейерным образом, и для завершения каждой из них требуется несколько тактов . Следствием этого является то, что результаты предыдущей инструкции будут отставать там, где они могут понадобиться в следующей. Исполнение в порядке все равно должно отслеживать эти зависимости. Однако его подход довольно прост: остановка, каждый раз. Исполнение вне очереди использует гораздо более сложные методы отслеживания данных, как описано ниже.
В более ранних процессорах обработка инструкций выполнялась в цикле инструкций, обычно состоящем из следующих шагов:
Часто процессор с последовательным выполнением имеет запись битового вектора , в который будут записываться регистры конвейером. [39] Если какие-либо входные операнды имеют соответствующий бит, установленный в этом векторе, инструкция останавливается. По сути, вектор выполняет значительно упрощенную роль защиты от опасностей регистра. Таким образом, выполнение вне очереди использует двумерные матрицы, тогда как выполнение по порядку использует одномерный вектор для избежания опасностей.
Эта новая парадигма разбивает обработку инструкций на следующие этапы:
Ключевая концепция обработки OoOE заключается в том, чтобы позволить процессору избегать класса остановок, которые происходят, когда данные, необходимые для выполнения операции, недоступны. В схеме выше процессор OoOE избегает остановок, которые происходят на шаге (2) процессора in-order, когда инструкция не полностью готова к обработке из-за отсутствующих данных.
Процессоры OoOE вовремя заполняют эти слоты другими готовыми инструкциями , а затем в конце переупорядочивают результаты, чтобы создать впечатление, что инструкции были обработаны как обычно. Способ, которым инструкции упорядочены в исходном компьютерном коде, известен как порядок программы , в процессоре они обрабатываются в порядке данных , порядке, в котором данные, операнды, становятся доступными в регистрах процессора. Для преобразования из одного порядка в другой и поддержания логического порядка вывода требуется довольно сложная схема; сам процессор выполняет инструкции в, казалось бы, случайном порядке.
Преимущество обработки OoOE растет по мере углубления конвейера инструкций и увеличения разницы в скорости между основной памятью (или кэш-памятью ) и процессором. На современных машинах процессор работает во много раз быстрее памяти, поэтому за то время, которое процессор in-order тратит на ожидание поступления данных, он мог бы обработать большое количество инструкций.
Одним из отличий, созданных новой парадигмой, является создание очередей, что позволяет отделить этап отправки от этапа выпуска, а этап выпуска от этапа выполнения. Раннее название парадигмы было развязанная архитектура . В более ранних процессорах in-order эти этапы работали довольно жестко , конвейерно.
Инструкции программы не могут быть запущены в изначально указанном порядке, пока конечный результат является правильным. Он отделяет этапы выборки и декодирования от этапа выполнения в конвейерном процессоре с помощью буфера .
Цель буфера — разделить доступ к памяти и выполнить функции в компьютерной программе, а также достичь высокой производительности за счет использования мелкозернистого параллелизма между ними. [40] При этом он эффективно скрывает все задержки памяти с точки зрения процессора.
Буфер большего размера теоретически может увеличить пропускную способность. Однако если процессор имеет неправильное предсказание ветвления , то может потребоваться очистка всего буфера, что приведет к потере большого количества тактовых циклов и снижению эффективности. Кроме того, буферы большего размера создают больше тепла и используют больше места на кристалле . По этой причине сегодня разработчики процессоров отдают предпочтение многопоточному подходу к проектированию.
Разделенные архитектуры обычно считаются бесполезными для вычислений общего назначения, поскольку они не очень хорошо справляются с кодом, требующим интенсивного управления. [41] Код, требующий интенсивного управления, включает такие вещи, как вложенные ветви, которые часто встречаются в ядрах операционных систем . Разделенные архитектуры играют важную роль в планировании в архитектурах с очень длинными командными словами (VLIW). [42]
Чтобы избежать ложных зависимостей операндов, которые могут снизить частоту, когда инструкции могут быть выданы не по порядку, используется техника, называемая переименованием регистров . В этой схеме имеется больше физических регистров, чем определено архитектурой. Физические регистры помечены так, что несколько версий одного и того же архитектурного регистра могут существовать одновременно.
Очередь результатов необходима для решения таких проблем, как неправильные предсказания переходов и исключения/ловушки. Очередь результатов позволяет перезапускать программы после исключения, что требует выполнения инструкций в порядке программы. Очередь позволяет отбрасывать результаты из-за неправильных предсказаний на более старых инструкциях переходов и исключений, принятых на более старых инструкциях.
Возможность отдавать распоряжения, проходящие через ветви, которые еще не разрешены, называется спекулятивным исполнением .
не ждать выполнения предыдущих инструкций, если эта инструкция не зависит от них
Алгоритм "позволяет последовательным инструкциям, которые обычно останавливаются из-за определенных зависимостей, выполняться непоследовательно" (также известно как выполнение вне очереди).
Такая гибкость повышает производительность, поскольку позволяет выполняться с меньшим временем "ожидания".
{{cite book}}
: |work=
проигнорировано ( помощь )Новый A19 использует "суперскалярные" методы научных компьютеров для одновременного выполнения множества инструкций. A19 может перекрывать до 140 операций, что в 10 раз больше, чем могут обычные мэйнфреймы.