Каково минимальное количество цепочек зависимостей, чтобы максимизировать пропускную способность выполнения?

Дана цепочка инструкций, связанных истинными зависимостями и периодически повторяющихся (т.е. цикл), например (a->b->c)->(a->b->c)->...

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

  • (a0->b0->c0)->(a0->b0->c0)->...
  • (a1->b1->c1)->(a1->b1->c1)->...

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

Какое оптимальное количество цепочек зависимостей обеспечивает максимальную производительность выполнения?

Согласно руководству Агнера Оптимизация подпрограмм на языке ассемблера, раздел 12.15: "Оптимальное количество аккумуляторов если процессору больше нечего делать, это задержка наиболее важной инструкции в цепочке зависимостей, деленная на обратную пропускную способность для этой инструкции». Что означает «самая важная инструкция»? Есть ли какая-либо другая техническая документация, решающая подобные проблемы?




Ответы (1)


Это зависит от их длины и от того, сколько мопов за цикл каждый из них может выполнять сам по себе.

Это также зависит от ширины оборудования. например

  • PIII с двумя исполнительными блоками ALU и пропускной способностью 3 операций в объединенном домене за такт по сравнению с
  • Haswell с четырьмя исполнительными блоками ALU (только три из которых могут обрабатывать векторы) и 4 пропускной способностью объединенных доменов за такт.

Я думаю, что «самая важная инструкция» означает ту, которая составляет большую часть длины критического пути. Если цепочка зависимостей, переносимая циклом, состоит из нескольких инструкций с разными задержками, это своего рода среднее значение. (Как, может быть, среднее геометрическое?)


Хорошим примером является добавление FP (например, суммирование массива):

В Sandybridge он имеет пропускную способность один на такт, но задержку 3c, поэтому одна цепочка зависимых инструкций addps выполняется с частотой один uop на 3c, поддерживая только 1/3 от максимальной пропускной способности множителя FP. (И оставив два других порта исполнения совершенно незанятыми.)

Три параллельные цепочки отложений могут поддерживать насыщение порта 1 addps инструкциями. Так что если вы используете три аккумулятора, вы можете держать в полете трех аддов. Если вы также сохраните множители 5 FP в полете, вы также можете насытить порт 0. Накладные расходы цикла могут выполняться на порту 5 (и, надеюсь, не воровать циклы с p01). Нагрузочные мопы могут микрослияться с добавлениями, поэтому они не занимают пропускную способность объединенного домена. Но вы можете выполнять некоторые нагрузки с отдельными movaps инструкциями и при этом не насыщать пропускную способность объединенного домена 4 за такт, но узкие места во внешнем интерфейсе могут ограничивать вас в снижении пропускной способности.


Haswell по-прежнему имеет только одну пропускную способность за такт для добавления FP, но два за такт для FP mul и FMA.

Таким образом, если вы суммируете массив с помощью FMA (с множителем 1,0), вам потребуется 10 векторных аккумуляторов (10 цепочек отложений), чтобы удерживать 10 FMA в полете, насыщая p01. p5 и p6 остаются неиспользованными, но вы также можете насытить порты нагрузки нагрузками с микроплавкими предохранителями.


Skylake сократила задержку FMA на 1 цикл, до 4, и отказалась от модуля добавления FP. (Поэтому добавление FP выполняется в блоке FMA, что удвоило пропускную способность для [v]addps за счет увеличения задержки на 1 с).

Таким образом, на SKL вам нужно всего 8 векторных аккумуляторов (8 цепочек dep), чтобы насытить p01. Но наличие большего количества цепочек отложений не повредит, если у вас не закончатся регистры. Таким образом, код, который идеально подходит для Haswell, использующий 10 аккумуляторов, должен быть идеальным и для SKL. Возможно, вы могли бы сэкономить немного энергии, просто используя addps вместо fma213ps (или что-то еще) с постоянным вектором 1,0.


См. Таблицы инструкций Agner для пропускной способности/задержки/номера портов и его microarch PDF для более подробной информации. Я не проверял номера портов или числа задержек, но я набирал этот пример так часто, что почти уверен, что он правильный :P.

Также смотрите другие ссылки в вики-странице x86.

person Peter Cordes    schedule 21.07.2016
comment
Спасибо за этот очень прагматичный и подробный ответ, но если у кого-то есть теоретические материалы для решения этой проблемы, это будет очень признательно. - person DMH; 01.08.2016
comment
@DMH: я думал, что это довольно хорошо иллюстрирует теорию. Вы вычисляете отношение пропускной способности к задержке для последовательности инструкций, и это количество ее копий, которые должны находиться в полете, чтобы стать узким местом по пропускной способности, а не по задержке. Это может означать или не означать их ручное чередование, в зависимости от длины и того, передаются ли они в цикле (например, использование нескольких аккумуляторов в сокращении для коротких зависимостей, переносимых циклом). - person Peter Cordes; 01.08.2016