В информатике , предикации является архитектурной особенностью , которая является альтернативой условной передачи управления , реализуемый машинных команд , таких как условная ветвь , условный вызов , условное возвращение и таблиц ветвления . Предикация работает, выполняя инструкции по обоим путям ветви и разрешая только этим инструкциям по выбранному пути изменять архитектурное состояние. [1] Инструкциям по выбранному пути разрешено изменять архитектурное состояние, потому что они были связаны ( предиктированы ) спредикат , логическое значение, используемое инструкцией, чтобы контролировать, разрешено ли инструкции изменять архитектурное состояние или нет.
Проще говоря: если бит условия регистрации установлен, инструкция выполняется; если бит чистый, это не так. Поскольку содержимое регистра условий является динамическим, выполнение предикативных инструкций также является динамическим, т. Е. (Условно) определяется во время выполнения.
Векторные процессоры , некоторые ISA SIMD (такие как AVX2 и AVX-512 ]) и графические процессоры в целом интенсивно используют предикацию, применяя один бит условной маски вектора к соответствующим элементам в обрабатываемых векторных регистрах, тогда как скалярное прогнозирование в скалярном для наборов инструкций нужен только один бит предиката. Где Предикатные Маски становятся особенно мощными в векторной обработке является , если массив из УСЛОВИЯ кодов , по одному на элемент вектора, может накормить обратно в предикатные Маски, которые затем применяются для последующих инструкций Vector.
Обзор
Большинство компьютерных программ содержат условный код, который будет выполняться только при определенных условиях в зависимости от факторов, которые не могут быть определены заранее, например, в зависимости от ввода пользователя. Поскольку большинство процессоров просто выполняют следующую инструкцию в последовательности, традиционным решением является вставка инструкций ветвления, которые позволяют программе условно переходить к другому разделу кода, тем самым изменяя следующий шаг в последовательности. Этого было достаточно, пока дизайнеры не начали улучшать производительность, реализуя конвейерную обработку инструкций , метод, который замедляется ветвями. Более подробное описание возникших проблем и популярных решений см. В разделе « Предиктор ветвлений» .
К счастью, один из наиболее распространенных шаблонов кода, который обычно полагается на ветвление, имеет более элегантное решение. Рассмотрим следующий псевдокод : [1]
if условие { dosomething } else { dosomethingelse };
В системе, использующей условное ветвление, это может быть преобразовано в машинные инструкции, похожие на: [1]
ветвь - if - условие для label1 dosomethingelse ветвь - to label2 label1 : dosomething label2 : ...
При использовании предикации все возможные пути ветвления закодированы внутри, но некоторые инструкции выполняются, а другие - нет. Основная идея состоит в том, что каждая инструкция связана с предикатом (слово здесь используется аналогично его использованию в логике предиката ) и что инструкция будет выполняться только в том случае, если предикат истинен. Машинный код для приведенного выше примера с использованием предсказания может выглядеть примерно так: [1]
( состояние ) что- то ( не условие ) что-то еще
Помимо исключения ветвей, в целом требуется меньше кода при условии, что архитектура предоставляет предиктивные инструкции. Хотя в целом это не гарантирует более быстрого выполнения, оно будет, если блоки кода dosomething и dosomethingelse достаточно короткие.
Самая простая форма предсказания - это частичное предсказание , где в архитектуре есть инструкции условного перемещения или условного выбора . Команды условного перемещения записывают содержимое одного регистра поверх другого только в том случае, если значение предиката истинно, тогда как инструкции условного выбора выбирают, в какой из двух регистров содержимое записывается в третий на основе значения предиката. Более обобщенная и способная форма - полное предсказание . Полная предикация имеет набор регистров предикатов для хранения предикатов (что позволяет одновременно исключать несколько вложенных или последовательных ветвей), и большинство инструкций в архитектуре имеют поле спецификатора регистра, чтобы указать, какой регистр предиката предоставляет предикат. [2]
Преимущества
Основная цель предсказания - избежать перескоков очень маленьких участков программного кода, повысить эффективность конвейерного выполнения и избежать проблем с кешем . Он также имеет ряд более тонких преимуществ:
- Функции, которые традиционно вычисляются с использованием простых арифметических и побитовых операций, могут быть быстрее вычислены с использованием предикативных инструкций.
- Предсказанные инструкции с разными предикатами можно смешивать друг с другом и с безусловным кодом, что позволяет лучше планировать инструкции и, следовательно, даже повысить производительность.
- Устранение ненужных инструкций ветвления может ускорить выполнение необходимых ветвей, например тех, которые составляют циклы, за счет уменьшения нагрузки на механизмы прогнозирования ветвлений .
- Устранение затрат на неверное предсказание ветвления, которые могут быть высокими в архитектурах с глубоким конвейером.
- Наборы инструкций, которые имеют исчерпывающие коды условий, сгенерированные инструкциями, могут дополнительно уменьшить размер кода путем непосредственного использования регистров условий в или в качестве предсказания.
Недостатки
Главный недостаток Predication - увеличенное пространство для кодирования. В типичных реализациях каждая инструкция резервирует битовое поле для предиката, определяющего, при каких условиях эта инструкция должна действовать. Когда доступная память ограничена, как на встроенных устройствах , эта стоимость пространства может быть непомерно высокой. Однако некоторые архитектуры, такие как 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 «s PA-RISC архитектуры (1986) имела функцию под названием обнуление , что позволило большинство инструкций , которые будут основываться на предыдущей инструкции. IBM «S архитектура МОЩНОСТИ (1990) показала условные инструкции MOVE. Преемник POWER, PowerPC (1993), отказался от этих инструкций. Digital Equipment Corporation «s Альфа архитектура (1992) также показал условные команды на перемещение. MIPS получил инструкции условного перемещения в 1994 году с версией MIPS IV; а в версии 9 (1994) SPARC был расширен инструкциями условного перемещения как для целочисленных регистров, так и для регистров с плавающей запятой.
В архитектуре Hewlett-Packard / Intel IA-64 большинство инструкций является предполагаемым. Предикаты хранятся в 64 специальных регистрах предикатов ; и один из регистров предиката всегда истинен, так что непредсказуемые инструкции - это просто инструкции, предиктированные со значением "истина". Использование предсказания важно в реализации конвейерной обработки программного обеспечения в IA-64, поскольку оно позволяет избежать написания отдельного кода для прологов и эпилогов. [ требуется разъяснение ]
В архитектуре x86 семейство инструкций условного перемещения ( CMOV
и FCMOV
) было добавлено к архитектуре процессором Intel Pentium Pro (1995). В CMOV
инструкции копируется содержимое регистра источника в регистр назначения в зависимости от предиката , подаваемого на значении регистра флага.
В архитектуре ARM исходный 32-битный набор инструкций предоставляет функцию, называемую условным выполнением, которая позволяет предиктировать большинство инструкций одним из 13 предикатов, основанных на некоторой комбинации четырех кодов условий, установленных предыдущей инструкцией. Набор инструкций Thumb от ARM (1994) отказался от условного выполнения, чтобы уменьшить размер инструкций, чтобы они могли умещаться в 16 битах, но его преемник, Thumb-2 (2003), решил эту проблему, используя специальную инструкцию, которая не оказывает никакого влияния, кроме предикаты для следующих четырех инструкций. 64-битный набор инструкций, представленный в ARMv8-A (2011), заменил условное выполнение инструкциями условного выбора.
SIMD, SIMT и Vector Predication
Некоторые наборы инструкций SIMD , такие как AVX2, имеют возможность использовать логическую маску для условной загрузки / сохранения значений в память, параллельная форма условного перемещения. Эта форма предсказания также используется в векторных процессорах и вычислениях на графическом процессоре с одной инструкцией и несколькими потоками . Все приемы, преимущества и недостатки одиночного скалярного предсказания также применимы к случаю параллельной обработки.
Смотрите также
- Предиктор ветвления
- Поток управления
- Слот задержки
- Параллелизм на уровне инструкций
- Оптимизирующий компилятор
- Срыв трубопровода
- Конвейерная обработка программного обеспечения
- Спекулятивное исполнение
- Векторный процессор
- Очень длинное командное слово
Рекомендации
- ^ a b c d Рик Виньярд (26 апреля 2000). «Предсказание» . cs.nmsu.edu . Проверено 22 апреля 2014 .
- ^ Mahlke, Scott A .; Хэнк, Ричард Э .; Маккормик, Джеймс Э .; Август, Давид I; Хун, Вэньмэй В. (22–24 июня 1995 г.). «Сравнение полной и частичной поддержки прогнозируемого выполнения для процессоров ILP». 22-й Международный симпозиум по компьютерной архитектуре .
- ^ а б Джозеф А. Фишер, Паоло Фарабоски, Клифф Янг (2004) Встроенные вычисления - подход VLIW к архитектуре, компиляторам и инструментам . Стр.172.
- ^ Кордес, Питер. «сборка - как выполнение вне очереди работает с условными инструкциями, например: CMOVcc в Intel или ADDNE (Добавить не равно) в ARM» . Переполнение стека .
В отличие от управляющих зависимостей (ветвей), они не предсказывают и не предполагают, какими будут флаги, поэтому cmovcc вместо jcc может создать цепочку зависимостей с переносом цикла и в конечном итоге оказаться хуже, чем предсказуемая ветвь. [1] является примером этого.
дальнейшее чтение
- Клементс, Алан (2013). Компьютерная организация и архитектура: темы и вариации . Cengage Learning. С. 532–539. ISBN 1-285-41542-6.