Трубопровод по учету регистров

Question

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

Вот код C ++ для простой тестовой программы:

#include <vector>

int main()
{
    std::vector<int> vec(10000u);
    std::fill(vec.begin(), vec.end(), 0);
    for (unsigned i = 0u; i < vec.size(); ++i)
    {
        vec[i] = 5;
    }

    return 0;
}

И часть ассемблерного кода, созданного для цикла:

...
00007FF6A4521080  inc         edx  
    {
        vec[i] = 5;
00007FF6A4521082  mov         dword ptr [rcx+rax*4],5  
00007FF6A4521089  mov         eax,edx  
00007FF6A452108B  cmp         rax,r9  
00007FF6A452108E  jb          main+80h (07FF6A4521080h)  
    }
...

В программе вектор " vec " выделен с постоянным размером и заполнен нулями. Важная «работа» происходит в цикле for, где все векторные переменные присваиваются 5 (просто случайное значение).

Я хочу спросить, не делает ли этот ассемблерный код какой-то сбой в конвейере? Причиной может быть то, что все инструкции каким-то образом связаны и работают с одинаковыми регистрами. Например, конвейер должен ждать с инструкцией cmp rax r9, прежде чем mov eax, edx фактически присвоит значение eax / rax ?

Зацикливание 10000 раз - это то место, где предсказание ветвления должно войти в работу. jb инструкция перескакивает 10000 раз и только в конце она пройдет. Это означает, что предсказатель ветвления должен очень легко предсказать, что скачок будет происходить большую часть времени. Тем не менее, эта оптимизация была бы бессмысленной с моей точки зрения, если сам код останавливает работу внутри цикла.

---

Моя целевая архитектура - Skylake i5-6400

Answer 1

TL; DR:

Случай 1: буфер, который умещается в L1D. Конструктор вектора или вызов std::fill полностью поместит буфер в L1D. В этом случае узким местом является пропускная способность конвейера в 1 хранилище и кэш L1D.

Случай 2: буфер, который вписывается в L2. Конструктор вектора или вызов std::fill полностью поместит буфер в L2. Однако L1 должен записывать грязные строки обратно в L2, и между L1D и L2 есть только один порт. Кроме того, линии должны быть извлечены из L2 в L1D. Пропускная способность 64B / цикл между L1D и L2 должна быть в состоянии легко справиться с этим, возможно, с периодическим конфликтом (подробнее см. Ниже). Таким образом, в целом узкое место такое же, как и в случае 1. Конкретный размер используемого вами буфера, около 40 КБ, не подходит для L1D Intel и последних процессоров AMD, но подходит для L2. Несмотря на то, что в случае одновременной многопоточности (SMT), может существовать дополнительная конкуренция со стороны другого логического ядра.

Случай 3: буфер, который не помещается в L2. Строки должны быть извлечены из L3 или памяти. Устройство предварительной выборки L2 DPL может отслеживать хранилища и предварительную выборку буфера в L2, тем самым уменьшая длительную задержку. Единственный порт L2 является узким местом вместе с буферами обратной записи и заполнения L1. Это серьезно, особенно когда буфер не помещается в L3, где межсоединение также может быть на критическом пути. Пропускная способность 1 хранилища слишком велика для подсистемы кеша. Два наиболее важных счетчика производительности: L1D_PEND_MISS.REQUEST_FB_FULL и RESOURCE_STALLS.SB.

---

Во-первых, обратите внимание, что конструктор (который, вероятно, будет встроен) vector сам инициализирует элементы в ноль, вызывая memset внутри. memset в основном делает то же самое, что и ваш цикл, но он очень оптимизирован. Другими словами, с точки зрения обозначения big-O, оба линейны по количеству элементов, но memset имеет меньший постоянный коэффициент. Кроме того, std::fill также внутренне вызывает memset, чтобы установить все элементы в ноль (снова). std::fill также, вероятно, будет встроен (при включенной правильной оптимизации). Следовательно, у вас действительно есть три цикла в этом куске кода. Было бы более эффективно инициализировать ваш вектор, используя std::vector<int> vec(10000u, 5). Теперь давайте перейдем к микроархитектурному анализу цикла. Я буду обсуждать только то, что ожидается от современных процессоров Intel, в частности от Haswell и Skylake ¹ .

Давайте внимательно рассмотрим код:

00007FF6A4521080  inc         edx
00007FF6A4521082  mov         dword ptr [rcx+rax*4],5  
00007FF6A4521089  mov         eax,edx  
00007FF6A452108B  cmp         rax,r9  
00007FF6A452108E  jb          main+80h (07FF6A4521080h) 

Первая инструкция будет декодирована в один моп. Вторая инструкция будет декодирована в два мопа, которые слиты во внешнем интерфейсе. Третья инструкция представляет собой перемещение из регистра в регистр и является кандидатом на исключение из перемещения на этапе переименования регистра. Трудно сказать наверняка, будет ли этот шаг устранен без выполнения кода ³ . Но даже если оно не будет устранено, инструкции будут отправлены следующим образом ² :

               dispatch cycle                            |         allocate cycle

cmp         rax,r9                           macro-fused | inc         edx                           (iteration J+3)
jb          main+80h (07FF6A4521080h)     (iteration J)  | mov         dword ptr [rcx+rax*4],5       (iteration J+3)
mov         dword ptr [rcx+rax*4],5       (iteration J+1)| mov         eax,edx                       (iteration J+3)
mov         eax,edx                       (iteration J+1)| cmp         rax,r9                            macro-fused
inc         edx                           (iteration J+2)| jb          main+80h (07FF6A4521080h)     (iteration J+3)
---------------------------------------------------------|---------------------------------------------------------
cmp         rax,r9                           macro-fused | inc         edx                           (iteration J+4)
jb          main+80h (07FF6A4521080h)     (iteration J+1)| mov         dword ptr [rcx+rax*4],5       (iteration J+4)
mov         dword ptr [rcx+rax*4],5       (iteration J+2)| mov         eax,edx                       (iteration J+4)
mov         eax,edx                       (iteration J+2)| cmp         rax,r9                            macro-fused
inc         edx                           (iteration J+3)| jb          main+80h (07FF6A4521080h)     (iteration J+4)

Инструкции cmp и jb будут макрофузированы в один моп. Таким образом, общее количество мопов равно 4 в слитом домене и 5 в неиспользованном домене. Среди них ровно один прыжок. Следовательно, итерация одного цикла может быть выдана за цикл.

Из-за зависимости между inc и mov хранилищем эти две инструкции не могут быть отправлены в одном и том же цикле. Тем не менее, inc из предыдущей итерации можно отправить с помощью мопов из предыдущей итерации.

Существует четыре порта (p0, p1, p5, p6), к которым можно подключить inc и mov. Существует ровно один порт, p6, для прогнозируемого принятого cmp/jb. Есть три порта (p2, p3, p7) для STA uop mov dword ptr [rcx+rax*4],5 и один порт, p4, для STD uop. (Хотя p7 не может обработать указанный режим адресации.) Поскольку существует только один порт для каждого, максимальная пропускная способность, которая может быть достигнута, составляет 1 итерацию за цикл.

К сожалению, пропускная способность будет хуже; многие магазины пропустят в L1D. Устройства предварительной выборки L1D не способны выполнять предварительную выборку строк в состоянии исключительной когерентности и не отслеживают запросы магазина. Но, к счастью, многие магазины будут объединены. Последовательные хранилища в цикле нацелены на последовательные расположения в виртуальном адресном пространстве. Поскольку строка имеет размер 64 байта, а каждое хранилище имеет размер 4 байта, каждые 16 последовательных хранилищ располагаются в одной и той же строке кэша. Эти магазины могут быть объединены в буфере магазина, но они не будут, потому что магазины уйдут в отставку как можно раньше, как только они окажутся на вершине ROB. Тело цикла довольно маленькое, поэтому маловероятно, что более 16 из 16 хранилищ будут объединены в буфере хранилища. Однако, когда комбинированный запрос хранилища будет выдан L1D, он пропустит и будет выделен LFB, который также поддерживает объединение хранилищ. Устройство предварительной выборки DPL-кэша L2 способно отслеживать запросы RFO, так что, надеюсь, мы почти всегда попадем в L2. Но это займет не менее 10-15 циклов, чтобы получить линию от L2 до L1 в. Тем не менее, RFO может быть отправлено досрочно, до того, как магазин действительно будет зафиксирован. В то же время, скорее всего, необходимо удалить грязную строку из L1, чтобы освободить место для входящей строки для записи. Выселенная строка будет записана в буфер обратной записи.

Трудно предсказать, каким будет общий эффект без запуска кода. Два наиболее значимых счетчика производительности: L1D_PEND_MISS.REQUEST_FB_FULL и RESOURCE_STALLS.SB.

.

L1D имеет только один порт хранилища шириной 16, 32 и 64 байта на Ivy Bridge, Haswell и Skylake соответственно. Таким образом, магазины будут совершены в этих гранулярности. Но один LFB всегда может содержать полную 64-байтовую строку кэша.

Общее количество слитков в магазине равно количеству элементов (в данном случае 1 миллион). Чтобы получить необходимое количество LFB, разделите на 16, чтобы получить 62500 LFB, что соответствует количеству RFO для L2. Потребуется 16 циклов, прежде чем потребуется еще один LFB, потому что за цикл может быть отправлено только одно хранилище. Пока L2 может доставить целевую линию в течение 16 циклов, мы никогда не будем блокировать LFB, и достигнутая пропускная способность будет близка к 1 итерации за цикл, или, с точки зрения IPC, 5 инструкций за цикл. Это возможно только в том случае, если мы почти всегда попадаем в L2 своевременно. Любая постоянная задержка в кеше или памяти значительно снизит пропускную способность ниже этой. Это может выглядеть примерно так: пакет из 16 итераций будет выполняться быстро, затем конвейер останавливается на LFB на некоторое количество циклов. Если это число равно задержке L3 (около 48 циклов), то пропускная способность будет составлять около 1 итерации за 3 цикла (= 16/48).

L1D имеет ограниченное количество (6?) Буферов обратной записи для хранения выселенных линий. Кроме того, L2 имеет только один 64-байтовый порт, который используется для всей связи между L1D и L2, включая обратные записи и RFO. Доступность буферов обратной записи также может быть на критическом пути. В этом случае количество LFB также является узким местом, поскольку LFB не будет записан в кэш, пока не будет доступен буфер обратной записи. Если нет, LFB заполнятся быстро, особенно если средство предварительной выборки L2 DPL смогло доставить линии своевременно. Очевидно, что потоковая кэш-память WB в L1D очень неэффективна.

Если вы запускаете код, вам также необходимо учесть два вызова на memset.

---

(1) На Sandy Bridge и Ivy Bridge, , инструкция mov dword ptr [rcx+rax*4],5 будет не ламинирована , что приведет к 5 мопам за итерацию в слитой области. Таким образом, интерфейс может быть на критическом пути.

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

(3) @PeterCordes обнаружил, что устранение ходов происходит в Skylake большую часть времени. Я также могу подтвердить это на Haswell.

Answer 2

Внеочередное выполнение скрывает задержку inc, питающего режим адресации магазина, как объяснил Хади.

Хранилище не может выполняться до цикла после inc от этой итерациивыполняется, но inc имеет только задержку в 1 цикл на большинстве uarches, поэтому нет времени для скрытого выполнения вне порядка.

---

Причина, по которой компилятор испускает этот неэффективный циклс дополнительным mov eax,edx означает, что вы использовали unsigned (32-битный) счетчик циклов с 64-битной size_t верхней границей.

unsigned типы в C ++ имеют хорошиеопределенное поведение переполнения (wraparound), которое должен реализовать компилятор (в отличие от подписанного переполнения, являющегося UB).Итак, как написано, цикл бесконечен, если vec.size() > UINT_MAX, и gcc должен создать код, который соответствует поведению абстрактной машины для этого случая.Это останавливает ваш компилятор от автоматической векторизации.

(И компиляторы, как правило, не проявляют агрессивности в отношении бесконечных циклов, являющихся UB, даже несмотря на то, что ISO C ++ говорит, что они есть, если они не содержат volatile или атомарных операций, или библиотекизвонки.)

Если бы вы использовали int i, у вас не было бы этой проблемы.Переполнением со знаком является UB, поэтому компилятор может предположить, что этого не происходит, и выдвинуть i на ширину size_t и указателей. Или лучше, используйте size_t i, вот для чего он. В любом случае, надеюсь, что компилятор может преобразовать цикл в приращение указателя и использовать простой режим адресации, а также автоматически векторизовать с SSE или AVX дляделать 16 или 32-байтовые хранилища.

---

Дополнительные mov eax,edx, однако, на 100% избыточны.i уже правильно расширен до нуля в RDX, поэтому компилятор может использовать inc edx / cmp rdx, r9.Это пропущенная оптимизация в любом используемом компиляторе.

Answer 3

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

И фактическая реализация x86 несколькими способами не приведет к снижению производительности, которое может подразумевать язык ассемблера с номинальной стоимостью.

То же самое относится и к предсказанию ветвления в этом цикле. Прогнозирование ветвей может происходить в разных формах одновременно. Первое, о чем вы должны подумать, это логика, которая каким-то образом предварительно вычисляет результат, так что выборка может начаться раньше (вот и все, что предсказывает ветвление, это выбрасывает дополнительную выборку, что, кстати, может иметь отрицательный эффект, некоторое количество часов. циклы раньше, чем обычная выборка будет). Или не беспокоиться о предварительных вычислениях и просто выбрасывать выборки для этого альтернативного пути на всякий случай и разрешать обычную выборку, чтобы покрыть условие не выполнено. Другое решение, которое вы можете / будете видеть реализованным, - это простой кэш, будь то глубокий или короткий. Я помню, как в прошлый раз, когда я был около 00007FF6A452108E, инструкция ветвления позволяла отбросить раннюю выборку и не беспокоилась о том, чтобы дождаться выполнения условия. Некоторые могут помнить только последние несколько ветвей, некоторые могут помнить больше, для такого простого цикла, как этот, запустите его 10 раз или 10 миллиардов, и вы не обязательно увидите прогноз ветвления.

По многим причинам я не ожидаю, что вы сможете создать что-то, что вы действительно сможете увидеть по сравнению с простым шумом. Прежде всего, вы, вероятно, выполняете это в операционной системе и спрашиваете операционную систему через слои кода, сколько времени рассчитывать на этот цикл. Я не ожидал, что вы сможете изолировать то, что вы пытаетесь сделать здесь, от шума операционной системы. Запуск DOS и отключение прерываний было бы началом, но я все еще не думаю, что вы увидите что-либо кроме шума процессора / системы.

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

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