Войти
В информатике предикация - это архитектурная функция, которая обеспечивает альтернативу условной передаче управления, реализованный машинными инструкциями, такими как условное ветвление, условный вызов, условный возврат и таблицы ветвлений. Предикация работает, выполняя инструкции по обоим путям ветви и разрешая только этим инструкциям по выбранному пути изменять архитектурное состояние. Инструкциям из взятого пути разрешено изменять архитектурное состояние, потому что они были связаны (предиктированы) с предикатом, логическим значением , используемым инструкцией для управления, разрешено ли инструкции изменять архитектурное состояние или не.
Большинство компьютерных программ содержат условный код, который будет выполняться только при определенных условиях в зависимости от факторов, которые не могут быть определены заранее, например, в зависимости от ввода пользователя. Поскольку большинство процессоров просто выполняют следующую команду в последовательности, традиционным решением является вставка инструкций ветвления, которые позволяют программе условно перейти к другому разделу кода, тем самым изменяя следующий шаг в последовательности. Этого было достаточно, пока разработчики не начали улучшать производительность за счет реализации конвейерной обработки инструкций, метода, который замедляется ветвлениями. Для более подробного описания возникших проблем и популярного решения см. предсказатель ветвления.
К счастью, один из наиболее распространенных шаблонов кода, который обычно полагается на ветвление, имеет более элегантное решение. Рассмотрим следующий псевдокод :
if condition {dosomething} else {dosomethingelse};В системе, которая использует условное ветвление, это может быть преобразовано в машинные инструкции, похожие на:
переход-если-условие в метку1 дошло-до метки2 метка1: дошло-метка2:...
При предикации все возможные пути ветвления закодированы внутри, но некоторые инструкции выполняются, а другие нет. Основная идея состоит в том, что каждая инструкция связана с предикатом (слово здесь используется аналогично его использованию в логике предиката ) и что инструкция будет выполняться только в том случае, если предикат истинен. Машинный код для приведенного выше примера с использованием предикации может выглядеть примерно так:
(условие) dosomething (не условие) dosomethingelse
Помимо исключения ветвей, требуется меньше кода в целом, при условии, что архитектура предоставляет предикативные инструкции. Хотя в целом это не гарантирует более быстрого выполнения, оно будет, если блоки кода dosomethingи dosomethingelseдостаточно короткие.
Самая простая форма предсказания - это частичное предсказание, когда в архитектуре есть условные инструкции перемещения или условного выбора. Команды условного перемещения записывают содержимое одного регистра поверх другого только в том случае, если значение предиката истинно, тогда как инструкции условного выбора выбирают, в какой из двух регистров содержимое записывается в третий на основе значения предиката. Более обобщенная и способная форма - полное предсказание. Полная предикация имеет набор регистров предикатов для хранения предикатов (что позволяет одновременно исключать несколько вложенных или последовательных ветвей), и большинство инструкций в архитектуре имеют поле спецификатора регистра, чтобы указать, какой регистр предиката предоставляет предикат.
Основная цель предсказания - избежать переходов через очень небольшие участки программного кода, повысить эффективность конвейерного выполнения и избежать проблем с кешем. Он также имеет ряд более тонких преимуществ:
Главный недостаток предикатности - увеличенное пространство кодирования. В типичных реализациях каждая инструкция резервирует битовое поле для предиката, определяющего, при каких условиях эта инструкция должна действовать. Когда доступная память ограничена, как на встроенных устройствах, эта стоимость пространства может быть непомерно высокой. Однако некоторые архитектуры, такие как Thumb-2, позволяют избежать этой проблемы (см. Ниже). Другие недостатки следующие:
Предсказание наиболее эффективно, когда пути сбалансированы или когда наиболее длинный путь выполняется наиболее часто, но определение такого пути очень сложно во время компиляции, даже при наличии профилирующей информации.
Предусмотренные инструкции были популярны в европейских компьютерных разработках 1950-х годов, включая Mailüfterl (1955), Zuse Z22 (1955), ZEBRA (1958) и Electrologica X1 (1958). В конструкции IBM ACS-1 1967 г. в форматах команд был выделен бит «пропуска», а в 1976 г. Гибкий процессор CDC выделил три бита условного выполнения в форматах микрокоманд.
Архитектура PA-RISC компании Hewlett-Packard (1986) имела функцию, называемую аннулированием, которая позволяла предиктировать большинство инструкций предыдущей инструкцией. Архитектура POWER (1990) IBM (1990) содержала инструкции условного перемещения. Преемник POWER, PowerPC (1993), отказался от этих инструкций. Архитектура Alpha компании Digital Equipment Corporation (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 предикатов, основанных на некоторой комбинации четыре кода состояния, установленные предыдущей инструкцией. Набор инструкций ARM Thumb (1994) отказался от условного выполнения, чтобы уменьшить размер инструкций, чтобы они умещались в 16 битах, но его преемник Thumb-2 (2003) преодолел эту проблему, с помощью специальной инструкции, которая не имеет никакого другого эффекта, кроме как предоставить предикаты для следующих четырех инструкций. 64-битный набор инструкций, представленный в ARMv8-A (2011), заменил условное выполнение инструкциями условного выбора.
Некоторые наборы инструкций SIMD, например AVX2, имеют возможность использовать логическую маску для условной загрузки / сохранения значений в память, параллельная форма условного перемещения. Эта форма предсказания также используется в вычислениях с одной инструкцией, несколькими потоками GPU, где вычислительное ядро выполняет код ветви с неудовлетворенным условием, но не фиксирует результаты, вычисленные в этом пути выполнения.
