Как формируется критический путь, когда существует зависимость данных между итерациями цикла во время выполнения ЦП инструкций?
В книге Computer Systems From A Programmer's Perspective есть следующий ассемблерный код для цикла:
L3:
1. movq %rax, (%rsi)
2. movq (%rdi), %rax
3. addq $1, %rax
4. subq $1, %rdx
5. jne .L3
Абстрактный ЦП, используемый для моделирования задач, имеет следующие функциональные блоки:
Предполагая, что %rsi и %rdi указывают на разные области памяти, автор говорит, что критический путь формируется инструкцией subq. Действительно, существует зависимость от данных, поскольку для уменьшения %rdx на каждой итерации нам нужно значение из предыдущей итерации.
Но разве нет зависимости данных между строками 2-3 и строкой 1? Если да, то почему он не образует критический путь? Мои мысли, чтобы ответить на него, следующие:
- ЦП может выполнять строки 2 и строки 3 заблаговременно для следующих итераций, используя технику, называемую переименованием регистров.
- Таким образом, когда строка 1 будет выполняться для нескольких последующих итераций, данные для нее готовы.
Если мои рассуждения имеют смысл, то что определяет, сколько операций записи, использующих один и тот же регистр (в данном случае loadq и addq в %rax), процессор может выполнить заранее?
Моя цель здесь — получить очень высокий уровень понимания того, как эти вещи могут работать.
Ответы 1
Да, есть много отдельных коротких цепочек зависимостей из 3 инструкций, каждая из которых начинается с загрузки (2) в одной итерации и заканчивается хранилищем (1) на следующей итерации. (Предполагая отсутствие алиасинга памяти).
Но нет цепочки зависимостей, переносимой циклом, кроме счетчика циклов; эта цепочка dep из 3 инструкций не соединяется обратно с входными зависимостями для любой из этих инструкций при следующем выполнении. Загрузка (2) разрывает зависимость от старого значения RAX, так что это начало другой короткой цепочки отложений, а не продолжение цепочки, начатой при последнем запуске.
Это было бы переносом в цикле, если бы вместо add $1, %rax была add %rax, %rdi или какая-либо другая инструкция, которая делала бы следующий адрес загрузки зависимым от предыдущей загрузки. В этом случае только хранилище будет «разветвляться» на каждой итерации. Как в микробенчмарке случайного доступа к памяти в Почему одна строка кода снижает производительность в 10 раз?
Таким образом, ЦП с широким неупорядоченным выполнением может иметь любое количество этих цепочек отложений в полете параллельно, перекрывая их задержки.
На самом деле, Sandybridge и более поздние версии должны иметь возможность запускать этот цикл с 1 итерацией за такт, как 4 моп, благодаря макрослиянию sub/jnz в один мопе для переднего и заднего конца. Узкое место в пропускной способности интерфейса, а также задержка на сервере sub; Передняя часть Ice Lake шириной 5 не будет работать быстрее.
uiCA может смоделировать это на Haswell , чтобы увидеть, как эти инструкции действительно будут проходить через фактический интерфейс и сервер реального конвейера, предполагая, что все загрузки и сохранения попадают в кэш L1d, а не псевдонимы. (Максимально точно смоделировано путем обратного проектирования для моделирования поведения внешнего интерфейса и планирования uop для циклов. Он не имитирует кеш.) Эта ссылка показывает, что Haswell поддерживает 1,0 цикла за итерацию. Визуализация таблицы трассировки разворачивает итерации цикла и показывает, в каком цикле каждая инструкция выдается из внешнего интерфейса во внутренний, когда она отправляется в исполнительный блок, завершает выполнение и когда удаляется. (Если эта ссылка на таблицу трассировки не работает, используйте первую ссылку, чтобы повторно сгенерировать ее путем повторного анализа из источника; источник asm является частью URL-адреса для первой ссылки.)
Выход без трассировки выглядит следующим образом. (LSD = буфер цикла, MITE = устаревшее декодирование, DSB = кэш-память uop, MS = секвенсор микрокода. Все uops здесь поступают из буфера цикла, который «блокирует их». Процессоры Intel декодируют хранилища как отдельные uop адреса хранилища и uop данных хранилища, микрослитые в одну интерфейсную uop, которая работает как 2 на серверной части, но может выдаваться как 1 и использовать только 1 запись ROB.)
Throughput (in cycles per iteration): 1.00
Bottlenecks: Dependencies, Issue, LSD, Ports
The following throughputs could be achieved if the given property were the only bottleneck:
- LSD: 1.00
- Issue: 1.00
- Ports: 1.00
- Dependencies: 1.00
M - Macro-fused with previous instruction
┌───────────────────────┬────────┬───────┬───────────────────────────────────────────────────────────────────────┬───────┐
│ MITE MS DSB LSD │ Issued │ Exec. │ Port 0 Port 1 Port 2 Port 3 Port 4 Port 5 Port 6 Port 7 │ Notes │
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│ 1 │ 1 │ 2 │ 0.13 0.25 1 0.63 │ │ mov qword ptr [rsi], rax
│ 1 │ 1 │ 1 │ 0.5 0.5 │ │ mov rax, qword ptr [rdi]
│ 1 │ 1 │ 1 │ 0.32 0.33 0.35 │ │ add rax, 0x1
│ 1 │ 1 │ 1 │ 1 │ │ sub rdx, 0x1
│ │ │ │ │ M │ jnz 0x6
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│ 4 │ 4 │ 5 │ 0.32 0.33 0.63 0.74 1 0.35 1 0.63 │ │ Total
└───────────────────────┴────────┴───────┴───────────────────────────────────────────────────────────────────────┴───────┘
Zen 1 и более поздние версии также могут поддерживать этот цикл со скоростью 1/такт; AMD объединяет только test или cmp с jcc, а не инструкции, которые также изменяют целочисленный регистр, поэтому для выпуска/переименования требуется 5 операций. Но внешний интерфейс Zen имеет ширину 5 инструкций / 6 мопов, поэтому его пропускная способность едва справляется с узким местом задержки в 1 цикл subq $1, %rdx
К вашему сведению, модель ЦП, которую использует CS:APP, в основном Intel Haswell (https://www.realworldtech.com/haswell-cpu/ ): обратите внимание на пропускную способность 4/такт для add/sub, по сравнению с 3 в Sandybridge- семья. И в других проблемах CS:APP мы видим, что их ЦП имеет 2/такт FP FMA/mul, но добавляет 1/такт FP, и задержки соответствуют Haswell. например Границы задержки и пропускной способности для процессоров для операций, которые должны выполняться последовательно Также обратите внимание, как результат mulsd считывается на каждой итерации, но по другой цепочке операций.
В любом случае, если бы существовала какая-либо петлевая зависимость дольше 1 цикла, это было бы узким местом. например добавьте or $0, %rdx к циклу, сделав его зависимостью с 2 циклами, и uiCA правильно имитирует это узкое место, в среднем 2,0 цикла на итерацию.
Пределы того, насколько далеко может видеть неработающий exec
Если мои рассуждения имеют смысл, то что определяет, сколько операций записи, использующих один и тот же регистр (в данном случае loadq и addq к %rax), процессор может выполнить заранее?
В этом случае узкое место переднего плана, вероятно, мешает внутреннему продвинуться далеко вперед. Но если бы не это (или на ЦП Ice Lake, интерфейс шириной 5 для цикла 4 uop), он был бы ограничен неупорядоченными ресурсами выполнения, в частности количеством физических регистров для переименования.
Целочисленный PRF Haswell имеет 168 записей. (https://www.realworldtech.com/haswell-cpu/3/).
Также потенциально емкость буфера повторного заказа (ROB). ROB Haswell имеет размер 192 мкп. Хранилище не записывает регистр, поэтому, по некоторым очень упрощенным приближениям, только 3/4 мопов в цикле должны выделять физический регистр для своего вывода. Более 16 из 168 записей PRF уже необходимы для хранения архитектурного состояния (включая значения регистров, которые вы не изменяете), но, как грубый расчет вручную, заполнение ROB 192 мопсами также израсходует 192 * 3/4 = 144 физический регистр файловые записи.
Смотрите https://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ для реальных экспериментов, подобных этому.
Значительно меньшим ограничением является размер планировщика (RS = станция резервирования). В Haswell это всего 60 мкп. Он отслеживает невыполненные мопы (в незакрепленном домене для семейства Sandybridge, поэтому хранилища занимают здесь 2 слота) по сравнению с ROB, отслеживающим не выведенные из эксплуатации мопы.
См. Понимание влияния lfence на цикл с двумя длинными цепочками зависимостей, для увеличения длины re: влияние размера RS на перекрытие длинных цепочек зависимостей.
С более широким внешним интерфейсом невыполненные мопы, заполняющие RS, в основном будут 1 за такт sub $1, %rdx + jnz мопов (из макрослияния под+ветки в один моп для порта 6, поскольку он был предсказан-занят), а хранилище -data uops (также ограничено 1/такт на Haswell, в отличие от store-address, который может работать на любом из p2/p3/p7 для этого простого режима адресации).
МОПы загрузки и добавления могут выполнять и освобождать свои записи RS (в среднем более 1 за цикл), ожидая удаления из ROB после выполнения всех предыдущих инструкций.
Если вы моделируете этот код в uiCA для более широкого ЦП, такого как Ice Lake, обратите внимание на увеличение количества циклов между выпуском и удалением по мере прокрутки трассировки. В отличие от Haswell, внешний интерфейс значительно опережает внутренний. (Ice Lake имеет пропускную способность хранилища 2/такт, включая хранилище данных, поэтому только узкие места с задержкой будут создавать резервные копии этих операций sub/jnz. В остальном это похоже на то, что это было бы для вашего бэкэнда Haswell с более широким интерфейсом. Конечно, у Ice Lake больше ROB, RS и PRF, чем у Haswell.)
Также связаны:
- Из каких соображений следует прогнозировать задержки операций на современных суперскалярных процессорах и как их рассчитать вручную?
- Почему mulss занимает всего 3 такта на Haswell, в отличие от таблиц инструкций Agner? (Развертывание циклов FP с несколькими аккумуляторами)
- https://agner.org/optimize/ особенно его руководства по микроархитектуре, в которых описываются детали конвейера различных микроархитектур x86.
- https://uops.info/
- Современные микропроцессоры 90-минутное руководство! отличный справочный материал для заполнения возможных пробелов в понимании основ пайплайнов и внеочередного выполнения. И конструктивные компромиссы (мощность, IPC, тактовая частота), с которыми сталкиваются архитекторы ЦП.
Вау, такой отличный ответ!! Спасибо за много полезных ссылок (uops.info великолепен). Для моего уровня знаний все еще требуется время, чтобы понять все, что вы здесь написали, но правильно ли я понял, что основная идея заключается в том, что ЦП в этом случае может загружать и добавлять значения намного раньше фактического выполнения посредством переименования регистров?
«Загрузка (2) разрывает зависимость от старого значения RAX, так что это начало другой короткой цепочки отложений, а не продолжение цепочки, начатой при последнем запуске» — это очень помогло. Таким образом, у нас есть много цепочек зависимостей из 3 инструкций, и каждая из них может работать независимо. Попался!
@Е.Щербо: Да, если фронтенд может передать тело цикла в бэкенд быстрее, чем 1 итерация за такт (например, Ice Lake), то да, независимые цепочки load+add будут выполняться значительно раньше цепочка отложений критического пути. Ваша основная мысль верна. Каждая инструкция, которая записывает регистр, переименовывается, когда она выдается в серверную часть; это позволяет избежать опасностей WAW и WAR.
@E.Shcherbo: И, кстати, да, часть ответа о том, насколько далеко вперед может продвинуться ЦП, сложна, но крошечна по сравнению с очень большим количеством итераций цикла. Если вы просто посмотрите на устойчивое состояние, не близкое к началу или концу цикла, количество циклов на итерацию просто ограничено самым узким местом, будь то задержка цепочки отложений, внешнего интерфейса или какого-либо внутреннего порта выполнения. или порты. Вот почему в вашем учебнике, вероятно, не говорится о том, насколько далеко может продвинуться серверная часть; Я написал об этом только потому, что вы спросили.
@E.Shcherbo: Ресурсы выполнения с глубоким нарушением порядка могут иметь значение для циклов с очень длинными, но не переносимыми петлями цепочками отложений. например например, оценка полинома шестого порядка или чего-то с цепочкой mul / add или FMA (правило Хорнера) на маломощном процессоре ARM может столкнуться с этим. У него могут быть только очереди планирования от 10 до 16 инструкций на порт выполнения, даже если у него приличный размер ROB. Так что этого было бы недостаточно для перекрытия цепочек зависимостей на слишком большом количестве итераций; он будет заполнен невыполненной зависимой работой от пары цепочек отложений, прежде чем появится более поздняя независимая работа.
По возможности лучше изучать полезные кодовые последовательности! Этот код делает некоторую запись и чтение, но всегда по тем же двум адресам памяти, что и
%rsiи%rdi, никогда не меняются, поэтому нет реального перемещения данных или вычислений (если только два указателя не совпадают, что заставляет последовательность кода увеличивать память).