Предикация (компьютерная архитектура) - Predication (computer architecture)

Не путать с Прогноз ветвления.

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

Обзор

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

К счастью, один из наиболее распространенных шаблонов кода, который обычно полагается на ветвление, имеет более элегантное решение. Рассмотрим следующее псевдокод:[1]

если условие    {сделай что-нибудь}еще    {что-то еще};

В системе, которая использует условное ветвление, это может привести к машинные инструкции похож на:[1]

ответвляться-если-условие к label1что-то ещеответвляться-к label2label1:сделай что-нибудьlabel2:...

При использовании предикации все возможные пути ветвления закодированы внутри, но некоторые инструкции выполняются, а другие - нет. Основная идея состоит в том, что каждая инструкция связана с предикатом (слово здесь используется аналогично его использованию в логика предикатов ) и что инструкция будет выполнена только в том случае, если предикат истинен. Машинный код для приведенного выше примера с использованием предсказания может выглядеть примерно так:[1]

(условие) сделай что-нибудь(нет условие) что-то еще

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

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

Преимущества

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

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

Недостатки

Главный недостаток Predication - увеличенное пространство для кодирования. В типичных реализациях каждая инструкция резервирует битовое поле для предиката, определяющего, при каких условиях эта инструкция должна действовать. Когда доступная память ограничена, как на встроенные устройства, эта стоимость пространства может быть непомерно высокой. Однако некоторые архитектуры, такие как Большой палец-2 могут избежать этой проблемы (см. ниже). Прочие недостатки следующие:[3]

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

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

История

Предсказанные инструкции были популярны в европейских компьютерных разработках 1950-х годов, включая Mailüfterl (1955), Цузе Z22 (1955), ЗЕБРА (1958), а Electrologica X1 (1958). В IBM ACS-1 В дизайне 1967 г. в форматах команд был выделен бит «пропуска», а в 1976 г. Гибкий процессор CDC выделил три бита условного выполнения в форматах микрокоманд.

Hewlett Packard с PA-RISC в архитектуре (1986) была функция, называемая аннулирование, что позволило основывать большинство инструкций предыдущей инструкцией. IBM с Архитектура POWER (1990) показали условные инструкции по перемещению. Преемник POWER, PowerPC (1993) отказались от этих инструкций. Корпорация цифрового оборудования с Альфа Архитектура (1992) также содержала инструкции условного перемещения. MIPS получили инструкции условного перемещения в 1994 году с версией MIPS IV; и SPARC в Версии 9 (1994) был расширен инструкциями условного перемещения как для целочисленных регистров, так и для регистров с плавающей запятой.

в Hewlett Packard /Intel IA-64 архитектура, большинство инструкций являются предполагаемыми. Предикаты хранятся в 64 специальных предикатах. регистры; и один из регистров предикатов всегда истинен, так что непредсказуемый инструкции - это просто инструкции, в основе которых лежит значение true. Использование предикации важно в реализации IA-64 конвейерная обработка программного обеспечения потому что это избавляет от необходимости писать отдельный код для прологов и эпилогов.[требуется разъяснение ]

в x86 архитектура, семейство условных инструкций перемещения (CMOV и FCMOV) были добавлены в архитектуру Intel Pentium Pro (1995) процессор. В CMOV инструкции скопировали содержимое исходного регистра в регистр назначения в зависимости от предиката, предоставленного значением регистра флага.

в ARM архитектура, исходный 32-разрядный набор инструкций предоставляет функцию, называемую условное исполнение это позволяет предиктировать большинство инструкций с помощью одного из 13 предикатов, основанных на некоторой комбинации четырех кодов условий, установленных предыдущей инструкцией. Руки Большой палец набор инструкций (1994) отказался от условного выполнения, чтобы уменьшить размер инструкций, чтобы они умещались в 16 битах, но его преемник, Большой палец-2 (2003) преодолели эту проблему с помощью специальной инструкции, которая не имеет никакого другого эффекта, кроме предоставления предикатов для следующих четырех инструкций. 64-битный набор инструкций, представленный в ARMv8-A (2011), заменил условное выполнение инструкциями условного выбора.

Немного SIMD наборы команд, такие как AVX2, могут использовать логические маска для условной загрузки / сохранения значений в память, параллельная форма условного перемещения. Эта форма предикации также используется в одна инструкция, несколько потоков Вычисления на графическом процессоре, когда вычислительное ядро ​​выполняет код ветви с невыполненным условием, но не фиксирует результаты, вычисленные в этом пути выполнения.

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

Рекомендации

  1. ^ а б c d Рик Виньярд (2000-04-26). «Предрасположенность». cs.nmsu.edu. Получено 2014-04-22.
  2. ^ Mahlke, Scott A .; Хэнк, Ричард Э .; Маккормик, Джеймс Э .; Август, Дэвид I .; Хун, Вэньмэй В. (22–24 июня 1995 г.). «Сравнение полной и частичной поддержки прогнозируемого выполнения для процессоров ILP». 22-й Международный симпозиум по компьютерной архитектуре.
  3. ^ а б Джозеф А. Фишер, Паоло Фарабоски, Клифф Янг (2004) Встроенные вычисления - подход VLIW к архитектуре, компиляторам и инструментам. Стр.172.
  4. ^ Кордес, Питер. "сборка - как выполнение вне очереди работает с условными инструкциями, например: CMOVcc в Intel или ADDNE (Добавить не равно) в ARM". Переполнение стека. В отличие от управляющих зависимостей (ветвей), они не предсказывают и не предполагают, какими будут флаги, поэтому cmovcc вместо jcc может создать цепочку зависимостей с переносом цикла и в конечном итоге оказаться хуже, чем предсказуемая ветвь. [1] является примером этого.

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