В архитектуре компьютера предикация — это функция, которая предоставляет альтернативу условной передаче управления , реализованную с помощью машинных инструкций условного перехода . Предикация работает, имея условные ( предикативные ) инструкции без перехода, связанные с предикатом , логическим значением , используемым инструкцией для управления тем, разрешено ли инструкции изменять архитектурное состояние или нет. Если предикат, указанный в инструкции, является истинным, инструкция изменяет архитектурное состояние; в противном случае архитектурное состояние остается неизменным. Например, предикативная инструкция перемещения (условный ход) изменит место назначения только в том случае, если предикат является истинным. Таким образом, вместо использования условного перехода для выбора инструкции или последовательности инструкций для выполнения на основе предиката, который контролирует, происходит ли переход, инструкции, которые должны быть выполнены, связаны с этим предикатом, так что они будут выполнены или не выполнены в зависимости от того, является ли этот предикат истинным или ложным. [1]
Векторные процессоры , некоторые SIMD ISA (такие как AVX2 и AVX-512 ) и графические процессоры в целом интенсивно используют предикацию, применяя один бит вектора условной маски к соответствующим элементам в обрабатываемых векторных регистрах, тогда как скалярная предикация в наборах скалярных инструкций требует только одного бита предиката. Где предикатные маски становятся особенно мощными в векторной обработке, так это если массив кодов условий , по одному на элемент вектора, может возвращаться в предикатные маски, которые затем применяются к последующим векторным инструкциям.
Большинство компьютерных программ содержат условный код, который будет выполняться только при определенных условиях в зависимости от факторов, которые нельзя определить заранее, например, в зависимости от ввода пользователя. Поскольку большинство процессоров просто выполняют следующую инструкцию в последовательности, традиционным решением является вставка инструкций ветвления , которые позволяют программе условно перейти к другому разделу кода, тем самым изменяя следующий шаг в последовательности. Этого было достаточно, пока разработчики не начали повышать производительность, внедряя конвейеризацию инструкций , метод, который замедляется ветвлениями. Для более подробного описания возникших проблем и популярного решения см. branch predictor .
К счастью, один из наиболее распространенных шаблонов кода, который обычно полагается на ветвление, имеет более элегантное решение. Рассмотрим следующий псевдокод : [1]
если условие { сделать_что-то } иначе { сделать_что-то_еще } В системе, использующей условное ветвление, это может привести к машинным инструкциям, выглядящим примерно так: [1]
branch_if_condition_to label1 do_something_else branch_always_to label2 label1 : do_something label2 : ... С предикацией все возможные пути ветвления кодируются в строке, но некоторые инструкции выполняются, а другие нет. Основная идея заключается в том, что каждая инструкция связана с предикатом (слово здесь используется аналогично его использованию в логике предикатов ) и что инструкция будет выполнена только в том случае, если предикат истинен. Машинный код для приведенного выше примера с использованием предикации может выглядеть примерно так: [1]
( условие ) сделать_что-то ( не условие ) сделать_что-то_еще Помимо устранения ветвей, требуется меньше кода в целом, при условии, что архитектура предоставляет предикативные инструкции. Хотя это не гарантирует более быстрого выполнения в целом, это будет так, если блоки кода do_somethingи достаточно короткие.do_something_else
Простейшей формой предикации является частичная предикация , где архитектура имеет инструкции условного перемещения или условного выбора . Инструкции условного перемещения записывают содержимое одного регистра поверх другого, только если значение предиката истинно, тогда как инструкции условного выбора выбирают, содержимое какого из двух регистров будет записано в третий, на основе значения предиката. Более обобщенная и эффективная форма — полная предикация . Полная предикация имеет набор регистров предикатов для хранения предикатов (что позволяет одновременно исключать несколько вложенных или последовательных ветвей), и большинство инструкций в архитектуре имеют поле спецификатора регистра для указания того, какой регистр предиката предоставляет предикат. [2]
Основная цель предикации — избежать переходов через очень маленькие разделы программного кода, повышая эффективность конвейерного выполнения и избегая проблем с кэшем . Она также имеет ряд более тонких преимуществ:
Основной недостаток предикации заключается в увеличенном пространстве кодирования. В типичных реализациях каждая инструкция резервирует битовое поле для предиката, определяя, при каких условиях эта инструкция должна иметь эффект. Когда доступная память ограничена, как на встроенных устройствах , эта стоимость пространства может быть непомерно высокой. Однако некоторые архитектуры, такие как Thumb-2, способны избежать этой проблемы (см. ниже). Другие недостатки следующие: [3]
Предикация наиболее эффективна, когда пути сбалансированы или когда самый длинный путь выполняется чаще всего, [3] но определить такой путь во время компиляции очень сложно, даже при наличии информации профилирования .
Предикативные инструкции были популярны в европейских компьютерных проектах 1950-х годов, включая Mailüfterl (1955), Zuse Z22 (1955), ZEBRA (1958) и Electrologica X1 (1958). Проект IBM ACS-1 1967 года выделил бит «пропуска» в своих форматах инструкций, а CDC Flexible Processor в 1976 году выделил три бита условного выполнения в своих форматах микроинструкций.
Архитектура PA-RISC компании Hewlett-Packard (1986) имела функцию, называемую обнулением , которая позволяла большинству инструкций предицироваться предыдущей инструкцией. Архитектура POWER компании IBM (1990) включала инструкции условного перемещения. Преемник POWER, PowerPC (1993), отказался от этих инструкций. Архитектура Alpha компании Digital Equipment Corporation (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 , такие как AVX2, имеют возможность использовать логическую маску для условной загрузки/хранения значений в памяти, параллельную форму условного перемещения, а также могут применять отдельные биты маски к отдельным арифметическим блокам, выполняющим параллельную операцию. Этот метод известен в таксономии Флинна как «ассоциативная обработка» .
Эта форма предикации также используется в векторных процессорах и вычислениях на GPU с одной инструкцией и несколькими потоками . Все методы, преимущества и недостатки одиночной скалярной предикации применимы также и к случаю параллельной обработки.
В отличие от зависимостей управления (ветвей), они не предсказывают и не предполагают, какими будут флаги, поэтому cmovcc вместо jcc может создать цепочку зависимостей, переносимых циклом, и в конечном итоге оказаться хуже, чем предсказуемая ветвь. Флаг оптимизации gcc -O3 делает код медленнее, чем -O2, является примером этого.
{{cite web}}: Внешняя ссылка в |quote=