Почему jnz требует 2 цикла для завершения во внутреннем цикле

Я на IvyBridge. Я обнаружил, что производительность jnz несовместима во внутреннем и внешнем циклах.

Следующая простая программа имеет внутренний цикл фиксированного размера 16:

global _start
_start:
    mov rcx, 100000000
.loop_outer:
    mov rax,    16

.loop_inner:
    dec rax
    jnz .loop_inner

    dec rcx
    jnz .loop_outer

    xor edi, edi
    mov eax, 60
    syscall

perf инструмент показывает, что внешний цикл выполняется 32c / iter. Это предполагает, что jnz требуется 2 цикла для завершения.

Затем я ищу в таблице инструкций Агнера, условный переход имеет 1-2 «обратную пропускную способность» с комментарием «быстро, если нет перехода».

На данный момент я начинаю верить, что вышеупомянутое поведение каким-то образом ожидаемо. Но почему jnz во внешнем цикле требуется только 1 цикл для завершения?

Если я полностью удалю часть .loop_inner, внешний цикл выполнит 1c / iter. Поведение выглядит непоследовательным.

Что мне здесь не хватает?

Отредактируйте для получения дополнительной информации:

perf результаты для указанной выше программы с помощью команды:

perf stat -ecycles,branches,branch-misses,lsd.uops,uops_issued.any -r4 ./a.out

is:

 3,215,921,579      cycles                                                        ( +-  0.11% )  (79.83%)
 1,701,361,270      branches                                                      ( +-  0.02% )  (80.05%)
        19,212      branch-misses             #    0.00% of all branches          ( +- 17.72% )  (80.09%)
        31,052      lsd.uops                                                      ( +- 76.58% )  (80.09%)
 1,803,009,428      uops_issued.any                                               ( +-  0.08% )  (79.93%)

perf результат эталонного случая:

global _start
_start:
    mov rcx, 100000000
.loop_outer:
    mov rax,    16
    dec rcx
    jnz .loop_outer

    xor edi, edi
    mov eax, 60
    syscall

is:

   100,978,250      cycles                                                        ( +-  0.66% )  (75.75%)
   100,606,742      branches                                                      ( +-  0.59% )  (75.74%)
         1,825      branch-misses             #    0.00% of all branches          ( +- 13.15% )  (81.22%)
   199,698,873      lsd.uops                                                      ( +-  0.07% )  (87.87%)
   200,300,606      uops_issued.any                                               ( +-  0.12% )  (79.42%)

Итак, причина в основном ясна: LSD по какой-то причине перестает работать во вложенном случае. Уменьшение размера внутреннего цикла немного снизит медлительность, но не полностью.

Обыскивая «руководство по оптимизации» Intel, я обнаружил, что LSD не будет работать, если цикл содержит «более восьми взятых ветвей». Это как-то объясняет поведение.


person user10865622    schedule 12.01.2019    source источник
comment
16 итераций должно быть достаточно, чтобы выход из внутреннего цикла предсказывал правильно (и вы, вероятно, увидите намного более медленное время для этого), но вы все равно должны проверить. (~ 23 итерации - это когда он перестает правильно предсказывать на Skylake в прошлый раз, когда я тестировал). Длительные жесткие циклы - это своего рода особый случай, специально обрабатываемый интерфейсом с использованием буфера цикла. Это могло быть поражение буфера цикла (LSD); проверьте счетчики на lsd.uops против uops_issued.any. (Я не думаю, что LSD может обрабатывать вложенные циклы, поэтому в лучшем случае все мопы внутреннего цикла исходят из LSD, но может быть меньше)   -  person Peter Cordes    schedule 12.01.2019
comment
Также стоит попытаться выровнять внешний цикл по 32. Это должно поместить все (внутренний + внешний) в одну и ту же строку uop-cache. Декодеры не будут объединять макросы обратно в dec / jnz на IvB (или на самом деле, если они попадут в декодеры в той же группе до 4 мопов), только на HSW и более поздних версиях, поэтому имейте в виду, что ваш внешний цикл, вероятно, имеет отдельные uops для dec и jnz. Однако это не прямая причина того, что вы видите. Кстати, как вы измерили стоимость внешнего цикла JNZ с присутствующим внутренним циклом? Или вы действительно имели в виду один длительный цикл без вложенности для 1c / iter?   -  person Peter Cordes    schedule 12.01.2019
comment
@PeterCordes Спасибо, ты прав, причина в ЛСД. Смотрите мою правку. Выравнивание не имеет значения, и предсказание ветвлений отлично работает в обоих случаях. Я согласен, если вы напишете эти комментарии в качестве ответа.   -  person user10865622    schedule 12.01.2019
comment
@PeterCordes Я все еще сомневаюсь: LSD - это то же самое, что и петлевой буфер в книге Агнера? Выглядит то же самое, но если это так, утверждение Агнера о буфере цикла не имеет измеримого эффекта в тех случаях, когда кеш uop не является узким местом ... неверно? Потому что это, безусловно, измеримый эффект, и кэш uop не является узким местом, потому что его емкость составляет ~ 1,5 КБ.   -  person user10865622    schedule 12.01.2019
comment
Да, Агнер называет это буфером обратной связи. Он утверждает, что добавление LSD в дизайн не ускоряет никакого кода. Но да, это кажется неправильным для очень плотных циклов, очевидно, что SnB / IvB действительно нуждается в буфере цикла для выдачи или выполнения циклов 1c / iter. Если только узкое место микроархитектуры не связано с извлечением мопов из кэша мопов после разветвления, в этом случае его предостережение покрывает это.   -  person Peter Cordes    schedule 12.01.2019
comment
@PeterCordes, я вижу. И я думаю, это не только для SnB / IvB, но также для Haswell и Skylake. Его таблица инструкций по-прежнему показывает, что у выбранной ветви пропускная способность 1-2 для Haswell и Skylake,   -  person user10865622    schedule 12.01.2019


Ответы (2)


TL; DR: кажется, что DSB может доставлять только один шаг перехода внутреннего цикла каждый второй цикл. Также переключатели DSB-MITE составляют до 9% времени выполнения.


Введение - Часть 1: Понимание событий производительности LSD

Сначала я расскажу, когда происходят LSD.UOPS и LSD.CYCLES_ACTIVE события производительности, а также некоторые особенности LSD на микроархитектурах IvB и SnB. Как только мы заложим эту основу, мы сможем ответить на вопрос. Для этого мы можем использовать небольшие фрагменты кода, специально разработанные для точного определения момента возникновения этих событий.

По документации:

LSD.UOPS: Количество Uops, доставленных LSD.
LSD.CYCLES_ACTIVE: Циклы Uops, доставленных LSD, но не поступивших от декодера.

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

Каждый из следующих тестов начинается с комментария, который содержит название теста. Все числа нормализованы на итерацию, если не указано иное.

; B1
----------------------------------------------------
    mov rax, 100000000
.loop:
    dec rax
    jnz .loop
----------------------------------------------------
Metric                             |  IvB   |  SnB
----------------------------------------------------
cycles                             |  0.90  |  1.00
LSD.UOPS                           |  0.99  |  1.99
LSD.CYCLES_ACTIVE                  |  0.49  |  0.99
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE   |  0.00  |  0.00
UOPS_ISSUED.STALL_CYCLES           |  0.43  |  0.50

Обе инструкции в теле цикла объединены в один uop. На IvB и SnB есть только один порт выполнения, который может выполнять инструкции перехода. Следовательно, максимальная пропускная способность должна составлять 1 центнер / куб. Однако по какой-то причине IvB на 10% быстрее.

Согласно Снижается ли производительность при выполнении циклов, число uop которых не кратно ширине процессора?, LSD в IvB и SnB не может выдавать мопс через границы тела цикла, даже если есть свободные места для задач. Поскольку цикл содержит один муп, мы ожидаем, что LSD будет выдавать один муп за цикл и что LSD.CYCLES_ACTIVE должно быть примерно равно общему количеству циклов.

На IvB LSD.UOPS соответствует ожиданиям. То есть ЛСД будет выдавать один мкоп за цикл. Обратите внимание: поскольку количество циклов равно количеству итераций, которое равно количеству мопов, мы можем эквивалентно сказать, что LSD выдает один моп за итерацию. По сути, большинство казненных бандитов были выпущены ЛСД. Однако LSD.CYCLES_ACTIVE составляет примерно половину числа циклов. Как это возможно? В таком случае, не должна ли ЛСД выдавать только половину от общего числа мопов? Я думаю, что здесь происходит то, что цикл по сути разворачивается дважды, и за цикл выдается два мопа. Тем не менее, только один муп может быть выполнен за цикл, но RESOURCE_STALLS.RS равно нулю, что указывает на то, что RS никогда не заполняется. Однако RESOURCE_STALLS.ANY составляет примерно половину количества циклов. Собирая все это вместе, кажется, что LSD фактически выдает 2 мопа каждый второй цикл и что есть некоторые структурные ограничения, которые достигаются каждый второй цикл. CYCLE_ACTIVITY.CYCLES_NO_EXECUTE подтверждает, что в RS всегда есть хотя бы один моп чтения в любом заданном цикле. Следующие эксперименты покажут условия, при которых происходит раскрутка.

На SnB LSD.UOPS показывает, что из LSD было выпущено вдвое больше мопов. Также LSD.CYCLES_ACTIVE указывает, что LSD был активен большую часть времени. CYCLE_ACTIVITY.CYCLES_NO_EXECUTE и UOPS_ISSUED.STALL_CYCLES такие же, как на IvB. Следующие ниже эксперименты помогут понять, что происходит. Кажется, что измеренное LSD.CYCLES_ACTIVE равно реальному _17 _ + _ 18_. Следовательно, чтобы получить реальный LSD.CYCLES_ACTIVE, нужно вычесть RESOURCE_STALLS.ANY из измеренного LSD.CYCLES_ACTIVE. То же самое и с LSD.CYCLES_4_UOPS. Реальный LSD.UOPS можно рассчитать следующим образом:

LSD.UOPS измерено = LSD.UOPS реальное + ((LSD.UOPS измерено / LSD.CYCLES_ACTIVE измерено) * _ 28_)

Таким образом,

LSD.UOPS реальный = LSD.UOPS измеренный - ((LSD.UOPS измеренный / LSD.CYCLES_ACTIVE измеренный) * RESOURCE_STALLS.ANY)
= LSD.UOPS измерено * (1 - (_35 _ / _ 36_ измерено))

Для всех тестов, которые я проводил на SnB (в том числе не показанных здесь), эти настройки точны.

Обратите внимание, что RESOURCE_STALLS.RS и RESOURCE_STALLS.ANY в SnB такие же, как IvB. Таким образом, кажется, что LSD работает одинаково, что касается этого конкретного теста, на IvB и SnB, за исключением того, что события LSD.UOPS и LSD.CYCLES_ACTIVE подсчитываются по-разному.

; B2
----------------------------------------------------
    mov rax, 100000000
    mov rbx, 0
.loop:
    dec rbx
    jz .loop
    dec rax
    jnz .loop
----------------------------------------------------
Metric                             |  IvB   |  SnB
----------------------------------------------------
cycles                             |  1.98  |  2.00
LSD.UOPS                           |  1.92  |  3.99
LSD.CYCLES_ACTIVE                  |  0.94  |  1.99
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE   |  0.00  |  0.00
UOPS_ISSUED.STALL_CYCLES           |  1.00  |  1.00

В B2 на итерацию приходится 2 мопа, и оба являются прыжками. Первый никогда не берется, поэтому остается только один цикл. Мы ожидаем, что он будет работать со скоростью 2 цента / л, что действительно так. LSD.UOPS показывает, что большинство мопов было выпущено из LSD, но LSD.CYCLES_ACTIVE показывает, что LSD был активен только половину времени. Это означает, что цикл не был развернут. Таким образом, кажется, что разворачивание происходит только тогда, когда в цикле есть один муп.

; B3
----------------------------------------------------
    mov rax, 100000000
.loop:
    dec rbx
    dec rax
    jnz .loop
----------------------------------------------------
Metric                             |  IvB   |  SnB
----------------------------------------------------
cycles                             |  0.90  |  1.00
LSD.UOPS                           |  1.99  |  1.99
LSD.CYCLES_ACTIVE                  |  0.99  |  0.99
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE   |  0.00  |  0.00
UOPS_ISSUED.STALL_CYCLES           |  0.00  |  0.00

Здесь также есть 2 мупа, но первый - это однотактный муп ALU, не связанный с мопом перехода. B3 помогает нам ответить на следующие два вопроса:

  • Если целью прыжка не является вертолет, будут ли LSD.UOPS и LSD.CYCLES_ACTIVE засчитываться дважды на SnB?
  • Если цикл содержит 2 мупа, из которых только один является прыжком, разворачивает ли LSD цикл?

B3 показывает, что ответ на оба вопроса - «Нет».

UOPS_ISSUED.STALL_CYCLES предполагает, что LSD остановит только один цикл, если он выдает два прыжка за один цикл. В B3 этого никогда не происходит, поэтому там нет киосков.

; B4
----------------------------------------------------
    mov rax, 100000000
.loop:
    add rbx, qword [buf]
    dec rax
    jnz .loop
----------------------------------------------------
Metric                             |  IvB   |  SnB
----------------------------------------------------
cycles                             |  0.90  |  1.00
LSD.UOPS                           |  1.99  |  2.00
LSD.CYCLES_ACTIVE                  |  0.99  |  1.00
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE   |  0.00  |  0.00
UOPS_ISSUED.STALL_CYCLES           |  0.00  |  0.00

У B4 есть дополнительная изюминка; он содержит 2 мопа в объединенном домене, но 3 мопа в объединенном домене, потому что инструкция load-ALU не используется в RS. В предыдущих тестах не было микроплавких мопов, только макро-слитые мопы. Цель здесь - увидеть, как ЛСД обращается с микрочастицами мопов.

LSD.UOPS показывает, что два мопа инструкции load-ALU израсходовали один слот выдачи (объединенный моп перехода занимает только один слот). Кроме того, поскольку LSD.CYCLES_ACTIVE равно cycles, разворачивания не произошло. Пропускная способность цикла соответствует ожиданиям.

; B5
----------------------------------------------------
    mov rax, 100000000
.loop:
    jmp .next
.next:
    dec rax
    jnz .loop
----------------------------------------------------
Metric                             |  IvB   |  SnB
----------------------------------------------------
cycles                             |  2.00  |  2.00
LSD.UOPS                           |  1.91  |  3.99
LSD.CYCLES_ACTIVE                  |  0.96  |  1.99
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE   |  0.00  |  0.00
UOPS_ISSUED.STALL_CYCLES           |  1.00  |  1.00

B5 - последний тест, который нам понадобится. Он похож на B2 тем, что содержит два мупа ветвления. Однако один из прыжков в B5 - это безусловный прыжок вперед. Результаты идентичны B2, что указывает на то, что не имеет значения, является ли команда перехода условной или нет. Это также имеет место, если первый переход является условным, а второй - нет.

Введение - Часть 2: Прогнозирование ветвлений в LSD

LSD - это механизм, реализованный в очереди uop (IDQ), который может улучшить производительность и снизить энергопотребление (следовательно, уменьшается тепловыделение). Это может улучшить производительность, потому что некоторые ограничения, существующие в интерфейсе, могут быть ослаблены в очереди uop. В частности, на SnB и IvB максимальная пропускная способность путей MITE и DSB составляет 4 uop / c, но в байтах это 16B / c и 32B / c соответственно. Пропускная способность очереди uop также составляет 4uops / c, но не имеет ограничений на количество байтов. Пока LSD выдает uops из очереди uop, интерфейс (т. Е. Блоки выборки и декодирования) и даже ненужную логику после IDQ можно отключить. До Nehalem LSD был реализован в модуле IQ. Начиная с Haswell, LSD поддерживает циклы, содержащие ошибки из MSROM. LSD в процессорах Skylake отключен, потому что, видимо, глючит.

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

Мы уже знаем, что блок предсказания ветвлений (BPU) на SnB и более поздних версиях может правильно предсказать, когда условная ветвь цикла проваливается, когда общее количество итераций не превышает некоторого небольшого числа, после чего BPU предполагает, что цикл будет повторяться. навсегда. Если LSD использует сложные возможности BPU для прогнозирования завершения заблокированного цикла, он должен иметь возможность правильно прогнозировать те же самые случаи. Также возможно, что LSD использует свой собственный предсказатель ветвления, который потенциально намного проще. Давайте разберемся.

mov rcx, 100000000/(IC+3)
.loop_outer:
    mov rax, IC
    mov rbx, 1 

.loop_inner:
    dec rax
    jnz .loop_inner

    dec rcx
    jnz .loop_outer

Пусть OC и IC обозначают количество внешних итераций и количество внутренних итераций соответственно. Они связаны следующим образом:

OC = 100000000 / (_ 57_ + 3) где IC> 0

Для любого данного IC общее количество вышедших на пенсию мопов одинаково. Кроме того, количество мопов в объединенном домене равно количеству мопов в несвязанном домене. Это приятно, потому что действительно упрощает анализ и позволяет нам проводить честное сравнение производительности между разными значениями IC.

По сравнению с кодом из вопроса, есть дополнительная инструкция mov rbx, 1, так что общее количество мопов во внешнем цикле составляет ровно 4 мопа. Это позволяет нам использовать событие производительности LSD.CYCLES_4_UOPS в дополнение к LSD.CYCLES_ACTIVE и BR_MISP_RETIRED.CONDITIONAL. Обратите внимание: поскольку существует только один порт выполнения ветвления, каждая итерация внешнего цикла занимает не менее 2 циклов (или, согласно таблице Агнера, 1-2 цикла). См. Также: Может ли LSD выпустить uOPs со следующей итерации обнаруженного цикла?.

Общее количество прыжков составляет:

OC + _66 _ * _ 67_ = 100 млн / (_ 68_ + 3) + IC * 100 млн / (_ 70_ + 3)
= 100 млн (IC + 1) / (_ 72_ + 3)

Предполагая, что максимальная пропускная способность перехода составляет 1 за цикл, оптимальное время выполнения составляет 100 млн (IC + 1) / (_ 74_ + 3) циклов. На IvB мы можем вместо этого использовать максимальную пропускную способность перехода 0,9 / c, если мы хотим быть строгими. Было бы полезно разделить это на количество внутренних итераций:

OPT = (100M (IC + 1) / (_ 77_ + 3)) / (100M_78 _ / (_ 79_ + 3)) =
100M (IC + 1) * (IC + 3) / (IC + 3) * 100MIC =
(IC + 1) / _ 85_ = 1 + 1 / IC

Следовательно, 1 ‹OPT‹ = 1,5 для IC> 1. Человек, разрабатывающий ЛСД, может использовать это для сравнения различных дизайнов ЛСД. Мы также скоро воспользуемся этим. Другими словами, оптимальная производительность достигается, когда общее количество циклов, деленное на общее количество прыжков, равно 1 (или 0,9 на IvB).

Если предположить, что прогноз для двух скачков независим и с учетом того, что jnz .loop_outer легко предсказуемо, производительность зависит от прогноза jnz .loop_inner. При ошибочном прогнозе, который изменяет управление на моп за пределами замкнутого цикла, LSD завершает цикл и пытается обнаружить другой цикл. LSD можно представить как конечный автомат с тремя состояниями. В одном состоянии LSD ищет зацикленное поведение. Во втором состоянии LSD изучает границы и количество итераций цикла. В третьем состоянии LSD воспроизводит цикл. Когда цикл существует, состояние меняется с третьего на первое.

Как мы узнали из предыдущей серии экспериментов, на SnB будут возникать дополнительные LSD-события, когда возникают проблемы, связанные с серверной частью. Так что цифры нужно понимать соответственно. Обратите внимание, что случай, когда IC = 1, не тестировался в предыдущем разделе. Об этом и пойдет речь здесь. Напомним также, что как на IvB, так и на SnB внутренний цикл может разворачиваться. Внешний цикл никогда не будет развернут, потому что он содержит более одного мупа. Кстати, LSD.CYCLES_4_UOPS работает как положено (извините, никаких сюрпризов).

На следующих рисунках показаны необработанные результаты. Я показал результаты только до IC = 13 и IC = 9 на IvB и SnB соответственно. В следующем разделе я расскажу, что происходит с большими значениями. Обратите внимание, что когда знаменатель равен нулю, значение не может быть вычислено и поэтому оно не отображается.

uop metrics  показатели цикла

LSD.UOPS/100M - это отношение количества мопов, выпущенных LSD, к общему количеству мопов. LSD.UOPS/OC - среднее количество мопов, выпущенных LSD за внешнюю итерацию. LSD.UOPS/(OC*IC) - среднее количество мопов, выпущенных LSD за внутреннюю итерацию. BR_MISP_RETIRED.CONDITIONAL/OC - это среднее количество исключенных условных ветвей, которые были неверно предсказаны на внешнюю итерацию, которое явно равно нулю как для IvB, так и для SnB для всех IC.

Для IC = 1 на IvB все мопы были выпущены из LSD. Внутренняя условная ветвь всегда не берется. Показатель LSD.CYCLES_4_UOPS/LSD.CYCLES_ACTIVE, показанный на втором рисунке, показывает, что во всех циклах, в которых LSD активен, LSD выдает 4 мопа за цикл. Из предыдущих экспериментов мы узнали, что когда LSD выдает 2 мопы прыжка в одном цикле, он не может выдавать мопы прыжка в следующем цикле из-за некоторых структурных ограничений, поэтому он остановится. LSD.CYCLES_ACTIVE/cycles показывает, что LSD останавливается (почти) каждый второй цикл. Мы ожидаем, что для выполнения внешней итерации потребуется около 2 циклов, но cycles показывает, что это занимает около 1,8 цикла. Вероятно, это связано с пропускной способностью 0,9 на IvB, которую мы видели ранее.

Случай IC = 1 на SnB аналогичен за исключением двух вещей. Во-первых, внешний цикл, как и ожидалось, занимает 2 цикла, а не 1,8. Во-вторых, количество всех трех LSD-событий вдвое больше ожидаемого. Их можно настроить, как описано в предыдущем разделе.

Прогнозирование ветвлений особенно интересно, когда IC> 1. Разберем подробнее случай IC = 2. LSD.CYCLES_ACTIVE и LSD.CYCLES_4_UOPS показывают, что примерно в 32% всех циклов LSD активен, а в 50% этих циклов LSD выдает 4 мопа за цикл. Так что либо есть неверные предсказания, либо LSD занимает много времени в состоянии обнаружения петель или в состоянии обучения. Тем не менее, _109 _ / (_ 110 _ * _ 111_) составляет около 1,6, или, другими словами, _112 _ / _ 113_ равно 1,07, что близко к оптимальной производительности. Трудно понять, какие мопы выдают группами по 4 из LSD, а какие - группами меньше 4 из LSD. Фактически, мы не знаем, как подсчитываются ЛСД-события при наличии ошибочных прогнозов ЛСД. Возможное развертывание добавляет еще один уровень сложности. Счетчики LSD-событий можно рассматривать как верхнюю границу полезных мопов, выпущенных LSD, и циклов, в которых LSD выдавал полезные мопы.

По мере увеличения IC и LSD.CYCLES_ACTIVE, и LSD.CYCLES_4_UOPS снижаются, и производительность ухудшается медленно, но стабильно (помните, что _117 _ / (_ 118 _ * _ 119_) следует сравнивать с OPT). Это как если бы последняя итерация внутреннего цикла была неверно предсказана, но ее штраф за неверное предсказание увеличивается с IC. Обратите внимание, что BPU всегда правильно предсказывает количество итераций внутреннего цикла.


Ответ

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

mov rcx, 100000000/(IC+2)
.loop_outer:
    mov rax, IC

.loop_inner:
    dec rax
    jnz .loop_inner

    dec rcx
    jnz .loop_outer

По сути, это то же самое, что и код из вопроса. Единственное отличие состоит в том, что количество внешних итераций регулируется для поддержания того же количества динамических мопов. Обратите внимание, что LSD.CYCLES_4_UOPS бесполезен в этом случае, потому что LSD никогда не будет выдавать 4 мопов в любом цикле. Все следующие цифры относятся только к IvB. Впрочем, не беспокойтесь, чем отличается SnB, в тексте будет упоминаться.

введите описание изображения здесь

Когда IC = 1, cycles / jumps составляет 0,7 (1,0 на SnB), что даже ниже 0,9. Я не знаю, как достигается такая пропускная способность. Производительность снижается с увеличением значения IC, что коррелирует с уменьшением активных циклов LSD. Когда IC = 13-27 (9-27 на SnB), LSD выдает ноль мопов. Я думаю, что в этом диапазоне LSD считает, что влияние на производительность из-за неправильного прогнозирования последней внутренней итерации превышает некоторый порог, он решает никогда не блокировать цикл и запоминает свое решение. Когда IC ‹13, LSD кажется агрессивным и, возможно, он считает петлю более предсказуемой. Для IC> 27 количество активных циклов LSD медленно растет, и это коррелирует с постепенным улучшением производительности. Хотя это и не показано на рисунке, поскольку IC вырастает далеко за пределы 64, большинство мопов будет исходить от LSD, а cycles / jumps установится на 0,9.

Особенно полезны результаты для диапазона IC = 13-27. Циклы задержек при отправке составляют примерно половину общего количества циклов, а также равны циклам задержек при отправке. Именно по этой причине внутренний цикл выполняется на скорости 2.0c / iter; потому что переходы внутреннего цикла вырабатываются / отправляются каждый второй цикл. Когда LSD не активен, мопы могут исходить от DSB, MITE или MSROM. Поддержка микрокода не требуется для нашего цикла, поэтому, вероятно, существует ограничение либо в DSB, либо в MITE, либо в обоих. Мы можем продолжить исследование, чтобы определить, где ограничения, используя события производительности внешнего интерфейса. Я сделал это, и результаты показывают, что около 80-90% всех мопов поступают от DSB. Сам DSB имеет много ограничений, и кажется, что петля затрагивает одно из них. Кажется, что DSB требуется 2 цикла, чтобы выполнить прыжок, который нацеливается на себя. Кроме того, для всего диапазона IC остановки из-за переключения MITE-DSB составляют до 9% всех циклов. Опять же, причина этих переключателей связана с ограничениями самого DSB. Обратите внимание, что до 20% доставляются с пути MITE. Предполагая, что мопы не превышают пропускную способность 16B / c пути MITE, я думаю, что цикл выполнялся бы на 1c / iter, если бы DSB не было.

На приведенном выше рисунке также показана частота ошибочного предсказания BPU (на итерацию внешнего цикла). На IvB это ноль для IC = 1-33, кроме случаев, когда IC = 21, 0-1, когда IC = 34-45, и ровно 1, когда IC> 46. На SnB это ноль для IC = 1-33 и 1 в противном случае.

person Hadi Brais    schedule 19.01.2019
comment
С IC = 1 мы можем не получить макрофузию, потому что только HSW и более поздние версии могут сделать 2 макрослияния в одной группе декодирования. Но если ветвь внутреннего цикла выполняется хотя бы один раз, тогда, возможно, внешний цикл dec / jnz повторно декодируется, когда внутренний цикл окончательно завершается, вместо сохранения результата декодирования из невыполненного пути. Это все еще не объясняет, как IC = 1 может приводить к более чем 1 скачку за цикл, но это потенциальная качественная разница. - person Peter Cordes; 19.01.2019
comment
@PeterCordes Я был удивлен, увидев, что uop магазина в B4, по-видимому, использует 2 слота для выдачи, что означает, что он не ламинируется, даже если он не использует режим индексированной адресации. Вы знаете, задокументировано ли это Intel? Я что-то упускаю? - person Hadi Brais; 19.01.2019
comment
Команды с непосредственным операндом и операндом, относящимся к RIP, никогда не могут слиться воедино, даже в декодерах. Так что нет никакого расслоения, и я думаю, это задокументировано в другом месте в руководстве Intel. Это относится и к mov-магазинам, и к test или cmp [rel foo], imm. Примеры см. В Режимах микрослияния и адресации. IIRC, нагрузка + рабочая часть add [rel foo], imm также не может предохранить микропредохранитель. - person Peter Cordes; 19.01.2019

(Частичный ответ / предположение, что я не закончил писать до того, как Хади опубликовал подробный анализ; некоторые из них продолжаются из комментариев)

Утверждение Агнера о том, что буфер цикла не имеет измеримого эффекта в тех случаях, когда кэш uop не является узким местом ... неверно? Потому что это, безусловно, измеримый эффект, и кэш uop не является узким местом, потому что его емкость составляет ~ 1,5 КБ.

Да, Агнер называет это буфером обратной связи. Он утверждает, что добавление LSD в дизайн не ускоряет код. Но да, это кажется неправильным для очень узких циклов, по крайней мере, для вложенных циклов. По-видимому, SnB / IvB действительно нуждается в буфере цикла для выдачи или выполнения циклов 1c / iter. Если только узкое место микроархитектуры не связано с извлечением мопов из кэша мопов после разветвления, в этом случае его предостережение покрывает это.

Существуют случаи, когда чтение кэша UOP может стать узким местом, кроме промахов в кэше uop. например если мопы упакованы не очень хорошо из-за эффектов выравнивания, или если они используют большие немедленные действия и / или смещения, которые требуют дополнительных циклов для чтения из кэша мопов. Дополнительные сведения об этих эффектах см. В разделе Sandybridge в руководстве Agner Fog по uarch. Ваше предположение, что емкость (до 1,5 тыс. Уп, если они упакованы идеально) - единственная причина, по которой она может быть медленной, очень неверно.

Кстати, обновление микрокода для Skylake полностью отключило LSD, чтобы исправить ошибку частичного слияния регистров, erratum SKL150 1, и это фактически не имело большого эффекта, за исключением случаев, когда крошечный цикл охватывает границу 32 Б и требует 2 строки кэша.

Но Агнер перечисляет JMP rel8/32 и принимает пропускную способность JCC как 1-2 цикла на HSW / SKL, по сравнению с 2 циклами на IvB. Так что кое-что о взятых ветках, возможно, ускорилось после IvB, кроме самого LSD.

Могут быть некоторые части ЦП, отличные от LSD, которые также имеют специальный случай для длительных крошечных циклов, который позволяет им выполнять 1 взятый прыжок за такт на Haswell и более поздних версиях. Я не проверял, какие условия вызывают пропускную способность ветки за 1 или 2 цикла на HSW / SKL. Также обратите внимание, что перед обновлением микрокода Агнер измерил ошибку SKL150.


сноска 1: см. Как именно работают частичные регистры на Haswell / Skylake? Написание AL, похоже, ложно зависит от RAX, а AH несовместим, и обратите внимание, что SKX и Kaby Lake поставляются с микрокодом, который уже включает это. Наконец, он снова включен в процессорах, таких как CannonLake / Ice Lake, что исправило ошибочную аппаратную логику, так что LSD можно безопасно снова включить.

(Раньше я думал, что Coffee Lake снова включил LSD, но похоже, что нет - wikichip прямо говорит, что он все еще отключен, поэтому я думаю, что это исправляет некоторые более ранние отчеты о том, что он был повторно включен. CFL исправила уязвимости L1TF и Meltdown, тем не менее, делая программное смягчение ненужным специально для этих уязвимостей.)

person Peter Cordes    schedule 19.01.2019
comment
Проголосовали. Ваш ответ и ответ Хади очень хороши, я уже принял ответ Хади до вашей публикации, извините за это. Я перечитал часть кэша uop в книге Агнера, но меня больше смущает организация кэша uop. Агнер показывает: один и тот же фрагмент кода может иметь несколько записей в кэше uop, если он имеет несколько записей перехода. Как в коде может быть несколько записей? В моем коде счетчик inner_loop равен 16, раньше я думал, что он имеет только одну запись uop - объединенный макрос jnz. Агнер имеет в виду, что в нем 16 записей? - person user10865622; 19.01.2019
comment
@ user10865622: Нет, в этом цикле одна и та же точка входа была изменена 16 раз. Представьте тело цикла с точкой входа первой итерации в середине всего тела, как для стратегии перехода к стратегии условий цикла, которую gcc -Os использует для циклов, которые, возможно, потребуется выполнить 0 раз. (Почему циклы всегда компилируются в стиль do ... while (прыжок хвостом)?). ЦП может закончить повторное декодирование с начала цикла и создать новую строку кэша uop, возможно, без удаления оригинала (сразу / вообще). - person Peter Cordes; 19.01.2019
comment
@ user10865622: Я думаю, что Хади более прямо отвечает на конкретный вопрос, в то время как мой обращается к дополнительным материалам из комментариев, поэтому вы должны оставить галочку принятия на Хади. (SO позволяет вам перемещать его, но нет способа принять более одного, что было бы полезно в некоторых случаях.) - person Peter Cordes; 19.01.2019
comment
Если я правильно понимаю ваш комментарий, ЦП имеет возможность различать инструкцию, следующую за ветвью, и инструкцию, следующую за ветвью. В первом случае будет создана новая запись, а во втором случае ЦП будет использовать существующую запись. Я прав? - person user10865622; 19.01.2019
comment
@ user10865622: Нет, я не совсем это говорю. Я не уверен, когда именно вы получите несколько строк кэша uop, содержащих одну и ту же инструкцию. Но чтобы избежать сумасшедшего переключения между декодированием и кешем uop, я думаю, что если ЦП уже выполняет декодирование из устаревших декодеров, он может только повторно проверить попадание в кеш uop при пересечении 32-байтовой границы. Или, по крайней мере, он будет декодировать + кешировать группу до 4 мопов, которые она только что декодировала. - person Peter Cordes; 19.01.2019
comment
Если в первый раз выполняются некоторые инструкции из блока, он запускается частично, первые несколько инструкций в блоке не декодируются и не кэшируются. Но затем, если вы перейдете к ним, они и последующие isns будут кэшированы в новой строке кэша uop. Декодирование происходит 4 раза за раз. Имеет смысл повторно декодировать инструкции из более ранней начальной точки и кэшировать это представление, как только ЦП видит, что выполнение иногда начинается с этого места. - person Peter Cordes; 19.01.2019
comment
Но если блок уже был кэширован, переход в его середину может попасть в эту строку кэша uop. - person Peter Cordes; 19.01.2019
comment
Ясно спасибо. Я обобщал ваш пример цикла while с неправильной точки зрения. Это больше касается некоторой проблемы с выравниванием строки кэша uop, и фактическая реализация может быть сложной. - person user10865622; 19.01.2019