(i к циклах. Следствием этого изъяна явлется то, что инсфукция перехода, которая большую цасть времени не выполняется, может иметь в фи раза больше неправильных предсказаний, qeM инсфукция перехода, которая большую часть времени выполняется.

Можно принимать эту ассимефичность в расчет, организовав ветви так, чтобы они qaoie выполнялись, а не пропускались. Пример консфукции if-then-else:

А: Е:

TEST ЕАХ,ЕАХ JZ А

<ветвь 1> JMP Е

<ветвь 2>

Если ветвь 1 выполняется чаще, чем ветвь 2, а последняя выполняется реже в два раза, тогда можно снизить количество неправильных предсказаний, поменяв две ветви так, чтобы инсфукция перехода выполнялась чаще, чем пропускалась:

А: Е:

TEST ЕАХ,ЕАХ JNZ А <ветвь 2> JMP Е

<ветвь 1>

(Это противоречит рекомендациям Intel).

Тем не менее, есть причины чаще помечать выполняющуюся ветвь первой:

помещение редко используемых ветвей подальше от основного кода делает использование кода кэша более оптимальным;

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

инсфукция перехода будет предсказана как не выполняющаяся, если она была вытеснена другими инсфукциями из ВТВ;

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

производилась ближе к его концу:

MOV ЕСХ, [N] L: MOV [EDI],EAX

ADD EDI,4 DEC ECX JNZ L

Если N велико, тогда инсфукция Ж2 будет чаще выполняться, чем пропускаться.

6.22.1. Предсказывание переходов в Р1

Механизм предсказывания переходов в Р1 очень отличается от того, как это реализовано в в последующих поколениях процессоров. Информация, найденная по этой теме в документах от Intel и других источниках противоречива.

У Р1 есть буфер переходов ВТВ, который может содержать информацию о 256 инструк-циях перехода. ВТВ организован в виде 4-направленного множественно-ассоциативного кэша по 64 элемента в каждом направлении. Это означает, что ВТВ может содержать не больше чем 4 элемента для каждого set-значения. Как выбирается конкретное set-значение будет обь-яснено позже. Каждый элемент ВТВ хранит адрес, куда должен быть совершен переход и состояние предсказания, которое может иметь три разных значения:

состояние 0: "не будет осуществлен"

состояние 1: "возможно не будет осуществлен"

состояние 2: "возможно будет осуществлен"

состояние 3: "будет осуществлен"

Инструкция перехода будет осуществлена, когда состояние ВТВ равно 2 или 3. и пропускается при состоянии О или 1. Состояние перехода работает как двухбитный счетчик, поэтому состояние увеличивается на 1, если переход был осуществлен, и уменьшается на 1, если этого не произошло. Понижение и повышение значения происходит по принципу "насыщения", т. е. значение не может понизиться ниже О (и стать 3) и не может повыситься выше 3 (и стать 0). По идее, все это должно привести к довольно хорошему проценту правильных предсказаний, потому что до того, как будет изменено предсказание, инструкция перехода должна быть выполнена два раза.

Тем не менее, этот механизм может быть скомпрометирован тем, что состояние О также означает "неиспользованный элемент ВТВ". Поэтому элемент ВТВ с состоянием О означает примерно то же, что если бы его вообще не было. Это имеет смысл, потом} что если у инструкции перехода нет соответствующего элемента ВТВ, предсказывается, что она не будет осуществлена. Это улучшает использование ВТВ, так как инструкция перехода, которая редко осуществляется, большую часть времени не будет занимать никакого элемента ВТВ.

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

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

Представим ситуацию, когда инструкция перехода выполняется каждый второй ра; В первый раз она попадает в ВТВ с состоянием 3, а затем будет колебаться меясд. состояниями 2 и 3. Каждый раз будет предсказываться, что она выполниться, но только 50% этих предсказаний будет верными. Теперь предположим, что однажды она отклонилась от привычного поведения и была пропущена. После этого происществия элемент ВТВ будет колебаться между состояниями 1 и 2, что будет давать 100% неправильных предсказаний. И так будет продолжаться, пока не случиться еще одно отклонение. Это худщее, что может произойти в работе этого механизма предсказания переходов.

6.22.1.2. ВТВ смотрит вперед (Р1). Механизм ВТВ подсчитывает инструкции попарно, а не по отдельности, поэтому нужно знать, как инструкции спариваются, чтобы суметь проанализировать, где хранится элемент ВТВ. Элемент ВТВ для любой управляющей инструкции присоединяется к адресу инструкции в U-конвейере из предыдущей пары инструкций (неспариваемая инструкция идет за одну пару).

SHR ЕАХ,1 MOV ЕВХ, [ESI ] СМР ЕАХ,ЕВХ

JB L

Здесь SHR спаривается с MOV, а СМР спаривается с JB. ВТВ-элемент для JB L присоединяется к адресу инструкции SHR ЕАХ, Г. Когда встречается этот ВТВ-элемент, и он находится в состоянии 2 или 3, Р1 считает целевой адрес из элемента ВТВ и загрузит инструкции, следующие за L в конвейер. Это произойдет до того, как будет декодирована инструкция перехода, поэтому Р1 полагается исключительно на информацию, содержащуюся в ВТВ, когда делает это.

Как известно, инструкции редко спариваются с первого раза (см. разд. 6.8). До того пока инструкции не спарились, элемент ВТВ будет присоединен к адресу инструкции СМР. Тем не менее, в больщинстве случаев Р1 достаточно умен, чтобы не выполнять элемент ВТВ при неиспользованной возможности спаривания, поэтому ВТВ-элемент сформируется только при втором выполнении, а следовательно, предсказания начнутся только с третьего. Лищь в случае, когда каждая вторая инструкция будет иметь размер в один байт, элемент ВТВ может сформироваться уже при первом выполнении, и окажется недествительным при втором, но так как инструкция, к которой был присоединен элемент, попадет в V-конвейер, она будет проигнорирована не вызовет особых потерь. Элемент ВТВ считывается только тогда, когда он присоединен к адресу инструкции для U-конвейера.

ВТВ-элемент идентифицируется своим set-значением, которое соответствует битам 0-5 адреса, к которому он присоединен. Биты 6-31 сохраняются в ВТВ как тег. Адреса-которые кратны 64 байтам, будут иметь одно и то же set-значение. Можно располагать не более четырех ВТВ-элементов с одинаковым set-значением. Если требуется пров рить, не будет ли ваща инструкция перехода конфликтовать с другой инструкции за один и тот же элемент ВТВ, необходимо сравнить биты 0-5 адресов инструкций, на-

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

6.22.1.3. Последовательные ветви (Р1). Когда переход пресдказан неправилы вейер очищается. Если следующая пара инструкций также содержит управляющу рукцию, то Р1 не будет загружать ее, так как он не может этого сделать, пока к( не очищен. В результате вторая инструкция предсказывается как невыполняюща зависимости от состояния элемента ВТВ. Поэтому, если второй переход также bi ется на самом деле, то результат - дополнительные потери. Состояние ВТВ-элеме второго перехода будет, тем не менее, правильно установлено. Если есть длиная i инструкций передачи управления, и первый переход в цепочке был предсказан ВИЛЬНО, тогда конвейер будет постоянно очищаться и предсказания будут noi неправильными, пока не будет встречена пара инструкций, в которой не будет пе Самый экстремальный случай подобного рода - это цикл, в котором происходят при каждой итерации из-за постоянного неправильного предсказания.

Это не единственная проблема с последовательными управляющими инстру! Другая проблема состоит в том, что может быть другая управляющая инструкцш ВТВ-элементом и управляющей инструкцией, принадлежащей ему. Если перва рукция производит переход, то могут произойти странные вещи. Рассмотрим еле; пример

SHR ЕАХ,1 MOV ЕВХ,[ESI] СМР ЕАХ,ЕВХ L1

L1 :

JB JMP L2

MOV ЕАХ,ЕВХ INC ЕВХ

Когда JB ЬГ пропускается, элемент ВТВ присоединяется к адресу СМР ЕА Но что случится, если JB Ы будет выполнена? В тот момент когда считываете элемент для JMP L2, процессор не знает, что следующая пара инструкций не сс команду перехода, поэтому он фактически предскажет, что пара инструкци! ЕАХ,ЕВХ / INC ЕВХ перейдет на L2. Потери, связанные с предсказанием инст не являющихся командами перехода, равны 3 тактам. Элемент ВТВ для JMP L2 i свое состояние на один, потому что он должен соверщать перхода. Если перей тогда состояние элемента ВТВ для JMP L2 будет понижежено до 1 и О, поэтому проблема исчезнет, пока снова не будет выполнено JMP L2.

Потери при предсказании инструкций, не являющихся управляющими, случаютс; тогда, когда предсказавыется переход на L1. В случае если выполнение JB LP npej ошибочно, тогда конвейер очищается и неверной зафузки цепочки L2 не случится, i

случае потеря от предсказания неуправляющих инструкщш как выполняющихся будет несу щественна, но состояние элемента ВТВ для JMP L2 будет понижено.

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

Теперь прорезюмируем возможные проблемы, к которым могут привести последова. тельные переходы:

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

элемент ВТВ может быть присоединен не к инструкции перехода и предсказать их как выполняющиеся;

второе последствие выщеизложенного - неправильно присоединенный элемент ВТВ будет понижать свое состояние, что может привести к последующему неправильном} предсказанию перехода, к которому он принадлежит. Даже безусловные переходы из-за этого могут быть предсказанны как невыполняющиеся;

две инструкции перехода могут использовать один и тот же элемент ВТВ, что может привести к предсказанию неправильной цели.

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

Рассмотрим еще один показательный пример:

Ha первый взгляд, как будто все в порядке: вызов функции, цикл, который пропускается, если счетчик равняется нулю, и другой вызов функциии. Какие проблемы могут возникнуть?

Сначала можно заметить, что функция Р вызывается из двух различных мест кода-Это означает, что цель возврата из Р будет все время меняться. Соответственно, возврат из Р будет все время предсказываться неправильно.

Теперь предположим, что ЕАХ равен нулю. При переходе на L2 его цель не буД загружена, так как неправильно предсказанное возвращение приведет к очистке конвейера. Затем цель второго вызова Р также не будет загружена, потому что JZ L2 вызовет

новую очистку конвейера. Здесь возникает ситуация, в которой цепь последователь! переходов заставляет постоянно очищаться конвейер из-за того, что первый переход ( предсказан неправильно. Элемент ВТВ для JZ L2 определяется по адресу инструк возврата из функции Р. Этот элемент ВТВ будет теперь неправильно присоединен к му, что должно быть после второго вызова Р, но это не приводит к потерям, так как к вейер очищается из-за неправильно предсказанного второго возврата.

Нужно посмотреть, что случитсья, если ЕАХ не будет равен нулю в следующий ] JZ L2 будет всегда предсказываться как невыполняющийся из-за очистки конвейс Второй вызов CALL Р будет иметь элемент ВТВ указывающий на TEST ЕАХ,Е/ Этот элемент будет неправильно ассоциирован с парой MOV/ADD, предсказывая ш ход на Р. Это приведет к очистке конвейера, который не даст загрузить цель JNZ Второй вызов CALL Р будет иметь в ВТВ элемент с адресом DEC ЕАХ. При вто] и третьем повторении цикла этот элемент также будет неправильно ассоциирован с рой MOV/ADD, пока ее состояние не понизится до 1 или 0. Это не вызовет пот во втором выполнении, так как очистка конвейера от JNZ ЕГ не даст загрузить невер! цель, но в третий раз так и случится. Последовательные итерации цикла не приво к потерям, но если они есть, то JNZ L1 будет предсказан неправильно. Очистка буф сделает невозможной зафузку цели CALL Р, не считая того, что ее элемент ВТВ ; был уничтожен несколькими неправильными ассоциированиями.

Можно улучшить этот код, поместив несколько NOPob, чтобы отделить последе тельные переходы друг от друга:

CALL Р

TEST ЕАХ,ЕАХ NOP

JZ L2 LI: MOV [EDI],EBX

ADD EDI,4

DEC EAX

JNZ LI . L2: NOP

CALL P

Дополнительные NOP фебуют 2 такта, но они сэкономят гораздо больше. Более т JZ L2 теперь перемещяется в U-конвейер, что снижает потери в случае неправильт предсказания с 4 до 3 тактов. Единственная оставшаяся проблема - это возвраты и которые всегда предсказываются неправильно. Эту проблему можно решить, заме вызов Р на макрос (если есть достаточно свободного места в кэше кода).

Урок, который можно извлечь из этого примера, заключается в том, что стоит внт тельно конфолировать последовательные переходы и смофеть, можно ли сэконо\ немного времени с помощью нескольких дополнительных NOP. Следует избегать та