Отрасль (информатика) - Branch (computer science)

Филиал является инструкцией в компьютерной программе , которая может вызвать компьютер , чтобы начать выполнение другой последовательности команд и , таким образом , отклоняться от своего поведения выполнения команд в порядке по умолчанию. Отделение (или разветвлений , разветвленный ) может также относиться к акту переключения исполнения в другую последовательность команд, в результате выполнения команды перехода. Инструкции ветвления используются для реализации потока управления в программных циклах и условных выражениях (т. Е. Выполнение определенной последовательности инструкций только при соблюдении определенных условий).

Инструкция ветвления может быть либо безусловным ветвлением , которое всегда приводит к ветвлению, либо условным ветвлением , которое может или не может вызывать ветвление в зависимости от некоторого условия. Кроме того, в зависимости от того, как он определяет адрес новой последовательности инструкций («целевой» адрес), инструкция ветвления обычно классифицируется как прямая , косвенная или относительная , что означает, что инструкция содержит целевой адрес или указывает, где находится целевой адрес должен быть найден (например, регистр или место в памяти), или он определяет разницу между текущим и целевым адресами.

Реализация

Механически команда перехода может изменить счетчик программ (ПК) ЦП . Счетчик программ хранит адрес памяти следующей инструкции, которая должна быть выполнена. Следовательно, ветвь может заставить ЦП начать выборку своих инструкций из другой последовательности ячеек памяти.

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

Когда ветвь принимаются , счетчик программы КП устанавливаются на аргумент инструкции перехода. Таким образом, следующая инструкция становится инструкцией по этому адресу в памяти . Следовательно, поток управления меняется.

Когда ветвь не занята , счетчик программы ЦП не изменяется. Следовательно, следующая выполняемая инструкция - это инструкция после инструкции ветвления. Следовательно, поток управления не изменился.

Термин ветвь может использоваться при ссылке на программы на языках высокого уровня, а также на программы, написанные на машинном коде или языке ассемблера . В языках программирования высокого уровня ветви обычно принимают форму условных операторов различных форм, которые инкапсулируют последовательность команд, которая будет выполняться, если условия удовлетворены. Инструкции безусловного перехода, такие как GOTO , используются для безусловного «перехода» к другой последовательности команд (начала выполнения).

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

Существуют также машины (или конкретные инструкции), где условие может быть проверено самой инструкцией перехода, например, ветвь <метка>, если регистр X отрицательный . В простых компьютерных схемах ветви сравнения выполняют больше арифметических операций и могут потреблять больше энергии, чем ветви регистров флагов. В быстрых компьютерных проектах ветви сравнения могут работать быстрее, чем ветви регистров флагов, потому что ветви сравнения могут обращаться к регистрам с большим параллелизмом, используя те же механизмы процессора, что и вычисления.

Некоторые ранние и простые архитектуры ЦП, все еще встречающиеся в микроконтроллерах, могут не реализовывать условный переход, а только условную операцию «пропустить следующую инструкцию». Таким образом, условный переход или вызов реализуется как условный пропуск инструкции безусловного перехода или вызова.

Примеры

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

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

состояние или результат x86 ПДП-11, ВАКС ARM (частично 6502) уравнение
ноль (подразумевает равное для sub / cmp) JZ; JNZ БЫТЬ Q; BNE БЫТЬ Q; BNE нуль; не ноль
отрицательный (N), знак (S) или минус (M) JS; JNS ИМТ; BPL ИМТ; BPL отрицательный; не отрицательный
арифметическое переполнение (флаг называется O или V) ДЖО; JNO БВС; BVC БВС; BVC перелив; не переполняться
перенос (от add, cmp, shift и т. д.) JC; JNC BCS; BCC BCS; BCC нести; не носить
беззнаковый снизу (нижний) JB BLO BLO * одолжить
без знака ниже или равно (ниже или равно) JBE BLOS BLS * одолжить или ноль
беззнаковый выше или равный (выше или такой же) JAE BHIS BHS * не брать в долг
беззнаковый выше (выше) JA BHI BHI * не брать и не ноль
подписано меньше чем JL BLT BLT знак ≠ переполнение
со знаком меньше или равно JLE BLE BLE (знак ≠ переполнение) или ноль
со знаком больше или равно JGE BGE BGE знак = переполнение
подписано больше чем JG BGT BGT (знак = переполнение), а не ноль

* x86, PDP-11, VAX и некоторые другие устанавливают флаг переноса, чтобы сигнализировать о заимствовании, и сбрасывают флаг переноса, чтобы сигнализировать об отсутствии заимствования . ARM, 6502 , PIC и некоторые другие делают противоположное для операций вычитания. Эта инвертированная функция флага переноса для определенных инструкций отмечена ( * ), то есть заимствовать = не переносить в некоторых частях таблицы, но, если не указано иное, заимствовать≡ переносить. Однако аддитивные операции продолжения обрабатываются одинаково в большинстве архитектур.

Проблемы с производительностью с инструкциями веток

Для достижения высокой производительности современные процессоры конвейерные . Они состоят из нескольких частей, каждая из которых частично обрабатывает инструкцию, передает свои результаты следующему этапу конвейера и начинает работу над следующей инструкцией в программе. Этот дизайн предполагает, что инструкции будут выполняться в определенной неизменной последовательности. Инструкции условного перехода делают невозможным знание этой последовательности. Таким образом, условные переходы могут вызывать «сбои», при которых конвейер должен быть перезапущен в другой части программы.

Повышение производительности за счет сокращения киосков в филиалах

Некоторые методы повышают скорость за счет уменьшения задержек из условных ветвей.

Подсказки предсказания ветвления

Исторически прогнозирование ветвлений основывалось на статистических данных и использовало результат для оптимизации кода. Программист скомпилирует тестовую версию программы и запустит ее с тестовыми данными. В тестовом коде подсчитывалось, как на самом деле были взяты ветки. Статистические данные из тестового кода затем использовались компилятором для оптимизации ветвей выпущенного кода. Оптимизация будет обеспечивать, чтобы самое быстрое направление ветвления (принятое или нет) всегда было наиболее часто используемым путем потока управления. Чтобы разрешить это, процессоры должны быть спроектированы с (или, по крайней мере, иметь) предсказуемую синхронизацию ветвления. Некоторые процессоры имеют наборы инструкций (например, Power ISA ), которые были разработаны с использованием «подсказок ветвлений», чтобы компилятор мог сообщить процессору, как следует выполнять каждую ветвь.

Проблема с прогнозированием ветвления программного обеспечения заключается в том, что он требует сложного процесса разработки программного обеспечения.

Предикторы аппаратного перехода

Для запуска любого программного обеспечения предикторы аппаратных ветвей переместили статистику в электронику. Предикторы перехода - это части процессора, которые угадывают результат условного перехода. Затем логика процессора делает ставку на предположение, начиная выполнять ожидаемый поток инструкций. Пример простой схемы аппаратного прогнозирования ветвлений - это предположить, что все обратные ветки (то есть к меньшему счетчику программ) принимаются (потому что они являются частью цикла), а все прямые ветки (к большему счетчику программ) не берутся. (потому что они оставляют петлю). Лучшие предикторы ветвления разрабатываются и проверяются статистически путем их моделирования в различных тестовых программах. Хорошие предикторы обычно подсчитывают результаты предыдущих выполнений ветки. Тогда более быстрые и дорогие компьютеры могут работать быстрее, если вложить средства в лучшую электронику для прогнозирования ветвлений. В ЦП с аппаратным предсказанием ветвления подсказки ветвлений позволяют предположительно лучшему предсказанию ветвления компилятора перекрывать более упрощенное аппаратное предсказание ветвления.

Безотказный код

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

Слот задержки

Другой способ - слот задержки перехода . В этом подходе всегда выполняется одна инструкция после перехода. Следовательно, компьютер может использовать эту инструкцию для выполнения полезной работы независимо от того, остановился ли его конвейер. Этот подход был исторически популярен в компьютерах RISC . В семействе совместимых процессоров он усложняет многоцикловые процессоры (без конвейера), более быстрые процессоры с более длинными, чем ожидалось, конвейерами и суперскалярные процессоры (которые могут выполнять инструкции не по порядку).

Смотрите также

Примечания

использованная литература

внешние ссылки