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

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

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

Обзор [ править ]

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

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

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

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

ветка  -  если  -  условие   для   метки1 
 сделать что-нибудьельсе 
 ветка  -  для   метки2 
 метка1  : 
 сделать что-нибудь 
 метка2  : 
 ...

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

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

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

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

Преимущества [ править ]

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

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

Недостатки [ править ]

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

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

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

История [ править ]

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

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, имеют возможность использовать логическую маску для условной загрузки/сохранения значений в памяти, параллельную форму условного перемещения, а также могут применять отдельные биты маски к отдельным арифметическим единицам, выполняющим параллельную операцию. Этот метод известен в таксономии Флинна как «ассоциативная обработка» .

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

См. также [ править ]

Ссылки [ править ]

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

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

[1]

[2]

[3]

[4]