Отрасль (информатика)

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

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

Выполнение

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

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

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

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

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

Термин «ветвь» также можно использовать применительно к программам на языках программирования высокого уровня . В этих ветвях обычно принимают форму условные операторы различной формы, инкапсулирующие последовательность команд, которая будет выполнена, если условия будут выполнены. Инструкции безусловного перехода, такие как GOTO, используются для безусловного перехода к другой последовательности команд. Если алгоритм требует условного перехода, вызову GOTO (или GOSUB) предшествует оператор IF-THEN, определяющий условие(я). Все языки высокого уровня поддерживают алгоритмы, которые могут повторно использовать код в виде цикла — структуры управления, которая повторяет последовательность инструкций до тех пор, пока не будет выполнено какое-либо условие, приводящее к завершению цикла. Циклы также считаются инструкциями ветвления. На машинном уровне циклы реализованы как обычные условные переходы, перенаправляющие выполнение на повторяющийся код.

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

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

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

Примеры

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

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

состояние или результат	х86	ПДП-11, ВАКС	ARM (частично 6502)	уравнение
ноль (подразумевается равенство для sub/cmp)	Джей Зи; ЮНЗ	ЛЯГУШКА; БНЕ	ЛЯГУШКА; БНЕ	ноль; не ноль
отрицательный (N), знак (S) или минус (M)	Дж.С.; JNS	ИМТ; БПЛ	ИМТ; БПЛ	отрицательный; не отрицательный
арифметическое переполнение (флаг O или V)	ДЖО; JNO	ВХЛ; БВЦ	ВХЛ; БВЦ	перелив; не переполняться
перенос (из add, cmp,shift и т.д.)	Джей Си; JNC	БКС; BCC	БКС; BCC	нести; не нести
без знака внизу (нижний)	Джей Би	БЛО	БЛО ^*	занимать
без знака ниже или равно (ниже или одинаково)	JBE	БЛОС	БЛС ^*	брать взаймы или ноль
без знака выше или равно (выше или одинаково)	ДЖЭ	БХИ	БХС ^*	не брать взаймы
без знака выше (выше)	И	БЫТЬ	БЫТЬ ^*	не брать и не ноль
подписал менее	Дж.Л.	БЛТ	БЛТ	sign≠overflow
подписано меньше или равно	JLE	БЫТЬ	БЫТЬ	(знак≠переполнение) или ноль
подписано больше или равно	JGE	БГЭ	БГЭ	знак = переполнение
подписано больше, чем	Дж.Г.	БГТ	БГТ	(знак=переполнение), а не ноль

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

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

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

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

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

Подсказки по предсказанию ветвей

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

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

Предсказатели аппаратных ветвей

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

Код без ветвей

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

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

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

См. также

Примечания

^ По крайней мере концептуально; см . внеочередное исполнение .

Ссылки

^ Кнут, Дональд (2008). Искусство компьютерного программирования . Том. 4, Предисловие 1A (6-е изд.). стр. 48–49.
^ «Избегание ветвей» . Wiki по шахматному программированию .
^ «Криптопостоянное время» . МедведьSSL .

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

Бесплатная документация по IA-32 и x86-64 , предоставленная Intel.
Часто задаваемые вопросы по PDP-11
Набор инструкций ARM

[1] По крайней мере концептуально; см . внеочередное исполнение .

[2] Кнут, Дональд (2008). Искусство компьютерного программирования . Том. 4, Предисловие 1A (6-е изд.). стр. 48–49.

[3] «Избегание ветвей» . Wiki по шахматному программированию .

[4] «Криптопостоянное время» . МедведьSSL .

[а]

[1]

[2]

[3]