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

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

Векторные процессоры , некоторые SIMD ISA (такие как AVX2 и AVX-512 ) и графические процессоры в целом интенсивно используют предикацию, применяя один бит вектора условной маски к соответствующим элементам в обрабатываемых векторных регистрах, тогда как скалярная предикация в скалярных инструкциях наборам нужен только один бит предиката. Маски предикатов становятся особенно эффективными при векторной обработке , если массив кодов условий , по одному на элемент вектора, может возвращаться в маски предикатов, которые затем применяются к последующим векторным инструкциям.

Обзор

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

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

if condition
    {dosomething}
else
    {dosomethingelse}

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

branch-if-condition to label1
dosomethingelse
branch-to label2
label1:
dosomething
label2:
...

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

(condition) dosomething
(not condition) dosomethingelse

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

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

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

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

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

Недостатки

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

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

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

История

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

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

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

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

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

SIMD, SIMT и векторное предсказание

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

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Рик Виньярд (26 апреля 2000 г.). «Предсказание» . cs.nmsu.edu . Архивировано из оригинала 20 апреля 2015 года . Проверено 22 апреля 2014 г.
^ Мальке, Скотт А.; Хэнк, Ричард Э.; Маккормик, Джеймс Э.; Август, Дэвид И.; Хун, Вэнь-мэй В. (1995). Сравнение полной и частичной поддержки предикатного выполнения для процессоров ILP . 22-й Международный симпозиум по компьютерной архитектуре, 22–24 июня 1995 г. CiteSeerX 10.1.1.19.3187 . дои : 10.1145/223982.225965 . ISBN 0-89791-698-0 .
^ Jump up to: ^а ^б Фишер, Джозеф А.; Фарабоски, Паоло; Янг, Клифф (2004). «4.5.2 Предикация § Предикация во встроенной области» . Встроенные вычисления — подход VLIW к архитектуре, компиляторам и инструментам . Эльзевир. п. 172. ИСБН 9780080477541 .
^ Кордес, Питер. «сборка — как выполнение внеочередного выполнения работает с условными инструкциями, например: CMOVcc в Intel или ADDNE (добавить не равно) в ARM» . Переполнение стека . В отличие от зависимостей управления (ветвей), они не предсказывают и не предполагают, какими будут флаги, поэтому cmovcc вместо jcc может создать цепочку зависимостей с циклическим переносом и в конечном итоге оказаться хуже, чем предсказуемая ветвь. Флаг оптимизации gcc -O3 делает код медленнее, чем -O2, является примером этого. {{cite web}}: Внешняя ссылка в |quote= ( помощь )

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

Клементс, Алан (2013). «8.3.7 Предикация» . Компьютерная организация и архитектура: темы и вариации . Cengage Обучение. стр. 532–9. ISBN 978-1-285-41542-0 .

[rvinyard-1] Jump up to: ^а ^б ^с ^д Рик Виньярд (26 апреля 2000 г.). «Предсказание» . cs.nmsu.edu . Архивировано из оригинала 20 апреля 2015 года . Проверено 22 апреля 2014 г.

[2] Мальке, Скотт А.; Хэнк, Ричард Э.; Маккормик, Джеймс Э.; Август, Дэвид И.; Хун, Вэнь-мэй В. (1995). Сравнение полной и частичной поддержки предикатного выполнения для процессоров ILP . 22-й Международный симпозиум по компьютерной архитектуре, 22–24 июня 1995 г. CiteSeerX 10.1.1.19.3187 . дои : 10.1145/223982.225965 . ISBN 0-89791-698-0 .

[Fisher04-3] Jump up to: ^а ^б Фишер, Джозеф А.; Фарабоски, Паоло; Янг, Клифф (2004). «4.5.2 Предикация § Предикация во встроенной области» . Встроенные вычисления — подход VLIW к архитектуре, компиляторам и инструментам . Эльзевир. п. 172. ИСБН 9780080477541 .

[4] Кордес, Питер. «сборка — как выполнение внеочередного выполнения работает с условными инструкциями, например: CMOVcc в Intel или ADDNE (добавить не равно) в ARM» . Переполнение стека . В отличие от зависимостей управления (ветвей), они не предсказывают и не предполагают, какими будут флаги, поэтому cmovcc вместо jcc может создать цепочку зависимостей с циклическим переносом и в конечном итоге оказаться хуже, чем предсказуемая ветвь. Флаг оптимизации gcc -O3 делает код медленнее, чем -O2, является примером этого. {{cite web}}: Внешняя ссылка в |quote= ( помощь )

[1]

[2]

[3]

[4]