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

Точки множественного ветвления (условные выражения) можно строить либо в ви дерева инструкций переходов, либо в виде списка адресов переходов. Если выбира дерево инструкций переходов, нужно будет включать некоторое число операций или других адкватных инструкций, чтобы отделить последовательные переходы дpyJ от друга, поэтому список адресов может быть более выгодным вариантом на Р1. Список адресов переходов следует помещать в сегменте данных, а не в сегменте кода!

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

6.22.2. Предсказание переходов в РММХ, РРго, Р2 и РЗ

6.22.2.1. Организация ВТВ (РММХ, РРго, Р2 и РЗ). Буфер переходов (ВТВ) РММХ состоит из 256 элементов, организованых как 16 направлений * 16 множеств. Каждый элемент идентифицируется битами 2-31 адреса последнего байта инструкции передачи управления, которой он принадлежит. Биты 2-5 определяют множество, а биты 6-31 сохраняются в ВТВ как тег. Инструкции передачи управления, находящиеся друг от друга на расстоянии 64 байт, имеют одинаковое set-значение и поэтому могут случайно вытеснять друг друга из ВТВ

Буфер переходов РРго, Р2 и РЗ имеет 512 элементов (16 направлений * 32 множества) Каждый элемент идентифицируется битами 4-31 адреса последнего байта инструкции передачи управления, к которой он принадлежит. Биты 4-8 определяют множество, и все биты сохраняются в ВТВ как тег. Инструкции передачи управления, которые находятся друг от друга на расстоянии 512 байт, могут случайно вытеснять друг друга из ВТВ.

РРго, Р2 и РЗ резервируют элемент ВТВ для любой инструкции передачи управления в первый раз ее выполнения (независимо от того, совершает ли она переход, или пропускается). РММХ резервирует элемент в первый раз, когда совершается переход. Инструк-

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

6.22.2.2. Потери при неверном предсказании (РММХ, РРго, Р2 и РЗ). На РММХ поте-и из-за неверного предсказания условного перехода равны 4 тактам для инструкции

J и-конвейере и 5 тактам, если она выполнялась в V-конвейере. Для всех других инструкций передачи управления потери равны 4 тактам.

На РРго, Р2 и РЗ потери из-за неверного предсказания очень высоки, так как у этих процессоров длинный конвейер. Неправильное предсказание обычно от 10 до 20 тактов. Поэтому очень важно избегать плохо предсказуемых ветвей, если программа будет выполняться на РРго, Р2 и РЗ.

6.22.2.3. Распознавание последовательностей условных переходов (РММХ, РРго, Р2 и РЗ). У данных процессоров есть продвинутый механизм распознавания последовательностей переходов, который может правильно предсказать выполнение инструкций переходов даже если переход осуществляется только каждый четвертый. Фактически они могут предсказать любую повторяющуюся последовательность переходов и непереходов, если период не превышает пяти, и многие последовательности с более высокими периодами.

Этот механизм называется "двухуровневой адаптирующейся схемой предсказания". Он был изобретен T.-Y. Yeh и Y. N. Patt. Механизм основывается на разновидности двухбитного счетчика, использующихся в Р1 (но без изъяна, описанного выше). Счетчик увеличивается, когда совершается переход и уменьшается, в противном случае. Нет автоматического обнуления при повышении 3 или приравнивания к 3 при понижении 0. Инструкция перехода предсказывается как выполняющаяся, если соответствующий счетчик равен 3 или 3, и предсказывается как несовершающая пере од, если он равен О или 1. Значительное улучшение данного алгоритма было получено путем введения 16 таких счетчиков для каждого элемента ВТВ. ВТВ выбирает один из этих шестнадцати счетчиков, основываясь на истории выполнения переходов за четыре последних раза. Если инструкция перехода совершает его и затем не делает этого три раза подряд, тогда биты истории равняются 1000 (1 = переход, О = не-переход). Значит, будет использоваться счетчик под номером 8 (ЮООЬ = 8) для предсказания в следующий раз и обновления состояния счетчика.

Если последовательность 1000 всегда следует за 1, тогда счетчик под номером 8 вскоре достигнет своего наивысшего состояния (3), что означает постоянное предсказывание последовательности 1000. Потребуется два отклонения от этой последовательности, чтобы изменить предсказание. Повторяющаяся последовательность 100010001000

будет иметь счетчик 8 в состоянии 3 и счетчик 1, 2 и 4 в состоянии 0. Другие двенадцд счетчиков не будут использоваться.

6.22.2.4. Последовательности, предсказанные совершенно (РММХ, РРго, Р2, Рз Повторяющаяся последовательность предсказывается совершенно этим MexannsMov если каждая 4-битная подпоследовательность полного периода уникальна. Ниже npti ставлен список последовательностей, которые предсказьшаются совершенно.

Таблица 6.6. Совершенно предсказанные последователь ноет

Читая табл. 6.6, необходимо учитывать учитывать, что если последовательность предсказывается верно, тогда та же последовательность, но прочитанная задом-наперед, также будет предсказана верно, как и та же последовательность, но с инвертированным битами. Рассмотрим последовательность 001011 из таблищ.1. Изменение порядка битов на обратный дает 1101000. Инвертирование всех битов дает 1110100. Изменение порядка битов и инвертирование одновременно 0010111. Все эти четыре последовательности будут распознаны. Циклический сдвиг всех битов на одну позицию влево дает 00101Ю. Это, конечно, не новая последовательность, а всего лишь чуть сдвинутая версия той, которая уже рассматривалась. Все последовательности, которые могут быть выведены от одной из перечисленных в таблице с помощью изменения порядка битов, инвертирования и циклического сдвига также могут быть разпознанны.

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

, ддва 6- Оптимизация для процессоров семейства Pentium 409

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

6.22.2.5. Обработка отклонений от регулярных последовательностей (РММХ, РРго, р2 и РЗ). Механизм предсказания также довольно хорошо справляется с обработкой почти регулярных последовательностей или отклонений от регулярной последовательности. Он не только заучивает, как выглядит регулярная последовательность, он также изучает, какие существуют отклонения от нее. Если отклонения все время одни и те же, тогда он будет помнить, что идет после отклонения, и оно будет стоить толко одно неправильное предсказание.

Пример

000111000111000111000101110001110 0011100010111000

в этой последовательности О означает не-переход, а 1 - переход. Механизм предсказания делает вывод, что повторяющаяся последовательность равна 000111. Первое отклонение - это неожиданный О, который отмечен знаком . После этого следующие три перехода могут быть неправильно предсказаны, потому что механизм предсказания еще не знает, что идет после 0010, 0101 и 1011. После одного или двух таких отклонений механизм предсказания делается вывод, что после 0010 идет 1, после 0101 идет 1, а после 1011 идет 1. Это означает, что после двух отклонений одного и того же вида, механизм предсказания точно знает как их обрабатывать, допуская только одно неправильное предсказание.

Механизм предсказания очень эффективени, когда происходит смена одной регулярной последовательности на другую. Если, например, первоначально была последовательность 000111 (с периодом 6), которая повторялась много раз, потом последовательность 01 (период 2) - много раз, а затем произошел возврат снова на последовательность 000111, в этом случае механизм не должен снова запоминать последовательность 000111, так как счетчики, которые были использованы для этой последовательности, остались в неприкосновенности. После нескольких смен последовательностей с одной на другую, механизм также предсказывает, как обрабатывать изменения ценой только одного неправильного предсказания во время переключения одной последовательности на другую.

6.22.2.6. Последовательности, не предсказываемые совершенно (РММХ, РРго, Р2 и РЗ). Простейшая последовательность, которая не может быть предсказана совершенно, -это переход, который совершается каждый 6-й раз. Рассмотрим последовательность:

000001000001000001 аЬ аЬ аЬ

За последовательностями 0000 следует О в позициях, помеченных а, и 1, в позициях, Помеченных Ь. Комбинация аЬ влияет на счетчик с номером О, который постоянно увеличивает и уменьшает свое значение. Если счетчик О был вначале равен О или 1, тогда его значение будет колебаться между О и 1. Это приведет к неправильному предсказанию

в П03ИЩ1И Ь. Если счетчик О был в самом начале равен 3, тогда его значение будет изменяться в пределах 2 и 3, что приведет к неправильному предсказанию в позиции а. Худший случай - когда его состояние было в начале равно 2. Он будет изменяться в пределах 1 - 2, что приведет к неправильному предсказанию в обоих позициях. (Это аналогично худшему случаю для Р1, объясненному выше). Какая ситуация получится, зависит от предыдущих значений элемента ВТВ до того, как он был зарезервирован. Но это проконтролировать невозможно, так как элементы ВТВ выбираются случайно.

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

6.22.2.7. Полностью случайные последовательности (РММХ, РРго, Р2 и РЗ). Способность распознавания последовательностей имеет изъян в случае полностью случайных нерегулярных последовательностей.

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

Таблица 6.7. «Отношение успешных предсказаний к неуспешным для полностью

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

6 22 2.8. Короткие циклы (РММХ). Предсказание переходов ненадежно в коротких циклах, так как у механизма распознавания последовательностей нет времени, чтоОь

Глава 6. Оптимизация для процессоров семейства Pentium

обновить свои данные перед очередной встречей с командой перехода. Это означает, простые последовательности, которые в обычном случае были бы предсказаны coi шенно, не будут распознанны. И наоборот, некоторые последовательности, кото] в обычном случае не были бы распознаны, будут предсказаны в коротком цикле. Наг мер, цикл, который всегда повторяется 6 раз, имел бы последовательность 111110 инструкции ветвления в начале цикла. В этой последовательности было бы одно или неправильных предсказаний за итерацию, но в коротком цикле не будет ни одного. То самое касается цикла, который повторяется 7 раз. С другим количеством повторе предсказуемость будет еще хуже в коротких циклах. Это означает, что количество вторений, равное 6 или 7, более предпочтительно для коротких циклов. Для оптимиза следует развернуть цикл, сделав его тело больше.

Чтобы узнать, подпадает ли цикл на РММХ под действие вышеизложенных npai можно подсчитать количество инструкций в цикле. Если количество равно 6 или мень тогда цикл является коротким. Если инструкций 7 и больше - распознавание послед( тельностей будет работать нормально. Довольно странно, что крличество тактов, к( рое требуется для выполнения инструкций, не играет роли, так же как, и спариваемс инструкций и вызываемые ими задержки. Сложные целочисленные инструкции при i счете не учитываются. В цикле может быть много таких инструкций, и он будет себя ти как короткий. Сложная целочисленная инструкция - это не спариваемая целочис: пая инструкция, которая всегда требует больше одного такта. Сложные инструк с плавающей запятой и инструкции ММХ выполняются одна за другой. Следует пс мать, что это правило выведено эвристическим путем и не на 100% надежно Мо: самостоятельно провести тестирование, используя датчик качества (регистр 35) PMI чтобы подсчитать количество неправильно предсказанных переходов. Результаты те( также не могут быть полностью надежны, потому что предсказания переходов зав1 от истории элемента ВТВ до начала эксперимента.

Короткие циклы на РРго, Р2 и РЗ предсказываются нормально, каждая итерг занимает минимум два цикла.

6.22.2.9. Относительные переходы и вызовы (РММХ, РРго, Р2 и РЗ). Распознавг последовательностей не работает в случае относительных переходов и вызовов, а ВТ1 может запомнить больше одного адреса назначения для косвенного вызова. Предок; вается переход к тому же адресу, что и в предыдущий раз.

6.22.2.10. Инструкции JECXZ и LOOP (РММХ). На РММХ распознавание послед тельностей не работает с этими двумя инструкциями, просто в качестве предсказг выбирается то, что произошло в последний раз. Этих двух инструкций следует избе в критическом коде для РММХ (на РРго, Р2 и РЗ предсказания осуществляются с пс Щью распознавания последовательностей, но специальные инструкции циклов все рс проигрывают по сравнению с комбинацией DEC ЕСХ / JNZ).