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

Я хочу иметь возможность вручную предсказать, сколько именно произвольная арифметическая (то есть без разветвления или памяти, хотя это было бы неплохо), код сборки x86-64 будет принимать для конкретной архитектуры, принимая во внимание переупорядочение команд, суперскалярность, задержки, ИПЦ и т. д.

Что / описать правила должны соблюдаться для достижения этой цели?

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

Как минимум, я ищу (1) подтверждение того, что каждое правило является правильным, или же правильное изложение каждого правила, и (2) список любых правил, которые я, возможно, забыл.

  • В каждом цикле выдается как можно больше инструкций, начиная с текущего цикла и, возможно, настолько далеко вперед, как размер буфера переупорядочения.
  • Инструкция может быть выдана для данного цикла, если:
    • Никакие инструкции, которые влияют на его операнды, все еще не выполняются. А также:
    • Если это инструкция с плавающей запятой, каждая инструкция с плавающей запятой до того, как она была выполнена (инструкции с плавающей запятой имеют статический порядок команд). А также:
    • Для этой инструкции имеется функциональная единица в этом цикле. Каждая (?) Функциональная единица является конвейерной, что означает, что она может принять 1 новую инструкцию за цикл, а общее количество функциональных единиц равно 1/CPI для CPI данного класса функций (здесь туманно: предположительно, например, addps а также subps использовать тот же функциональный блок? Как мне это определить?). А также:
    • Меньше, чем суперскалярная ширина (обычно 4) количество инструкций уже было выдано в этом цикле.
  • Если никакие инструкции не могут быть выданы, процессор просто не выдает никаких - состояние, называемое "остановка".

В качестве примера рассмотрим следующий пример кода (который вычисляет перекрестный продукт):

shufps   xmm3, xmm2, 210
shufps   xmm0, xmm1, 201
shufps   xmm2, xmm2, 201
mulps    xmm0, xmm3
shufps   xmm1, xmm1, 210
mulps    xmm1, xmm2
subps    xmm0, xmm1

Моя попытка предсказать время ожидания для Haswell выглядит примерно так:

; `mulps`  Haswell latency=5, CPI=0.5
; `shufps` Haswell latency=1, CPI=1
; `subps`  Haswell latency=3, CPI=1

shufps   xmm3, xmm2, 210   ; cycle  1
shufps   xmm0, xmm1, 201   ; cycle  2
shufps   xmm2, xmm2, 201   ; cycle  3
mulps    xmm0, xmm3        ;   (superscalar execution)
shufps   xmm1, xmm1, 210   ; cycle  4
mulps    xmm1, xmm2        ; cycle  5
                           ; cycle  6 (stall `xmm0` and `xmm1`)
                           ; cycle  7 (stall `xmm1`)
                           ; cycle  8 (stall `xmm1`)
subps    xmm0, xmm1        ; cycle  9
                           ; cycle 10 (stall `xmm0`)
Источник

1 ответ

Это называется статическим анализом производительности. Википедия говорит ( https://en.wikipedia.org/wiki/List_of_performance_analysis_tools), что AMD CodeXL от AMD имеет "статический анализатор ядра" (то есть для вычислительных ядер, то есть циклов). Я никогда не пробовал это.

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

IACA неплох, но есть ошибки (например, неверные данные для shld на Sandybridge, и в последний раз я проверял, он не знает, что Haswell/Skylake может сохранять индексированные режимы адресации с микрозонкой для некоторых инструкций. Но, возможно, теперь это изменится, когда Intel добавит подробности об этом в свое руководство по оптимизации.) IACA также бесполезен для подсчета входных мопов переднего плана, чтобы увидеть, насколько ты близок к узкому месту (ему нравится только подсчитывать количество мопов в неиспользованном домене),

Статический анализ часто довольно хорош, но определенно проверяйте его с помощью счетчиков производительности. См. Может ли MOV x86 действительно быть "свободным"? Почему я не могу воспроизвести это вообще? для примера профилирования простого цикла для исследования микроархитектурной особенности.

Основное чтение:

Руководство по микроархам Agner Fog (глава 2: Execor exec) объясняет некоторые основы цепочек зависимостей и выполнения out-of-order. Его руководство "Оптимизация сборки" содержит более хорошие вводные и продвинутые материалы по производительности.

В последующих главах его руководства по микроархам рассматриваются детали конвейеров в процессорах, таких как Nehalem, Sandybridge, Haswell, K8/K10, Bulldozer и Ryzen. (Атом / Сильвермонт / Ягуар).

Таблицы команд Agner Fog (электронная таблица или PDF) также обычно являются лучшим источником для разбивки задержек команд / пропускной способности / порта выполнения.

Документы по анализу микроархов Дэвида Кантера очень хороши с диаграммами. например, https://www.realworldtech.com/sandy-bridge/, https://www.realworldtech.com/haswell-cpu/ и https://www.realworldtech.com/bulldozer/.

Смотрите также другие ссылки на производительность в теге x86 вики.

Я также попытался объяснить, как ядро ​​ЦП находит и использует параллелизм на уровне команд в этом ответе, но я думаю, что вы уже поняли эти основы, насколько они актуальны для настройки программного обеспечения. Я упоминал, как SMT (Hyperthreading) работает как способ предоставления большего количества ILP одному ядру ЦП.

В терминологии Intel:

  • "выпуск" означает отправку UOP в неработающую часть ядра; наряду с переименованием регистра, это последний шаг в интерфейсе. Этап "выпуск / переименование" часто является самой узкой точкой в ​​конвейере, например, в 4 раза по Intel после Core2. (С более поздними версиями, такими как Haswell и особенно Skylake, они часто очень близки к таковым в некотором реальном коде благодаря улучшенным декодерам SKL и пропускной способности uop-кеша, а также улучшениям внутренней и кеш-пропускной способности.): micro-fusion позволяет отправить 2 мопа через интерфейс и занять только одну запись ROB. (Мне удалось построить цикл на Skylake, который выдерживает 7 мопов неиспользованного домена за такт). Смотрите также http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ re: размер окна не в порядке.

  • "диспетчеризация" означает, что планировщик отправляет моп в порт исполнения. Это происходит, как только все входные данные готовы, и соответствующий порт выполнения доступен. Как точно запланированы x86 мопы?, Планирование происходит в "неиспользованном" домене; микроплавкие мопы отслеживаются отдельно в планировщике OoO (aka Reservation Station, RS).

Во многих других публикациях по компьютерной архитектуре эти термины используются в противоположном смысле, но именно эту терминологию вы найдете в руководстве по оптимизации Intel, а также названия счетчиков производительности оборудования, такие как uops_issued.any или же uops_dispatched_port.port_5,

сколько времени займет произвольный арифметический код сборки x86-64

Это зависит и от окружающего кода, потому что OoO exec

Ваш финал subps результат не должен быть готов, прежде чем процессор начнет работать с более поздними инструкциями. Задержка имеет значение только для более поздних инструкций, которым необходимо это значение в качестве входных данных, а не для целочисленного зацикливания и тому подобного.

Иногда важна пропускная способность, и exec-of-exec может скрыть задержку нескольких независимых цепочек коротких зависимостей. (например, если вы делаете одно и то же для каждого элемента большого массива из нескольких векторов, несколько перекрестных произведений могут быть запущены одновременно.) В результате вы получите сразу несколько итераций в полете, хотя и в программном порядке Вы заканчиваете все одну итерацию, прежде чем выполнять любую из следующих. (Программная конвейерная обработка может помочь для циклических тел с высокой задержкой, если OoO exec трудно сделать все переупорядочение в HW.)

Есть три основных измерения для анализа короткого блока

Вы можете приблизительно охарактеризовать короткий блок неразветвленного кода в терминах этих трех факторов. Обычно только один из них является узким местом для данного варианта использования. Часто вы смотрите на блок, который вы будете использовать как часть цикла, а не как тело всего цикла, но OoO exec обычно работает достаточно хорошо, так что вы можете просто сложить эти числа для пары разных блоков, если они не так долго, что размер окна OoO мешает найти все ILP.

  • задержка от каждого входа до выхода (ов). Посмотрите, какие инструкции находятся в цепочке зависимостей от каждого входа к каждому выходу. например, для одного выбора может потребоваться один ввод, чтобы быть готовым раньше.
  • общее количество мопов (для узких мест внешней пропускной способности), домен слияния на процессорах Intel. например, Core2 и более поздние версии могут теоретически выпускать / переименовывать 4 мопа слитых доменов за такт в планировщик неупорядоченного состояния /ROB. Семейство Sandybridge часто может достигнуть этого на практике с кэш-памятью uop и циклическим буфером, особенно Skylake с его улучшенными декодерами и пропускной способностью uop-кэша.

  • Число мопов для каждого внутреннего порта выполнения (неиспользуемый домен). например, случайный код часто будет узким местом на порту 5 на процессорах Intel. Корпорация Intel обычно публикует только цифры пропускной способности, а не разбивки портов, поэтому вам нужно взглянуть на таблицы Агнера Фога (или выходные данные IACA), чтобы сделать что-то значимое, если вы не просто повторяете одну и ту же инструкцию миллион раз.

    Как правило, вы можете предполагать планирование / распределение в лучшем случае с мопами, которые могут работать на других портах, не крадя занятые порты очень часто, но это действительно случается. ( Как именно запланированы x86-мопы?)

    Глядя на ИПЦ недостаточно; две команды CPI=1 могут или не могут конкурировать за один и тот же порт выполнения. Если они этого не делают, они могут выполнять параллельно. например, Haswell может работать только psadbw на порте 0 (задержка 5c, пропускная способность 1c, т.е. CPI=1), но это один моп, поэтому смесь 1 psadbw + 3 add инструкции могут выдержать 4 инструкции за часы. Есть векторные ALU на 3 разных портах в процессорах Intel, причем некоторые операции реплицируются на все 3 (например, логические значения), а некоторые - только на один порт (например, сдвигается до Skylake).

Иногда вы можете придумать пару разных стратегий, одна из которых может иметь меньшую задержку, но стоить больше мопов. Классическим примером является умножение на константы, такие как imul eax, ecx, 10 (1 моп, 3 с задержки на Intel) против lea eax, [rcx + rcx*4] / add eax,eax (2 мопа, задержка 2с). Современные компиляторы, как правило, выбирают 2 LEA против 1 IMUL, хотя лягун до 3,7 предпочитал IMUL, если только он не мог выполнить работу только с одной другой инструкцией.

См. Каков эффективный способ подсчета установленных битов в позиции или ниже? для примера статического анализа для нескольких различных способов реализации функции.

См. Также Почему mulss занимает всего 3 цикла в Haswell, в отличие от таблиц инструкций Агнера? (который оказался гораздо более подробным, чем можно было бы догадаться из названия вопроса) для еще одного краткого изложения статического анализа и некоторых полезных вещей о развертывании с несколькими аккумуляторами для сокращения.

Каждый (?) Функциональный блок конвейеризован

В последних процессорах делитель конвейерный, но не полностью конвейерный. (Тем не менее, деление FP является однопроцессорным, так что если вы сделаете один divps смешанный с десятками mulps / addps может иметь незначительное влияние на пропускную способность, если задержка не имеет значения: деление с плавающей запятой или умножение с плавающей запятой. rcpps + итерация Ньютона имеет худшую пропускную способность и примерно одинаковую задержку.

Все остальное полностью конвейерно на основных процессорах Intel; многоцикловая (взаимная) пропускная способность для одного мопа. (переменное число целых сдвигов, как shl eax, cl имеют меньшую, чем ожидалось, пропускную способность для 3-х мопов, потому что они создают зависимость через мопс слияния флагов. Но если вы сломаете эту зависимость через флаги с add или что-то, вы можете получить лучшую пропускную способность и задержку.)

На AMD до Ryzen, целочисленный множитель также только частично конвейеризован. например бульдозер imul ecx, edx только 1 моп, но с задержкой 4c, пропускной способностью 2c.

Xeon Phi (KNL) также имеет некоторые не полностью конвейеризованные инструкции тасования, но он имеет тенденцию к узкому месту на входе (декодирование инструкций), а не на стороне, и имеет небольшую возможность буфера + OoO exec для скрытия назад пузырьки

Если это инструкция с плавающей запятой, каждая инструкция с плавающей запятой до того, как она была выполнена (инструкции с плавающей запятой имеют статический порядок команд)

Нет.

Может быть, вы читали это для Silvermont, который не выполняет OoO exec для FP/SIMD, только целое число (с небольшим окном ~20 моп). Может быть, некоторые ARM-чипы такие же, с более простыми планировщиками для NEON? Я не знаю много о деталях ARM uarch.

Основные основные микроархитектуры, такие как семейство P6 / SnB, и все чипы AMD OoO выполняют OoO exec для инструкций SIMD и FP так же, как для целочисленных. Процессоры AMD используют отдельный планировщик, но Intel использует унифицированный планировщик, поэтому его полный размер можно применять для нахождения ILP в целочисленном или FP-коде, в зависимости от того, что выполняется в данный момент.

Даже основанная на silvermont Knight's Landing (в Xeon Phi) делает OoO exec для SIMD.

x86, как правило, не очень чувствителен к упорядочению команд, но планирование uop не выполняет анализ критических путей. Таким образом, иногда может оказаться полезным сначала поместить инструкции на критический путь, чтобы они не застревали в ожидании, когда их входные данные готовы, в то время как другие команды выполняются на этом порту, что приводит к большему срыву позже, когда мы получаем инструкции, которым нужен результат критический путь. (то есть именно поэтому это критический путь.)

Моя попытка предсказать время ожидания для Haswell выглядит примерно так:

Да, это выглядит правильно. shufps работает на порту 5, addps работает на р1, mulps работает на p0 или p1. Skylake сбрасывает выделенный модуль добавления FP и запускает SIMD FP add/mul/FMA для модулей FMA на p0/p1, все с задержкой 4c (вверх / вниз с 3/5/5 в Haswell или 3/3/5 в Бродуэлла).

Это хороший пример того, почему сохранение целого вектора направления XYZ в векторе SIMD обычно отстой. Хранение массива X, массива Y и массива Z позволило бы вам выполнять 4 перекрестных произведения параллельно без перемешивания.

Вики-тэг SSE содержит ссылку на эти слайды: SIMD на Insomniac Games (GDC 2015), в которой рассматриваются проблемы, связанные с массивом структур и структурой массивов для трехмерных векторов, и почему часто всегда пытаться использовать SIMD одна операция вместо использования SIMD для параллельного выполнения нескольких операций.

Источник
Другие вопросы по тегам