Почему зависимость в итерации цикла не может быть выполнена вместе с предыдущей

Question

Я использую этот код для проверки влияния зависимости в итерации цикла на IvyBridge:

global _start
_start:
    mov rcx,    1000000000
.for_loop:          
    inc rax     ; uop A
    inc rax     ; uop B
    dec rcx     ; uop C
    jnz .for_loop   

    xor rdi,    rdi
    mov rax,    60  ; _exit(0)
    syscall

поскольку dec а также jnz будет слит с макросом до одного мопа, в моем цикле 3 мопа, они отмечены в комментариях.

uop B зависит от uop A, поэтому я думаю, что выполнение будет таким:

A C
B A C  ; the previous B and current A can be in the same cycle
B A C
...
B A C
B

Поэтому цикл может выполняться 1 цикл на итерацию.

Тем не менее perf инструмент показывает:

 2,009,704,779      cycles                
 1,008,054,984      stalled-cycles-frontend   #   50.16% frontend cycles idl

Таким образом, это 2 цикла на итерацию, и 50% времени простоя внешнего интерфейса.

Что вызвало 50% простоя фронтэнда? Почему гипотетическая схема выполнения не может быть реализована?

Answer 1

B и A образуют цепочку зависимостей, переносимую циклом. A в следующей итерации не может работать, пока не получит результат B в предыдущей.

B никогда не может работать в том же цикле, что и A: какой вход будет использовать более поздний, если предыдущий еще не дал результата?

Эта цепочка длиной 2 цикла (на одну итерацию), потому что задержка inc это 1 цикл. Это создает узкое место задержки в бэкэнде, которое не может скрыть выполнение вне очереди. (За исключением очень низкого количества итераций, где он может перекрывать его с кодом после цикла).

Так же, как если бы вы полностью развернули огромную цепочку times 102400 inc eaxнет никакого параллелизма на уровне команд для процессора, который можно найти между цепочкой команд, каждая из которых зависит от предыдущей.

Макрос сплавленный dec rcx/jnz uop не зависит от цепочки RAX и является более короткой цепочкой (всего 1 цикл на итерацию, только 1 дек с ветвлением с задержкой 1 c). Таким образом, он может работать параллельно с B или A мопс.

---

См. Мой ответ на другой вопрос, чтобы узнать больше о концепции параллелизма на уровне команд и цепочек зависимостей и о том, как процессоры используют этот параллелизм для параллельного выполнения инструкций, когда они независимы.

Микроарх PDF Agner Fog демонстрирует это на примерах из предыдущей главы: Глава 2: Выполнение не по порядку (все процессоры, кроме P1, PMMX).

---

Если вы запускаете новую 2-тактную цепочку депов на каждой итерации, она будет работать так, как вы ожидаете. Новая цепочка, отбрасывающая каждую итерацию, открыла бы параллелизм на уровне команд для ЦП, чтобы одновременно удерживать A и B от разных итераций в полете.

.for_loop:
    xor eax,eax          ; dependency-breaking for RAX
    inc rax     ; uop A
    inc rax     ; uop B
    dec rcx     ; uop C
    jnz .for_loop   

Семейство Sandybridge обрабатывает обнуление xor без исполнительного модуля, так что это все еще только 3 мопа с неиспользованным доменом в цикле, поэтому IvyBridge имеет достаточно исполнительных портов ALU для запуска всех 3 в одном цикле. Это также максимизирует интерфейс на 4 мопах слитых доменов за такт.

Или, если вы изменили A, чтобы запустить новую цепочку депонирования в RAX с какой-либо инструкцией, которая безоговорочно перезаписывает RAX без зависимости от результата inc, ты будешь в порядке.

    lea  rax, [rdx + rdx]     ; no dependency on B from last iter
    inc  rax                  ; uop B

За исключением пары инструкций с неудачной выходной зависимостью: почему имеет значение нарушение "выходной зависимости" LZCNT?

    popcnt rax, rdx        ; false dependency on RAX, 3 cycle latency
    inc  rax               ; uop B

Только на процессорах Intel popcnt, а также lzcnt/tzcnt иметь выходную зависимость без причины. Это потому, что они используют тот же модуль выполнения, что и bsf/bsr, которые оставляют место назначения неизменным, если ввод равен нулю, на процессорах Intel и AMD. Intel по-прежнему только документирует это на бумаге как неопределенное, если ввод для BSF/ BSR равен нулю, но они создают оборудование, которое реализует более строгие гарантии. (AMD даже документирует это поведение BSF/BSR.) Так или иначе, поэтому BSF/BSR Intel похожи на CMOV и нуждаются в качестве адресата в качестве входа в случае, если источник reg равен 0. popcnt, (и lzcnt/tzcnt на pre-Skylake) тоже страдают от этого.

---

Если вы сделали цикл более 5 мопов слитых доменов, SnB/IvB мог бы выдать его в лучшем случае 1 на 2 цикла от внешнего интерфейса. Haswell и позже "развернуть" в буфере цикла или что-то еще, так что цикл 5 моп может работать при ~1,25 с за одну итерацию, но SnB / IvB нет. Снижается ли производительность при выполнении циклов, число операций которых не кратно ширине процессора?

Начиная с Core 2, передний этап выпуска / переименования имеет ширину 4 мопа с плавким доменом в процессорах Intel.