Введение

Формы условных операторов в компьютерном программировании

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

Обзор

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

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

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

Недостатки

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

История

Предсказуемые инструкции были популярны в европейских компьютерных конструкциях 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) имела функцию, называемую аннулированием, которая позволяла большинству инструкций зависеть от предыдущей инструкции. Архитектура IBM POWER (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 предикатов, основанных на некоторой комбинации четырех кодов состояния, установленных предыдущей инструкцией. Набор инструкций Thumb (1994) отказался от условного выполнения, чтобы уменьшить размер инструкций и обеспечить их размещение в 16 битах, но его преемник Thumb 2 (2003) решил эту проблему, используя специальную инструкцию, которая не имеет никакого эффекта, кроме как предоставлять предикаты для следующих четырех инструкций. 64-битный набор инструкций, представленный в ARMv8 A (2011), заменил условное выполнение инструкциями условного выбора.

SIMD, SIMT и векторная предикация

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