Оптимизация для процессоров семейства Pentium: 22. Команды передачи управления и переходов (все процессоры) — Архив WASM.RU
Семейство процессоров Pentium пытаются предсказывать, когда произойдет безусловный переход и будет ли осуществлен условный. Если предсказание оказывается верным, тогда это может сэкономить существенное количество времени, так как в конвеер будут загружены последующие инструкции, и начнется их раскодировка еще до того, как будет осуществлен сам переход. Если пресказание оказывается неверным, тогда конвеер должен быть очищен, что вызовет потери производительности, количество которых зависит от длины конвеера.
Предсказания основываются на буфере переходов (BTB), который сохраняет историю каждого перехода и делает предсказания, основываясь на прежних выполнения каждой инструкции. BTB организован как множественно-ассоциативный (set-associative) кэш, в котором новые элементы используются согласно псевдослучайному методу замещений.
Оптимизируя код важно снижать количество возможных неправильных предсказаний перехода. Это можно сделать при хорошом понимании того, как работает предсказание переходов.
Механизм предсказания переходов адекватно не объясняется ни в руководствах от Интела, ни где-нибудь еще, поэтому здесь дается очень детальное описание. Эта информация основывается на моих собственных исследованиях (осуществленных с помощью Karki Jitendra Bahadur для PPlain).
Далее я буду использовать термин "команда передачи управления" для любой инструкции, которая меняет eip, включая условные и безусловные, прямые и косвенные, ближние и дальние переходы, вызовы и возвраты. Все эти инструкции используют предсказание.
22.1 Предсказывание переходов в PPlain
Механизм предсказывания переходов в PPlain очень отличается от того, как это реализовано в других трех процессорах. Информация, найденная по этой теме в документах от Интела и где-либо еще очень противоречива, и данные в этих документах советы приводят к неполностью оптимизированному коду.
У PPlain есть буфер переходов (BTB), который может содержать информацию о 256 инструкциях перехода. BTB организована в виде 4-х направленного множественно-ассоциативного кэша по 64 элемента на каждом направлении. Это означает, что BTB может содержать не больше чем 4 элемента для каждого set-значения. Как высчитывается set-значение будет объяснено позже. Каждый элемент BTB хранит адрес, куда должен быть совершен переход и состояние предсказания, которое может иметь три разных значения:
- состояние 0: "не будет осуществлен"
- состояние 1: "возможно не будет осуществлен"
- состояние 2: "возможно будет осуществлен"
- состояние 3: "будет осуществлен"
Предсказывается, что инструкция перехода будет осуществлена, когда состояние равно 2 или 3, и пропускается при состоянии 0 или 1. Состояние перехода работает как двух-битный счетчик, поэтому состояние увеличивается на 1, если переход был осуществлен и понижается, если этого не произошло. Понижение и повышение значения происходит по принципу "насыщения", то есть значение не может понизиться ниже 0 (и стать 3) и не может повыситься выше 3 (и стать 0). По идее, все это должно привести к довольно хорошему проценту правильных предсказаний, потому что до того, как будет изменено предсказание, инструкция перехода должна быть выполнена два раза не так, как она выполняется обычно.
Тем не менее, этот механизм может был поставлен под угрозу тем, что состояние 0 также означает "неиспользованный элемент BTB". Поэтому элемент BTB с состоянием 0 означает примерно то же, что если бы его вообще не было. Это имеет смысл, потому что если у инструкции перехода нет соответствующего элемента BTB, предсказывается, что она не будет осуществлена. Это улучшает использование BTB, так как инструкция перехода, которая редко осуществляется большую часть времени не будет занимать никакого элемента BTB.
Если у инструкции перехода нет своего элемента в BTB, генерируется такой элемент и значение его состояние будет установлено в 3. Это означает, что перейти от состояния 0 к состоянию 1 невозможно (кроме очень специфических случаев, обсуждаемых позже). От состояния 0 вы можете перейти только к состоянию 3, если иснтрукция перехода будет выполнена. Если этого не произойдет, она не получит свой элемент в BTB.
Это серьезный промах в дизайне архитектуры процессора. Очевидно, что таким образом дизайнеры отдали предпочтение минимизации потери роизводительности при загрузке в первый раз часто выполняющихся инструкций перехода и проигнорировали то, что это серьезно искажает первоначальную идею и снижает производительность в маленьких внутренних циклах. Следствием этого изъяна явлется то, что инструкция перехода, которая большую часть времени не выполняется, может иметь в три раза больше неправильных предсказаний, чем инструкция перхода, которая большую часть времени выполняется. (Похоже, что пока я не опубликовал свои исследования, инженеры Интела были не в курсе насчет этого).
Вы можете принять эту ассиметричность в расчет, организовав ваши ветви так, чтобы они чаще выполнялись, а не пропускались. Посмотрите на этот пример конструкции if-then-else:
Код (Text):
Если ветвь 1 выполняется чаще, чем ветвь 2, а последняя выполняется реже в два раза, тогда вы можете снизить количество неправильных предсказаний, поменяв две ветви так, чтобы инструкция перехода выполнялась чаще, чем пропускалась:
Код (Text):
(Это противоречит рекомендациям в интеловских руководствах и туториалах).
Тем не менее, есть причины, что помечать чаще выполняющуюся вертвь первой:
- Помещение редко используемых ветвей подальше от основного кода делает использование кода кэша более оптимальным.
- Редко выполняющаяся инструкция перехода не будет напрасно занимать элемент BTB, что, вероятно, сделает использование BTB более оптимальным.
- Инструкция перехода будет предсказан как не выполняющаяся, если она была вытеснена другими инструкциями из BTB.
- Ассиметричность предсказывания переходов существует только в PPlain.
Впрочем, эти предположения не играет никакой роли для маленьких критических циклов, поэтому я все же рекомендую организовывать ветви так, как это было описано выше.
Так же вам следует организовать циклы таким образом, чтобы проверка условия производилась внизу цикла, как в нижеприведенном примере:
Код (Text):
Если N велико, тогда инструкция JNZ будет чаще выполняться, чем пропускаться.
Представьте ситуацию, где инструкция перехода выполняется каждый второй раз. В первый раз она попадает в BTB с состоянием 3, а затем будет колебаться между состояниями 2 и 3. Каждый раз будет предсказываться, что она выполниться, но только 50% этих предсказаний будет верными. Теперь предположите, что однажды она отклонилась от привычного поведения и была пропущена.
01010100101010101010101, where 0 means nojump, and 1 means jump. ^01010100101010101010101, где 0 означает пропуск, а 1 означает переход. ^Дополнительный пропуск помечен знаком '^'. После этого происшествия элемент BTB будет колебаться между состояниями 1 и 2, что будет давать 100% неправильных предсказаний. И так будет продолжаться, пока не случиться еще одно отклонение. Это худшее, что можете произойти в работе этого механизма предсказания переходов.
22.1.2 BTB смотрит вперед (PPlain)
Механизм BTB подсчитывает инструкции попарно, а не по отдельности, поэтому вы должны знать, как инструкции спариваются, чтобы суметь проанализировать, где храниться элемент BTB. Элемент BTB для любой управляющей инструкции присоединяется к адресу инструкции в U-конвеере из предыдущей пары инструкций (неспариваемая инструкция идет за одну пару).
Пример:
Код (Text):
Здесь SHR спаривается с MOV, а CMP спаривается с JB. BTB-элемент для 'JB L' присоединяется к адресу инструкции 'SHR EAX,1'. Когда встречается этот BTB-элемент, и он находится в состоянии 2 или 3, тогда Pentium считает целевой адрес из элемента BTB и загрузит инструкции, следующие за L в конвеер. Это произойдет до того, как будет декодирована инструкция перехода, поэтому Pentium полагается исключительно на информацию, содержащуюся в BTB, когда делает это.
Вы можете вспомнить, что инструкции редко спариваются в первый раз при выполнении (смотрите главу 8). Если инструкции выше не спарились, тогда элемент BTB будет присоединен к адресу инструкции CMP, и данный элемент будет неверен при следующем выполнении, когда инструкции уже спарились. Тем не менее, в большинстве случаев PPlain достаточно умен, чтобы не делать элемент BTB при неиспользованной возможности спаривания, поэтому вы получите BTB-элемент только при втором выполнении, а следовательно, предсказания начнутся только с третьего. (В редких случаях, когда каждая вторая инструкция размером в один байт, элемент BTB может возникнуть уже при первом выполнении, что окажется неверным при втором выполнении, но так как инструкция, к которой был присоединен элемент, попадет в V-конвеер, это игнорируется и не вызывает особых потерь. Элемент BTB считывается только тогда, когда он присоединен к адресу инструкции для U-конвеера).
BTB-элемент идентифицируется своим set-значением, которое равно битам 0-5 адреса, к которому он присоединен. Биты 6-31 сохраняются в BTB как тег. Адреса, которые находятся на расстоянии кратном 64 байтам, будут иметь одно и то же set-значение. Вы можете иметь не более четырех BTB-элементов с одинаковым set-значением. Если вы хотите проверить, не будет ли ваша инструкция перехода бороться с другой инструкцией за один и тот же элемент BTB, вы можете сравнить биты 0-5 адресов инструкций, направляющихся в U-конвеер, из предыдущих пар инструкций. Это очень утомительно, и я никогда не слышал о том, что кто-нибудь делал подобное. Нет никаких инструментов, которые могли бы выполнить эту работу за вас.
22.1.3 Последовательные ветви (PPlain)
Когда переход пресдказан неправильно, то конвеер очищается. Если следующая пара инструкций также содержит управляющую инструкцию, то PPlain не будет загружать ее цель, так как он не может этого сделать, пока конвеер не очищен. В результатет вторая инструкция предсказывается как невыполняющаяся вне зависимости от состояния элемента BTB. Поэтому, если второй переход также выполняется на самом деле, то вы получите новые потери. Состояние BTB-элемента для второго перехода будет, тем не менее, правильно изменено. Если у вас есть длиная цепочка инструкций передачи управления, и первый переход в цепочке был предсказан неправильно, тогда конвеер будет постоянно очищаться, и предсказания будут постоянно неправильными, пока не будет встречена пара инструкций, в которой не будет перехода. Самый экстремальный случай подобного рода - это цикл, в котором происходят потери при каждой итерации из-за постоянного неправильного предсказания.
Это не едиснтвенная проблема с последовательными управляющими инструкциями. Другая проблема состоит в том, что у вас может быть другая управляющая инструкция между BTB-элементом и управляющей инструкцией, принадлежащей ему. Если первая инструкция производит переход, то могут произойти странные вещи. Представьте следующий пример:
Код (Text):
Когда 'JB L1' пропускается, вы можете получить элемент BTB, присоединенный к адресу 'CMP EAX,EBX'. Но что случится, если 'JB L1' будет выполнена? В тот момент, когда считывается BTB-элемент для 'JMP L2', процессор не знает, что следующая пара инструкций не содержит команду перехода, поэтому он фактически предскажет, что пара инструкций 'MOV EAX,EBX / INC EBX' перейдет на L2. Потери, связанные с предсказанием инструкций, не являющихся командами перехода, равны 3 тактам. Элемент BTB для 'JMP L2' понизит свое состояние на один, потому что он относится к чему-то, что не совершает перхода. Если мы перейдем к L1, тогда состояние элемента BTB для 'JMP L2' будет понижежено до 1 и 0, поэтому данная проблема исчезнет, пока не снова не будет выполнено 'JMP L2'.
Потери при предсказании инструкций, не являющихся управляющими, случаются только тогда, когда предсказавыется переход на L1. В случае, если выполнение 'JB L1' предсказано ошибочно, тогда конвеер очищается, и мы не получим фальшивую загрузку цели L2, поэтому в этом случае мы не заметим потери от предсказания неуправляющих инструкций как выполняющихся, но состояние элемента BTB для 'JMP L2' будет понижено.
Теперь предположите, что мы заменяем инструкцию 'INC EBX' на другую инструкцию перехода. Тогда третья инструкция перехода будет использовать тот же элемент BTB, что и 'JMP L2', что приводит к возможным потерям из-за предсказания неправильной цели (если только целью не является L2).
Теперь прорезюмируем возможные проблемы, к которым могут привести последовательные переходы:
- невозможность загрузить цель перехода, когда конвеер очищается из-за предыдущего неправильно предсказанного перехода.
- элемент BTB может быть присоединен не к инструкции перехода и предсказать их как выполняющиеся.
- второе последствие вышеизложенного - неправильно присоединенный элемент BTB будет понижать свое состояние, что может привести к последующему неправильному предсказанию перехода, к которому он принадлежит. Даже безусловные переходы из-за этого могут быть предсказанны как невыполняющиеся.
- две инструкции перехода могут использовать один и тот же элемент BTB, что может привести к предсказанию неправильной цели.
Вся эта путаница может привести к многчисленным потерям, поэтому вы определенно должны избегать пар инструкций, содержащих переход, находящихся непосредственно после плохо предсказуемой инструкции передачи управления.
Теперь еще один показательный пример:
Код (Text):
На первый взгляд как будто все в порядке: вызов функции, цикл, который пропускается, если счетчик равняется нулю, и другой вызов функциии. Какие проблему могут возникнуть?
Сначала мы можем заметить, что функция P вызывается из двух различных мест кода. Это означает, что цель возвращения из P будет все время меняться. Соответственно, возврат из P будет все время предсказываться неправильно.
Теперь предположите, что EAX равен нулю. При переходе на L2 его цель не будет загружена, так как неправильно предсказанное возвращение приведет к очищению конвеера. Затем цель второго вызова P также не будет загружена, потому что 'JZ L2' вызовет новое очищение ковеера. Здесь мы имеем ситуацию, в которой цепь последовательных переходов заставляет постоянно очищаться конвеер из-за того, что первый переход был предсказан неправильно. Элемент BTB для 'JZ L2' сохраняется по адресу инструкции возвращения из функции P. Этот элемент BTB будет теперь неправильно присоединен к тому, что должно быть после второго вызова P, но это не приводит к потерям, так как конвеер очищается из-за неправильно предсказанного второго возвращения.
Теперь давайте посмотрим, что случитсья, если EAX не равен нулю в следующий раз: 'JZ L2' будет всегда предсказываться как невыполняющийся из-за очищения конвеера. Второй 'CALL P' будет иметь свой элемент по адресу 'TEST EAX,EAX'. Этот элемент будет неправильно ассоциирован с парой 'MOV/ADD', предсказывая их переход на P. Это приведет к очищению конвеера, который не даст загрузить цель 'JNZ L1'. Если мы уже были здесь ранее, тогда второй 'CALL P' будет иметь другой элемент BTB с адресом 'DEC EAX'. При втором и третьем повторении цикла этот элемент также будет неправильно ассоциирован с парой 'MOV/ADD', пока ее состояние не понизится до 1 или 0. Это не вызовет потерь во втором выполнении, так как очищение конвеера от 'JNZ L1' не даст загрузить неверную цель, но в третьем выполнении так и случится. Последовательные итерации цикла не приводят к потерям, но если они есть, то JNZ L1 будет предсказан неправильно. Очищение буфера сделает невозможной загрузку цели 'CALL P', не считая того, что ее элемент BTB уже был уничтожен несколькими неправильными ассоциированиями.
Мы можем улучшить этот код, поместив несколько NOP'ов, чтобы отделить друг от друга последовательные переходы:
Код (Text):
Дополнительные NOP'ы стоят 2 такта, но они сохранят гораздо больше. Более того, 'JZ L2' теперь перемещяется в U-конвеер, что снижает потери в случае неправильного предсказания с 4 до 3 тактов. Единственная оставшаяся проблема - это возвраты из P, которые всегда предсказываются неправильно. Эту проблему можно решить, заменив вызов P на макрос (если у вас есть достаточное количество свободного кэша кода).
Урок, который можно извлечь из этого примера, заключается в том, что вам всегда стоит внимательно контролировать последовательные переходы и смотреть, не можете ли вы сэкономить немного времени с помощью нескольких NOP'ов. Вам следует избегать таких ситуаций, когда неправильное предсказание неибежно, например, выходы из циклов и возвращения из процедур, вызываемых из разных мест. Если у вас есть что-нибудь полезное, что можно поместить вместо NOP'ов, тогда вам, конечно, следует поместить именно это.
Мультиветвенные переходы (выражения условий) можно сделать либо в виде дерева инструкций переходов, либо в виде списка адресов переходов. Если вы выберите дерево инструкций переходов, то вам стоит включить несколько NOP'ов или других инструкций, чтобы отделить последовательные переходы друг от друга, поэтому список адресов может быть более выгодным вариантом на PPlain. Список адресов переходов следует помещать в сегменте данных. Никогда не помещайет данные в сегменте кода!
22.1.4 Маленькие циклы (PPlain)
В маленьких циклах часто происходит доступ к одному и тому же элементу BTB с небольшими интервалами. Вместо того, чтобы ждать, когда обновится элемент BTB, PPlain каким-то образом минует конвеер и получает состояние после последнего перехода, прежде, чем оно записывает в BTB. Этот механизм почти прозрачен для пользователя, но в некоторых случаях он приводит к забавным эффектам: вы можете видеть предсказание перехода от состояния 0 к состоянию 1, а не к состоянию 3, если ноль еще не быль записан в BTB. Это случается, если в цикле не больше четырех пар инструкций. В цикла с двумя парами инструкций может случиться так, что состояние 0 сохраняется на протяжении двух итераций, причем элемент не стирается из BTB. В таких маленьких циклах в редких случаях предсказание использует состояние, бывшее два цикла назад, а не в предыдущем повторении. Эти забавные эффекты обычно не приводят к снижению качества.
22.2 Предсказание переходов в PMMX, PPro, PII и PIII
22.2.1 Организация BTB (PMMX, PPro, PII и PIII)
Буфер переходов (BTB) PMMX состоит из 256 элементов, организованых как 16 направлений * 16 множеств. Каждый элемент идентифицируется битами 2-31 адреса последнего байта инструкции передачи управления, которой он принадлежит. Биты 2-5 определяют множество, а биты 6-31 сохраняются в BTB как тег. Инструкции передачи управления, находящиеся друг от друга на расстоянии 64 байт, имеют одинаковое set-значение, и поэтому могут случайно выдавливать друг друга из BTB. Так как есть 16 направление на множество, то это не будет происходить слишком часто.
Буфер переходов PPro, PII и PIII имеет 512 элементов (16 направлений * 32 множества). Каждый элемент идентифицируется битами 4-31 адреса последнего байта инструкции передачи управления, к которой он принадлежит. Биты 4-8 определяют множество, и все биты сохраняются в BTB как тег. Инструкции передачи управления, которые находятся друг от друга на расстоянии 512 байт, могут случайно выдавливать друг друга из BTB. Так как есть 16 направлений на множество, это не бдует происходить слишком часто.
PPro, PII и PIII резервируют элемент BTB для любой инструкции передачи управления в первый раз ее выполнения (независимо от того, совершает ли она переход, или пропускается). PMMX резервирует элемент в первый раз, когда совершается переход. Инструкция перехода, которая никогда не совершает переход, будет оставаться вне BTB на PMMX. Как только она однажды совершит переход, она окажется в BTB и будет оставаться там все время, даже если она никогда не будет совершать переход снова.
Элемент может быть выдавлен из BTB, когда другой инструкции передачи управления с тем же самым set-значение требуется элемент BTB.
22.2.2 Потери при неверном предсказании (PMMX, PPro, PII и PIII)
На PMMX потери из-за неверного предсказания условного перехода равны 4 тактам для инструкции в U-конвеере и 5 тактам, если она выполнялась в V-конвеере. Для всех других инструкций передачи управления потери равны 4 тактам.
На PPro, PII и PIII потери из-за неверного предсказания очень высоки, так как у этих процессоров длинный конвеер. Неправильное предсказание обычно стоит от 10 до 20 тактов. Поэтому очень важно избегать плохо предсказуемых ветвей, если программа будет выполняться на PPro, PII и PIII.
22.2.3 Распознавание последовательностей условных переходов (PMMX, PPro, PII и PIII)
У этих процессоров есть продвинутый механизм распознавания последовательностей, который может правильно предсказать выполнение инструкции переходов, например, если так совершает переход каждый четвертый раз и не выполняется в остальные три раза. Фактически они могут предсказать любую повторяющуюся последовательность переходов и не-переходов, если период не превышает пяти, и многие последовательности с более высокими периодами.
Этот механизм называется "двух-уровневой адаптирующейся схемой предсказания". Он был изобретен T.-Y. Yeh и Y. N. Patt. Механизм основывается на разновидности двухбитного счетчика, использующихся в PPlain (но без изъяна, описанного выше). Счетчик повышается, когда совершается переход и понижается, когда этого не происходит. Нет автоматического обнуления при повышении 3 или приравнивания к 3 при понижении 0. Инструкция перехода предсказывается как выполняющаяся, если соответствующий счетчик равен 3 или 3, и предсказывается как несовершающая переход, если он равен 0 или 1. Значительное улучшение данного алгоритма было получено путем введения 16 таких счетчиков для каждого элемента BTB. Он выбирает один из этих шестнадцати счетчиков, основываясь на истории выполнения переходов за четыре последних раза. Если, например, инструкция перехода однажды выполняется, а потом нет на протяжении четырех последних раз. Если, например, инструкция перехода совершает его однажды и затем не делает его три раза подряд, тогда биты истории равны 1000 (1 = переход, 0 = не-переход). Значит, будет использоваться счетчик под номером 8 (1000b = 8) для предсказания в следующий раз и обновления состояния счетчика.
Если последовательность 1000 всегда следует за 1, тогда счетчик под номером 8 вскоре достигнет своего нивысшего состояния (3), что означает постоянное предсказываения последовательности 1000. Потребуется два отклонения от этой последовательности, чтобы изменить предсказание. Посвторяющаяся последовательность 100010001000 будет иметь счетчик 8 в состоянии 3 и счетчик 1, 2 и 4 в состоянии 0. Другие двенадцать счетчиков не будут использоваться.
22.2.4 Последовательности, предсказанные совершенно (PMMX, PPro, PII, PIII)
Повторяющаяся последовательность предсказывается совершенно этим механизмом, если каждая 4-х битная подпоследовательность полного периода уникальная. Ниже представлен список последовательностей, которые предсказываются совершенно:
period perfectly predicted patterns 1-5 all 6 000011, 000101, 000111, 001011 7 0000101, 0000111, 0001011 8 00001011, 00001111, 00010011, 00010111, 00101101 9 000010011, 000010111, 000100111, 000101101 10 0000100111, 0000101101, 0000101111, 0000110111, 0001010011, 0001011101 11 00001001111, 00001010011, 00001011101, 00010100111 12 000010100111, 000010111101, 000011010111, 000100110111, 000100111011 13 0000100110111, 0000100111011, 0000101001111 14 00001001101111, 00001001111011, 00010011010111, 00010011101011, 00010110011101, 00010110100111 000010011010111, 000010011101011, 000010100110111, 15 000010100111011, 000010110011101, 000010110100111, 000010111010011, 000011010010111 16 0000100110101111, 0000100111101011, 0000101100111101, 0000101101001111Читая эту таблицу, вы должны учитывать, что если последовательность предсказывается верно, тогда та же последовательность, но прочитанная задом-наперед также будет предсказана верно, также как и та же последовательность, но с инвертированным битами. Пример: в таблице мы нашли последовательность: 001011. Изменение порядка битов на обратный дает: 1101000. Инвертирование всех битов дает 1110100. Изменение порядка битов и инвертирование вместе: 0010111. Все эти четыре последовательности будут распознаны. Циклический сдвиг всех битов на одну позицию влево дает: 0010110. Это, конечно, не новая последовательность, а всего лишь чуть сдвинутая версия той, которую мы рассматривали. Все последовательности, которые могут быть выведены от одной из перечисленных в таблице с помощью изменения порядка битов, инвертирования и циклического сдвига также могут быть разпознанны. В целях экономии места они не были перечисленны.
У механизма распознавания последовательностей уходит два периода на то, чтобы выучить регулярную повторяющуюся последовательность после того, как был создан соответствующий элемент BTB. Последовательность неправильных предсказаний в период обучения не воспроизводима, вероятно из-за того, что элемент BTB содержит что-то до того, как резервируется. Так как элементы BTB резервируются по случайной схеме, то предсказание того, что произойдет в течении начального периода, маловероятно.
22.2.5 Обработка отклонений от регулярных последовательностей (PMMX, PPro, PII и PIII)
Механизм предсказания также довольно хорошо справляется с обработкой 'почти регулярных' последовательностей или отклонений от регулярной последовательности. Он не только заучивает, как выглядит регулярная последовательность, он также изучает, какие существуют отклонения от нее. Если отклонения все время одни и те же, тогда он будет помнить, что идет после отклонения, и оно будет стоить толко одно неправильное предсказание.
Пример:
0001110001110001110001011100011100011100010111000 ^ ^В этой последовательности 0 означает не-переход, а 1 - переход. Механизм выучивает то, что повторяющаяся последовательность равна 000111. Первое отклонение - это неожиданный 0, который я отметил знаком '^'. После этого 0 следующие три перехода могут быть неправильно предсказаны, потому что механизм еще не выучил, что идет после 0010, 0101 и 1011. После одного или двух отклонений того же вида он выучивает, что после 0010 идет 1, после 0101 идет 1, а после 1011 идет 1. Это означает, что после двух отклонений одного и того же вида, он выучивает как их обрабатывать, допуская только одно неправильное предсказание.
Механизм предсказания очень эффективени, когда происходит смена одной регулярной последовательности на другую. Если, например, у нас была последовательность 000111 (с периодом 6), которая повторилась много раз, потом последовательность 01 (период 2) много раз, а затем произошел возврат на последовательность 000111, тогда механизм не должен снова изучать последовательность 000111, так как счетчики, которые были использованы для этой последовательность остались в неприкосновенности. После нескольких смен последовательностей с одной на другую, механизм также выучивает, как обрабатывать изменения ценой только одного неправильного предсказания во время переключения одной последовательности на другую.
22.2.6 Последовательности, не предсказываемые совершенно (PMMX, PPro, PII и PIII)
Простейшая последовательность, которая не может быть предсказана совершенно - это переход, который совершается каждый 6-ой раз. Вот последовательность:
000001000001000001 ^^ ^^ ^^ ab ab abЗа последовательностью 0000 следует 0 в позициях, помеченных 'a', и 1, в позициях, помеченных 'b'. Это влияет на счетчик под номером 0, который постоянно повышает и понижает свое значение. Если счетчик 0 был вначале равен 0 или 1, тогда он будет колебаться между 0 и 1. Это приведет к неправильному предсказанию в позиции b. Если счетчик 0 был в самом начале равен 3, тогда он будет колебаться между состояниями 2 и 3, что приведет к неправильному предсказанию в позиции a. Худший случай - это когда его состояние было в начале равно 2. Он будет колебаться между 1 и 2, что приведет к неправильному предсказанию в обоих позициях. (Это аналогично худшему случаю для PPlain, объясненному выше). Какую из этих ситуаций мы получим, зависит от истории элемента BTB до того, как он был зарезервирован. Мы не можем это проконтролировать, так как элементы BTB выбираются случайно.
В принципе, можно избежать худший случай, если задать в самом начале задать специально спроектированную последовательность, чтобы поместить счетчик в желаемое состояние. Такой подход трудно порекомендовать, так как он значительно усложняет код и любая информация, которую мы поместим в счетчик будет, похоже, потеряна при следующем прерывании или переключении задач.
22.2.7 Полностью случайные последовательности (PMMX, PPro, PII и PIII)
Мощная способность распознавания последовательностей имеют небольшой изъян в случае полностью случайных нерегулярных последовательностей.
Следующая таблица перечисляет эспериметально найденную часть неверных предсказаний для полностью случайных нерегулярных последовательностей.
часть переходов/не-переходов часть неверных предсказаний 0.001/0.999 0.001001 0.01/0.99 0.0101 0.05/0.95 0.0525 0.10/0.90 0.110 0.15/0.85 0.171 0.20/0.80 0.235 0.25/0.75 0.300 0.30/0.70 0.362 0.35/0.65 0.418 0.40/0.60 0.462 0.45/0.55 0.490 0.50/0.50 0.500Часть неправильных предсказаний немного вы, чем если бы это было без распознавания последовательностей, потому что процессор пытается найти повторяющиеся блоки там, где нет никакой закономерности.
22.2.8 Маленькие циклы (PMMX)
Предсказание переходов ненадежно в маленьких циклах, где у механизма распознавания последовательностей нет времени, чтобы обновить свои данные перед новой встречей с переходом. Это означает, что простые последовательности, которые в обычном случае были бы предсказаны совершенно, не будут распознанны. Также некоторые последовательности, которые в обычном случае не были бы распознаны, будут предсказаны в маленьком цикле. Например, цикл, который всегда повторяется 6 раз, имел бы последовательность 111110 для инструкции ветвления в начале цикла. В этой последовательности было бы одно или два неправильных предсказаний за итерацию, но в маленьком цикле не будет ни одного. То же самое касается цикла, который повторяется 7 раз. С другим количеством повторений предсказуемость будет хуже в маленьких циклах, чем обычно. Это означает, что количество повторений, равное 6 или 7, более предпочтительно для маленьких циклов. Вы можете развернть цикл, чтобы сделать его больше.
Чтобы узнать, подпадает ли цикл на PMMX под действие вышеизложенных правил, вы можете сделать следующее: подсчитайте количество инструкций в цикле. Если количество равно 6 или меньше, тогда цикл является "маленьким". Если у вас больше 7 инструкций, тогда у вас может быть достаточно твердая уверенность в том, что распознавание последовательностей будет работать нормально. Довольно странно, что количество тактов, которое требуется для выполнения инструкций, не играет роли, как и спариваемость инструкций и вызываемые ими задержки. Сложные целочисленные инструкции при подсчете не учитываются. В цикле может быть много таких инструкций, и он будет себя вести как "маленький". Сложная целочисленная инструкция - это не спариваемая целочисленная инструкция, которая всегда требует больше одного такта. Сложные инструкции плавающей запятой и инструкции MMX идут одна за одну. Обратите внимание, что это правило выведено эвристическим путем и не 100% надежно. В важных случаях вы можете провести свое собственное тестирование. Вы можете использовать датчик качества с номером 35 в PMMX, чтобы подсчитать количество неправильно предсказанных переходов. Результаты тестов также не могут быть полностью надежны, потому что предсказания переходов зависят от истории элемента BTB до резервирования.
Маленькие циклы на PPro, PII и PIII предсказываются нормально, и каждое повторение занимает минимум два цикла.
22.2.9 Косвенные переходы и вызовы (PMMX, PPro, PII и PIII)
Распознавание последовательностей не работает в случае косвенных переходов и вызовов, а BTB не может запомнить больше одной цели для косвенного вызова. Предсказывается переход к той же цели, что и в прошлый раз.
22.2.10 JECXZ и LOOP (PMMX)
На PMMX распознавание последовательностей не работает с этими двумя инструкциями, просто предсказывается то, что произошло в последний раз. Эти две инструкции следует избегать в критическом коде для PMMX (на PPro, PII и PIII) предсказания осуществляются с помощью распознавания последовательностей, но специальные инструкции циклов все равно ужасны по сравнению с DEC ECX / JNZ).
22.2.11 Возвраты (PMMX, PPro, PII и PIII)
У процессоры PMMX, PPro, PII и PIII есть стековый буфер возвратов (RSB), который используется для предсказывания инструкций возвратов. RSB работает как FIFO (первым-вошел-первым-вышел) буфер. Каждый раз, когда выполняется инструкция вызова, соответствующий адрес возврата помещается в RSB. И каждый раз, когда выполняется инструкция возврата, адрес возвращения вынимается из RSB и используется для предсказывания возврата. Этот механизм обеспечивает корректное предсказание этих инструкций, когда одна и та же подпрограмма вызывается из разных мест.
Чтобы этот механизм работал правильно, вы должны убедиться, что все вызовы и возвраты соответствуют. Никогда не выходите из подпрограммы без возвраты и никогда не используйте возврат в качестве косвенного перехода, если скорость играет решающую роль.
RSB может содержать до 4 элементов в PMMX, шестнадцать в PPro, PII и PIII. В случае, когда RSP пуст, инструкция возврата предсказывается также, как и косвенный переход, то есть ожидается переход туда, куда он был совершен в последний раз.
На PMMX, когда подпрограммы вложены друг в друга более, чем на 4 уровня, все возвраты, кроме 4 самых внутренних уровней, поддерживаемых PMMX, используют простой механизм предсказания, пока не происходит новых вызовов. Инструкция возврата, находящаяся в RSB, также занимает один элемент BTB. Четыре элемента в RSB PMMX'а кажутся не весть чем, но это, вероятно, эффективно. Подрограммы, вложенные более, чем на 4 уровня, не являются чем-то необычным, но только внутренние уровни максимально эффективны в плане скорости, не считая возможности рекурсивных процедур.
На PPro, PII и PIII, когда подпрограммы вложены глубже, чем на 16 уровней, внутренние 16 уровней используют RSB, в то время как все последующие возвраты из внешних уровней предсказываются неверно, поэтому рекурсивные процедуры не следует делать вложенными более, чем на 16 уровней.
22.2.12 Статическое предсказание (PMMX)
Инструкция передачи управления, которая не встречалась ранее, или которая не находится в BTB всегда предсказывается как невыполняющаяся на PMMX. Не играет роли, куда совершается переход: вперед или назад.
Инструкция перехода не получит элемент BTB, если она постоянно невыполняется. Как только она выполнится, она попадет в BTB и будет оставаться там вне зависимости от того, сколько раз она не выполнится в дальнейшем. Инструкция передачи управления может исчезнуть из BTB только, если она была выдавлена другой инструкцией передачи управления.
Любая инструкция передачи управления, которая переходит на адрес, непосредственно следующий за ней же, не получает элемент в BTB.
Пример:
LL:Код (Text):
Эта инструкция никогда не поулчит элемент в BTB и поэтому всегда будет предсказываться неправильно.
22.2.13 Статическое предсказывание (PPro, PII и PIII)
На PPro, PII и PIII инструкция передачи управления, которая не встречалась ранее или которой нет в BTB, предсказывается как невыполняющаяся, если она указывает вперед, и как выполняющаяся, если она указывает назад (например, цикл). Статическое предсказываение занимает больше времени, чем динамическое предсказание на этих процессорах.
Если похоже, что ваш код не прокэширован, то предпочтительнее, чтобы наиболее часто встречающаяся инструкция перехода не выполнялась, чтобы улучшить доставку.
22.2.14 Закрытые переходы (PMMX)
На PMMX существует риск, что две инструкции передачи управления разделят один и тот же элемент BTB, если они находятся слишком близко друг к другу. Очевидным результатом станет то, что они всегда будут предсказываться неправильно.
Элемент BTB для инструкции передачи управления определяется по битам 2-31 адреса последнего байта инструкции. Если две инструкции передачи управления находятся так близко друг от друга, что отличаются только битами 0-1 этих адресов, то у нас есть проблема разделяемого элемента BTB. Пример:
Код (Text):
Если последний байт инструкции CALL и последний байт инструкции JNC находятся внутри того же слова памяти, то мы получаем потери. Вы должны взглянуть на сгенерированный ассемблерный листинг, чтобы увидеть, разделены ли эти два адреса границей двойного слова или нет (граница двойного слова - это адрес, который делится на 4).
Есть несколько путей решить эту проблему:
- Переместить код чуть вверх или вниз в памяти, чтобы между двумя адресами была граница двойного слова.
- Изменить короткий переход на ближний переход, чтобы конец инструкции сместился чуть вниз.
- Поместить какую-либо инструкцию между CALL и JNC. Это самый простой метод и единственный, если вы не знаете, где находятся границы двойного слова, например если ваш сегмент не выровнен по двойному слову или потому что код смещается то вверх, то вниз в результате изменений в предшествущем коде.
Код (Text):
Если вы хотите избежать проблем и на PPlain, тогда поместите вместо MOV два NOP'а, чтобы предотвратить спаривание.
Инструкция RET особенно беззащитна перед этой проблемой, потому она всего один байт длиной.
Код (Text):
Здесь вам может потребоваться вставить три байта:
Код (Text):
22.2.15 Последовательные вызовы или возвраты (PMMX)
Возникают потери, когда первая пара инструкций, следующая за меткой-целью вызова, содержит другой вызов или возврат, следующий сразу после другого возврата.
Пример:
Код (Text):
Требуется два NOP перед 'CALL FUNC2', потому что один NOP будет спариваться с CALL. Одного NOP достаточно перед RET, потому что эта инструкция неспариваема. Не требуется NOP между двумя инструкциями CALL, потому что нет потерь при вызове после возврата (на PPlain вам потребуется здесь два NOP).
Подобные потери последовательных вызовах возникают только, когда одни и те же подпрограммы вызываются из более, чем одного места (вероятно, это происходит из-за обновления RSB). Последовательные возвраты всегда приводят к потерям. Иногда возникает небольшая задержка при переходе после вызова, но нет потерь при возврате после вызова, вызова после возврата, перехода, вызова или возврата после перехода или перехода после возврата.
22.2.16 Последовательные переходы (PPro, PII и PIII)
Переход, вызов или возврат не может выполниться в первый такт после предыдущего перехода, вызова или возврата. Поэтому последовательные переходы занимают по два такта на переход, и вы можете захотеть убедиться, что у процессора есть чем еще заняться. В силу определенных причин цикл требует не менее двух тактов на итерацию на этих процессорах.
22.2.17 Проектирование предсказуемых переходв (PMMX, PPro, PII и PIII)
Многоветвенные переходы (реализующие высокоуровневые выражения switch/case) реализуются как список адресов переходов или как дерево инструкций переходов. Так как косвенные переходы предсказываются плохо, то последний метод может быть более предпочтителен, если дерево будет представлено в виде хорошо предсказуемой последовательности и у вас есть достаточное количество элементов BTB. В случае, если решите использовать предыдущий метод, рекомендуется, чтобы адреса переходов были помещены в сегмент данных.
Вы можете захотеть реорганизовать ваш код так, чтобы последовательности переходов, которые не предсказываются совершенно, были заменены другими последовательностями. Предположите, например, цикл, который выполняется 20 раз. Условный переход внизу цикла выполнится 19 раз и нет - каждый 20 раз. Эта последовательность регулярна, но не будет узнана механизмом распознавания последовательностей, поэтому невыполнение данной инструкции будет всегда предсказываться неправильно. Вы можете сделать два вложенных цикла по 4 и 5 повторений или развернуть цикл в четыре раза и позволить ему выполниться 5 раз, чтобы были только распознаваемые последовательности. Этот вид сложных схем оправдывает себя только на PPro, PII и PIII, где неверное предсказание стоит слишком дорого. Для циклов с большим количеством повторения особо смысла бороться с одним неправильным предсказанием нет.
22.3. Избегание переходов (все процессоры)
Есть много причин, почему вы можете захотеть снизить количество переходов, вызовов и возвратов:
- неверные предсказания стоят очень дорого
- в зависимости от процессора могут возникнуть различные потери при последовательных вызовах
- инструкции перехода могут выталкивать друг друга из буфера переходов
- возврат занимает 2 такта на PPlain и PMMX, вызовы и возвраты генерируют 4 мопа на PPro, PII и PIII.
- На PPro, PII и PIII доставка инструкций может быть задержена после перехода (глава 15), а вывод из обращения может быть менее эффективным для совершенных переходов, чем для других мопов (глава 18).
Вызовы и возвраты можно избежать, если заменить маленькие процедуры макросами. Во многих случаях можно снизить количество переходов, перегруппировав ваш код. Например, переход на переход можно заменить переходом к конечной цели. В некоторых случаях это возможно сделать даже с условными переходами, если условие то же самое или известно. Переход на возврат можно заменить возвратом. Если вы хотите устранить возврат на возврат, тогда вы не должны манипулировать стековым указателем, потому что это будет создавать помехи механизму предсказания, основывающимся на RSP. Вместо этого вы можете заменить предыдущий вызов на переход. Например 'CALL PRO1 / RET' можно заменить на 'JMP PRO1', если PRO1 заканчивается тем же видом RET.
Вы можете также устранить переходом, дублируя код, на который совершается переход. Это может быть полезным, если у вас есть двухнаправленная ветвь внутри цикла или до возврата.
Пример:
Код (Text):
Переход на C можно устранить, продублировав эпилог цикла:
Код (Text):
Наиболее часто выполняющийся переход здесь должен быть первым. Переход на D находится вне цикла и поэтому менее критичен. Если переход выполняется так часто, что его нужно тоже оптимизировать, то замените его тремя инструкциями, которые следуют за D.
22.4. Избегание условных переходов, используя флаги (все процессоры)
Самое главное - избавиться от условных переходов, особенно если они плохо предсказуемы. Иногда возможно получить тот же эффект, искусно манипулируя битами и флагами.
Код (Text):
(На PPlain и PMMX используйте 'MOV EDX,EAX / SAR EDX,31' вместо CDQ).
Флаг переноса особенно полезен для подобных трюков:
- Установка флага переноса, если значение равно нулю: CMP [VALUE],1
- Установка флага переноса, если значение не равно нулю: XOR EAX,EAX / CMP EAX,[VALUE]
- Повышение счетчика на 1, если установлен флаг переноса: ADC EAX,0
- Установка бита каждый раз, когда установлен флаг переноса: RCL EAX,1
- Генерация битовой маски, если установлен флаг переноса: SBB EAX,EAX
- Установка бита при определенном условии: SETcond AL
- Установка всех бит при определенном условии: XOR EAX,EAX / SETNcond AL / DEC EAX (помните о том, что в последнем примере условие должно быть сформулировано наоборот).
Следующий пример находит меньшее из двух беззнаковых чисел: if (b < a) a = b
Код (Text):
А вот пример, как выбрать между двумя числами: if (a != 0) a = b; else a = c;
Код (Text):
Стоит или нет применять подобные трюки зависит от того, насколько предсказумы условные переходы, есть или нет возможности под спариванию инструкций, есть или нет рядом другие переходы, из-за которых могут возникнуть потери.
22.5. Замена условных переходов услоными перемещениями (PPro, PII и PIII)
У процессоров PPro, PII и PIII есть инструкции условного перемещения данных, созданных специально для избежания переходов, потому что неверное предсказание перехода стоит на этих процессорах слишком дорого. Есть инструкции условного перемещения данных и для целочисленных регистров и для регистров плавающей запятой. В коде, который будет выполняться только на этих процессорах, вы можете заменить плохо предсказуемые переходы инструкциями условного перемещения там, где это возможно. Если вы хотите, чтобы ваш код выполнялся на всех процессорах, вы можете сделать две версии самого критичного кода, одну для процессоров, которые поддерживают инструкции условного перемещния и одну для тех, которые не поддерживаются (смотрите главу 27.10, чтобы узнать, как определить, поддерживает ли процессор условные переходы).
Потери из-за неправильного предсказания перехода могут быть столько высоки, что имеет смысл заменить их условными перемещениями, даже если это будет стоить несколько дополнительных инструкций. Но у инструкций условного перехода есть один недостаток: они делают цепочки зависимости длинее. Условное перемещение ждет готовности обоих операндов-регистров, даже если требуется только один из них. Условное перемещение ждет готовности трех операндов: флаг условия и еще два операнда перемещения. Вы должны решить, может ли один из этих трех операндов привести к задержкам из-за ошибок в работе с кешем или из-за цепочек зависимости. Если флаг условия доступе задолго до операндов перемещения, вы можете так же использовать инструкции перехода, потому что возможное неправильное предсказание может быть преодолено, пока ожидается готовность операндов перемещения. В тех ситуация, где вам нужно долго ждать операнд перемещения, который потом еще может и не понадобиться, инструкция перехода будет быстрее, чем условный переход, несмотря на потери, связанные с возможным неправильным предсказанием. Обратная ситуация возникает, когда флаг условия задерживается, а оба операнда перемещения доступны ранее. В этой ситуации условный переход более предпочтителен, чем инструкция перехода, если вероятно неправильно предсказание. © Агнер Фог, пер. Aquila
Оптимизация для процессоров семейства Pentium: 22. Команды передачи управления и переходов (все процессоры)
Дата публикации 22 авг 2002
