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

Например, возьмите следующую игрушечную петлю2:

top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top

это в основном реализует цикл (со следующим соответствием:eax -> total, c -> ecx):

do {
  total += popcnt(c + 5);
} while (--c > 0);

Я знаком с процессом оптимизации любого маленького цикла, рассматривая разбивку по uop, задержки в цепочке зависимостей и так далее. В приведенном выше цикле у нас есть только одна переносимая цепочка зависимостей:dec ecx, Первые три инструкции цикла (lea, imul, add) являются частью цепочки зависимостей, которая начинает каждый цикл заново.

Финалdec а такжеjne слиты. Таким образом, мы имеем в общей сложности 4 мопа слитых доменов и одну цепочку зависимостей с циклом переноса с задержкой в ​​1 цикл. Таким образом, исходя из этих критериев, кажется, что цикл может выполняться за 1 цикл / итерацию.

Тем не менее, мы должны посмотреть на давление порта:

lea можно выполнить на портах 1 и 5Popcnt может выполняться на порту 1add можно выполнить на портах 0, 1, 5 и 6Предсказано-принятоjnz выполняется на порту 6

Таким образом, чтобы перейти к 1 циклу / итерации, вам необходимо выполнить следующее:

Popcntдолжен выполнить на порту 1 (единственный порт, на котором он может выполняться)lea должен выполнить на порту 5 (и никогда на порту 1)add должен выполнить на порту 0, и никогда на любом из трех других портов, которые он может выполнить наjnz в любом случае может выполняться только на 6 порту

Это много условий! Если бы инструкции были запланированы случайным образом, вы могли бы получить намного худшую пропускную способность. Например, 75%add будет идти в порт 1, 5 или 6, что приведет к задержкеpopcnt, lea или жеjnz на один цикл. Аналогично дляlea который может перейти на 2 порта, один из которых используется совместно сpopcnt.

IACA, с другой стороны, сообщает о результате, очень близком к оптимальному, 1,05 цикла на итерацию:

Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - l.o
Binary Format - 64Bit
Architecture  - HSW
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 1.05 Cycles       Throughput Bottleneck: FrontEnd, Port0, Port1, Port5

Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |  6   |  7   |
---------------------------------------------------------------------------------------
| Cycles | 1.0    0.0  | 1.0  | 0.0    0.0  | 0.0    0.0  | 0.0  | 1.0  | 0.9  | 0.0  |
---------------------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis

| Num Of |                    Ports pressure in cycles                     |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |  6  |  7  |    |
---------------------------------------------------------------------------------
|   1    |           |     |           |           |     | 1.0 |     |     | CP | lea eax, ptr [ecx+0x5]
|   1    |           | 1.0 |           |           |     |     |     |     | CP | popcnt eax, eax
|   1    | 0.1       |     |           |           |     | 0.1 | 0.9 |     | CP | add edi, eax
|   1    | 0.9       |     |           |           |     |     | 0.1 |     | CP | dec ecx
|   0F   |           |     |           |           |     |     |     |     |    | jnz 0xfffffffffffffff4

Это в значительной степени отражает необходимое «идеальное» планирование, о котором я упоминал выше, с небольшим отклонением: оно показываетadd красть порт 5 отlea на 1 из 10 циклов. Он также не знает, что слитая ветвь собирается перейти на порт 6, так как это предсказано, как принято, поэтому он помещает большую часть мопов для ветки на порт 0, и большинство мопов дляadd на порту 6, а не наоборот.

Неясно, являются ли дополнительные 0,05 цикла, которые IACA сообщает по оптимальному, результатом некоторого глубокого, точного анализа или менее проницательного следствия алгоритма, который он использует, например, анализ цикла по фиксированному числу циклов, или просто ошибка или что-то еще. То же самое касается 0,1 доли мопа, которая, по ее мнению, попадет в неидеальный порт. Также не ясно, если одно объясняет другое - я думаю, что неправильное назначение порта 1 из 10 приведет к счету циклов 11/10 = 1,1 цикла на итерацию, но я не определил фактический нисходящий поток. результаты - может быть, влияние меньше в среднем. Или это может быть просто округление (0,05 == 0,1 до 1 знака после запятой).

Так как же на самом деле планируются современные процессоры x86? Особенно:

Когда несколько моповготовы на станции бронирования, в каком порядке они запланированы для портов?Когда UOP может перейти на несколько портов (например,add а такжеlea в приведенном выше примере), как определяется, какой порт выбран?Если какой-либо из ответов включает такую ​​концепцию, каксамый старший выбрать среди мопов, как это определяется? Возраст с момента его доставки в РС? Возраст с тех пор, как он стал готов? Как нарушаются связи? Приходит ли когда-нибудь порядок программ?Результаты на Skylake

Давайте измерим некоторые фактические результаты на Skylake, чтобы проверить, какие ответы объясняют экспериментальные данные, так что вот некоторые реальные результаты измерений (изperf) на моей коробке Skylake. Смущает, я собираюсь перейти на использованиеimul для моей инструкции «выполняется только на одном порту», ​​так как она имеет много вариантов, включая версии с тремя аргументами, которые позволяют вам использовать разные регистры для источника и назначения. Это очень удобно при создании цепочек зависимостей. Это также позволяет избежать всей "неправильной зависимости от пункта назначения",popcnt есть.

Независимые инструкции

Давайте начнем с рассмотрения простого (?) Случая, когда инструкции относительно независимы - без каких-либо цепочек зависимостей, кроме тривиальных, таких как счетчик цикла.

Вот 4 моп петли (только 3 выполненных мопа) с умеренным давлением. Все инструкции независимы (не указывайте ни источники, ни пункты назначения).add может в принципе украстьp1 нуженimul или жеp6 необходимо для dec:

Пример 1

instr   p0 p1 p5 p6 
xor       (elim)
imul        X
add      X  X  X  X
dec               X

top:
    xor  r9, r9
    add  r8, rdx
    imul rax, rbx, 5
    dec esi
    jnz top

The results is that this executes with perfect scheduling at 1.00 cycles / iteration:

   560,709,974      uops_dispatched_port_port_0                                     ( +-  0.38% )
 1,000,026,608      uops_dispatched_port_port_1                                     ( +-  0.00% )
   439,324,609      uops_dispatched_port_port_5                                     ( +-  0.49% )
 1,000,041,224      uops_dispatched_port_port_6                                     ( +-  0.00% )
 5,000,000,110      instructions:u            #    5.00  insns per cycle          ( +-  0.00% )
 1,000,281,902      cycles:u   

                                           ( +-  0.00% )

Как и ожидалось,p1 а такжеp6 полностью используютсяimul а такжеdec/jnz соответственно, а затемadd проблемыгрубо пополам между оставшимися доступными портами. Заметкагрубо - фактическое соотношение составляет 56% и 44%, и это соотношение довольно стабильно во всех прогонах (обратите внимание на+- 0.49% вариации). Если я отрегулирую выравнивание петли, разделение изменится (53/46 для выравнивания 32B, больше похоже на 57/42 для выравнивания 32B + 4). Теперь мы ничего не изменим, кроме позицииimul в петле:

Пример 2

top:
    imul rax, rbx, 5
    xor  r9, r9
    add  r8, rdx
    dec esi
    jnz top

Потом вдругp1/p5 сплит составляет ровно 50% / 50% с вариацией 0,00%:

   500,025,758      uops_dispatched_port_port_0                                     ( +-  0.00% )
 1,000,044,901      uops_dispatched_port_port_1                                     ( +-  0.00% )
   500,038,070      uops_dispatched_port_port_5                                     ( +-  0.00% )
 1,000,066,733      uops_dispatched_port_port_6                                     ( +-  0.00% )
 5,000,000,439      instructions:u            #    5.00  insns per cycle          ( +-  0.00% )
 1,000,439,396      cycles:u                                                        ( +-  0.01% )

Это уже интересно, но трудно сказать, что происходит. Возможно, точное поведение зависит от начальных условий при входе в цикл и чувствительно к упорядочению в цикле (например, потому что используются счетчики). Этот пример показывает, что происходит нечто большее, чем «случайное» или «глупое» планирование. В частности, если вы просто устранитеimul Инструкция из цикла, вы получите следующее:

Пример 3

   330,214,329      uops_dispatched_port_port_0                                     ( +-  0.40% )
   314,012,342      uops_dispatched_port_port_1                                     ( +-  1.77% )
   355,817,739      uops_dispatched_port_port_5                                     ( +-  1.21% )
 1,000,034,653      uops_dispatched_port_port_6                                     ( +-  0.00% )
 4,000,000,160      instructions:u            #    4.00  insns per cycle          ( +-  0.00% )
 1,000,235,522      cycles:u                                                      ( +-  0.00% )

Здесьadd в настоящее время примерно равномерно распределен средиp0, p1 а такжеp5 - поэтому наличиеimul повлияло наadd планирование: это было не просто следствием какого-то правила «избегать порта 1».

Обратите внимание, что общее давление порта составляет всего 3 моп / цикл, так какxor является идиомой обнуления и устраняется в переименователе. Давайте попробуем с максимальным давлением 4 моп. Я ожидаю, что любой механизм, задействованный выше, сможет идеально спланировать это. Мы только меняемxor r9, r9 вxor r9, r10, так что это больше не идиома обнуления. Мы получаем следующие результаты:

Пример 4

top:
    xor  r9, r10
    add  r8, rdx
    imul rax, rbx, 5
    dec esi
    jnz top

       488,245,238      uops_dispatched_port_port_0                                     ( +-  0.50% )
     1,241,118,197      uops_dispatched_port_port_1                                     ( +-  0.03% )
     1,027,345,180      uops_dispatched_port_port_5                                     ( +-  0.28% )
     1,243,743,312      uops_dispatched_port_port_6                                     ( +-  0.04% )
     5,000,000,711      instructions:u            #    2.66  insns per cycle            ( +-  0.00% )
     1,880,606,080      cycles:u                                                        ( +-  0.08% )

К сожалению! Вместо того, чтобы равномерно планировать всеp0156, планировщик недоиспользованp0 (это только выполнение чего-то ~ 49% циклов), и, следовательно,p1 а такжеp6 переподписан, потому что они выполняют как своитребуется опсimul а такжеdec/jnz, Такое поведение, я думаю, согласуется сСчетчик на основе Индикатор давления, как указано в их ответе, и смопы назначаются на порт во время выдачи, а не во время выполнения как упоминали и Хайести, и Питер Кордес. Такое поведение3 делаетвыполнить самый старый готовый мопс Правило не так эффективно. Если бы мопы не были связаны с портами исполнения в вопросе, а скорее во время исполнения, то это «самое старое» правило решило бы проблему выше после одной итерации - один разimul и одинdec/jnz задержали на одну итерацию, они всегда будут старше конкурирующихxor а такжеadd инструкции, поэтому всегда должны быть запланированы в первую очередь. Однако я узнал, что если порты назначаются во время выпуска, это правило не помогает, потому что порты предопределены во время выпуска. Я думаю, это все еще немного помогает в одобрении инструкций, которые являются частью длинных цепочек зависимости (так как они, как правило, отстают), но это не панацея, как я думал.

Это также, кажется, объясняет результаты выше:p0 получает больше давления, чем на самом деле, потому чтоdec/jnz комбо можеттеоретически выполнить наp06. по факту потому что предсказано, что ветвь взята только когда-либоp6, но, возможно, эта информация не может быть введена в алгоритм балансировки давления, поэтому счетчики имеют тенденцию видеть одинаковое давление наp016Это означает, чтоadd иxor распространяться по-разному, чем оптимально.

Возможно, мы сможем это проверить, развернув цикл так, чтобыjnz это менее важный фактор ...

1 Ок, правильно написаномикроопераций, но это убивает возможность поиска и фактически набирает символ «μ», я обычно прибегаю к копированию-вставке символа с веб-страницы.

2 Я изначально использовалimul вместоpopcnt в петле, но, невероятно,МАКА неподдержать это!

3 Обратите внимание, что я не утверждаю, что это плохой дизайн или что-то в этом роде - вероятно, существуют очень веские аппаратные причины, по которым планировщик не может легко принимать все свои решения во время выполнения.