Неожиданно плохая и странная бимодальная производительность для цикла магазина на Intel Skylake

Я вижу неожиданно низкую производительность для простого цикла хранилища, который имеет два магазина: один с шагом вперед 16 байт и один, который всегда находится в одном и том же месте ¹ например:

volatile uint32_t value;

void weirdo_cpp(size_t iters, uint32_t* output) {

    uint32_t x = value;
    uint32_t          *rdx = output;
    volatile uint32_t *rsi = output;
    do {
        *rdx    = x;
        *rsi = x;

        rdx += 4;  // 16 byte stride
    } while (--iters > 0);
}

В сборке этот цикл, вероятно, ³ выглядит следующим образом:

weirdo_cpp:

...

align 16
.top:
    mov    [rdx], eax  ; stride 16
    mov    [rsi], eax  ; never changes

    add    rdx, 16

    dec    rdi
    jne    .top

    ret

Когда область доступа к памяти находится в L2, я ожидаю, что она будет работать менее чем за 3 цикла на итерацию. Второй магазин просто продолжает попадать в одно и то же место и должен добавить цикл. Первый магазин подразумевает вхождение линии из L2 и, следовательно, выселение линии каждые 4 итерации. Я не уверен, как вы оцениваете стоимость L2, но даже если вы консервативно оцениваете, что L1 может выполнять только один из следующих циклов: (a) зафиксировать хранилище или (b) получить строку из L2 или (c) высекайте линию до L2, вы получите что-то вроде 1 + 0,25 + 0,25 = 1,5 цикла для потока хранилища stride-16.

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

Однако фактическая производительность очень странная. Здесь типичный прогон испытательного жгута:

Estimated CPU speed:  2.60 GHz
output size     :   64 KiB
output alignment:   32
 3.90 cycles/iter,  1.50 ns/iter, cpu before: 0, cpu after: 0
 3.90 cycles/iter,  1.50 ns/iter, cpu before: 0, cpu after: 0
 3.90 cycles/iter,  1.50 ns/iter, cpu before: 0, cpu after: 0
 3.89 cycles/iter,  1.49 ns/iter, cpu before: 0, cpu after: 0
 3.90 cycles/iter,  1.50 ns/iter, cpu before: 0, cpu after: 0
 4.73 cycles/iter,  1.81 ns/iter, cpu before: 0, cpu after: 0
 7.33 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.33 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.34 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.26 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.28 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.31 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.29 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.28 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.29 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.27 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.30 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.30 cycles/iter,  2.81 ns/iter, cpu before: 0, cpu after: 0
 7.28 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0
 7.28 cycles/iter,  2.80 ns/iter, cpu before: 0, cpu after: 0

Две вещи здесь странные.

Во-первых, это бимодальные тайминги: есть быстрый режим и медленный режим. Мы начинаем в медленном режиме, занимая около 7,3 цикла на итерацию, а в какой-то момент переходим к примерно 3,9 циклам на итерацию. Такое поведение является последовательным и воспроизводимым, и два тайминга всегда довольно согласованы вокруг двух значений. Переход проявляется в обоих направлениях от медленного режима до быстрого режима и наоборот (а иногда и нескольких переходов за один проход).

Другая странная вещь - очень плохая производительность. Даже в быстром режиме, примерно в 3,9 цикла, производительность намного хуже, чем максимальный эффект 1.0 + 1.3 = 2.3, который вы ожидаете от добавления каждого из этих случаев с одним хранилищем (и считая, что абсолютно нулевое произведение может перекрываться когда оба магазина находятся в цикле). В медленном режиме производительность страшна по сравнению с тем, что вы ожидаете, основываясь на первых принципах: она занимает 7,3 цикла, чтобы сделать 2 магазина, и если вы поместили их в L2, то это примерно 29 циклов за хранилище L2 (поскольку мы сохраняем только одну полную строку кэша каждые 4 итерации).

Skylake записан как имеющий пропускную способность 64B/цикл между L1 и L2, что намного выше наблюдаемой пропускной способности (около 2 байтов)/цикл в медленном режиме).

Что объясняет низкую пропускную способность и бимодальную производительность, и я могу избежать этого?

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

Вы можете найти тестовый код и использовать его в github. Существует платформа Makefile для Linux или Unix-подобных платформ, но ее также следует относительно легко создавать на Windows. Если вы хотите запустить вариант asm, вам понадобится nasm или yasm для сборки ⁴ - если у вас нет этого, вы можете просто попробовать версию на С++.

Исключенные возможности

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

Факторы выравнивания: выходной массив равен 16 байтам, и я попытался выполнить выравнивание до 2 МБ без изменений. Также устраняется устранение по умолчанию.
Конфликт с другими процессами на машине: эффект наблюдается более или менее одинаково на холостом компьютере и даже на сильно загруженном (например, используя stress -vm 4). Сам тест должен быть полностью локально-локальным, так как он соответствует L2, а perf подтверждает, что на итерацию очень мало пропусков L2 (около 1 пропустить каждые 300-400 итераций, вероятно, связанных с кодом printf).
TurboBoost: TurboBoost полностью отключен, подтвержденный тремя различными показаниями МГц.
Энергосберегающий материал: регулятор производительности intel_pstate в режиме performance. Во время теста не наблюдаются изменения частоты (процессор остается практически заблокированным на 2,59 ГГц).
Эффекты TLB: эффект присутствует, даже если выходной буфер расположен на огромной странице размером 2 МБ. В любом случае, записи 64 4k TLB больше, чем покрытие выходного буфера 128K. perf не сообщает о каких-либо особенно странных действиях TLB.
4k aliasing: более старые версии с более сложными версиями этого теста показали некоторое сглаживание на 4k, но это было устранено, так как в эталоне нет загрузок (он загружает, что может неправильно использовать предыдущие хранилища). Также устраняется устранение по умолчанию.
Конфликты ассоциативности L2: устранены устранением по умолчанию и тем фактом, что это не исчезает даже с 2MB-страницами, где мы можем быть уверены, что выходной буфер выстроен линейно в физической памяти.
Эффекты гиперпотока: HT отключен.
Предварительная выборка: здесь могут быть задействованы только два из prefetchers ( "DCU", а также L1 ↔ L2 prefetchers), поскольку все данные хранятся в L1 или L2, но производительность одинакова со всеми включенными префаймерами или все отключены.
Прерывания: нет корреляции между количеством прерываний и медленным режимом. Существует ограниченное количество полных прерываний, в основном, тиков часов.

toplev.py

Я использовал toplev.py, который реализует Intel Top Down метод анализа, и неудивительно, что он идентифицирует контрольный показатель как привязанный к магазину:

BE             Backend_Bound:                                                      82.11 % Slots      [  4.83%]
BE/Mem         Backend_Bound.Memory_Bound:                                         59.64 % Slots      [  4.83%]
BE/Core        Backend_Bound.Core_Bound:                                           22.47 % Slots      [  4.83%]
BE/Mem         Backend_Bound.Memory_Bound.L1_Bound:                                 0.03 % Stalls     [  4.92%]
    This metric estimates how often the CPU was stalled without
    loads missing the L1 data cache...
    Sampling events:  mem_load_retired.l1_hit:pp mem_load_retired.fb_hit:pp
BE/Mem         Backend_Bound.Memory_Bound.Store_Bound:                             74.91 % Stalls     [  4.96%] <==
    This metric estimates how often CPU was stalled  due to
    store memory accesses...
    Sampling events:  mem_inst_retired.all_stores:pp
BE/Core        Backend_Bound.Core_Bound.Ports_Utilization:                         28.20 % Clocks     [  4.93%]
BE/Core        Backend_Bound.Core_Bound.Ports_Utilization.1_Port_Utilized:         26.28 % CoreClocks [  4.83%]
    This metric represents Core cycles fraction where the CPU
    executed total of 1 uop per cycle on all execution ports...
               MUX:                                                                 4.65 %           
    PerfMon Event Multiplexing accuracy indicator

На самом деле это не проливает много света: мы уже знали, что это, должно быть, магазины, которые могут испортить вещи, но почему? Описание Intel условия не говорят много.

Ниже приведено разумное резюме некоторых проблем, связанных с взаимодействием L1-L2.

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

³ В частности, это выглядит так, как если вы пишете сборку вручную или компилируете ее с помощью gcc -O1 (версия 5.4.1) и, возможно, наиболее разумных компиляторов (volatile используется, чтобы избежать погружения в основном мертвого второго магазина за пределы цикла).

⁴ Без сомнения, вы можете преобразовать это в синтаксис MASM с небольшими изменениями, поскольку сборка настолько тривиальна. Принимать запросы на передачу.

Ответ 1

То, что я нашел до сих пор. К сожалению, на самом деле это не дает объяснения низкой производительности, а вовсе не для бимодального распространения, но это скорее набор правил, когда вы можете увидеть производительность и примечания по ее смягчению:

Пропускная способность хранилища в L2 составляет не более одной 64-байтной строки кэша за три цикла ⁰ помещая верхний предел ~ 21 байт за цикл на пропускную способность магазина. С другой стороны, серия магазинов, которые промахиваются в L1 и попадают в L2, будет занимать не менее трех циклов на каждую строку кэша.
Над этой базой существует значительное ограничение, когда магазины, попавшие в L2, чередуются с магазинами в другую строку кэша (независимо от того, попадают ли эти магазины в L1 или L2).
Штраф, по-видимому, несколько больше для магазинов, находящихся поблизости (но все же не в одной строке кэша).
Бимодальная производительность по крайней мере поверхностно связана с вышеупомянутым эффектом, поскольку в случае без перемежения она не появляется, хотя у меня нет дополнительных объяснений.
Если вы убедитесь, что строка кэша уже находится в L1 перед хранилищем, путем предварительной выборки или фиктивной загрузки, медленная производительность исчезает, а производительность больше не является бимодальной.

Детали и фотографии

64-байт Stride

Исходный вопрос произвольно использовал шаг 16, но пусть начинается с, вероятно, простейшего случая: шаг 64, т.е. одна полная строка кеша. Как оказалось, различные эффекты видны с любым шагом, но 64 обеспечивает прохождение кеша L2 на каждом шаге и поэтому удаляет некоторые переменные.

Позвольте также удалить второй магазин на данный момент - так что мы просто тестируем однострочное хранилище на 64 байта на 64 КБ памяти:

top:
mov    BYTE PTR [rdx],al
add    rdx,0x40
sub    rdi,0x1
jne    top

Выполняя это в той же самой упряжке, что и выше, я получаю около 3.05 циклов/хранилище ² хотя есть довольно небольшая вариация по сравнению с тем, что я привык видеть (- вы даже можете найти там 3.0).

Таким образом, мы знаем, что мы, вероятно, не будем делать лучше, чем это для устойчивых магазинов, исключительно для L2 ¹. Хотя Skylake, по-видимому, имеет пропускную способность в 64 байта между L1 и L2, в случае потока магазинов эта полоса пропускания должна использоваться как для выселений из L1, так и для загрузки новой строки в L1. 3 цикла кажутся разумными, если для каждого из них требуется один цикл (a) выселить грязную линию жертвы от L1 до L2 (b) обновить L1 с новой строкой из L2 и (c) зафиксировать хранилище в L1.

Что происходит, когда вы добавляете вторую запись в одну строку кэша (в следующий байт, хотя это и не имеет значения) в цикле? Вот так:

top:
mov    BYTE PTR [rdx],al
mov    BYTE PTR [rdx+0x1],al
add    rdx,0x40
sub    rdi,0x1
jne    top

Здесь приведена гистограмма времени для 1000 прогонов тестовой жгуты для вышеуказанного цикла:

  count   cycles/itr
      1   3.0
     51   3.1
      5   3.2
      5   3.3
     12   3.4
    733   3.5
    139   3.6
     22   3.7
      2   3.8
     11   4.0
     16   4.1
      1   4.3
      2   4.4

Таким образом, большинство раз кластеризуется около 3,5 циклов. Это означает, что это дополнительное хранилище добавило только 0,5 цикла к времени. Это может быть что-то вроде буфера хранилища, способного выгрузить два магазина в L1, если они находятся в одной строке, но это происходит примерно в половине случаев.

Учтите, что буфер хранилища содержит ряд таких хранилищ, как 1, 1, 2, 2, 3, 3, где 1 указывает строку кэша: половина позиций имеет два последовательных значения из одной и той же строки кэша, а половина - нет. Поскольку буфер хранилища ожидает, чтобы сбрасывать хранилища, а L1 активно вытесняет и принимает линии от L2, L1 будет доступен для магазина в произвольной точке, и если он находится в позиции 1, 1, возможно, хранит сток в одном цикле, но если он равен 1, 2, он принимает два цикла.

Обратите внимание, что существует еще один пик около 6% результатов около 3,1, а не 3,5. Это может быть устойчивое состояние, когда мы всегда получаем удачный результат. Существует еще один пик около 3% при ~ 4.0-4.1 - "всегда неудачная" компоновка.

Позвольте проверить эту теорию, посмотрев различные смещения между первым и вторым магазинами:

top:
mov    BYTE PTR [rdx + FIRST],al
mov    BYTE PTR [rdx + SECOND],al
add    rdx,0x40
sub    rdi,0x1
jne    top

Мы пробуем все значения FIRST и SECOND от 0 до 256 с шагом 8. Результаты с переменными значениями FIRST на вертикальной оси и SECOND по горизонтали:

Мы видим конкретный шаблон - белые значения являются "быстрыми" (вокруг значений 3.0-4.1, рассмотренных выше для смещения 1). Значения желтого цвета выше, до 8 циклов и красные до 10. Фиолетовые выбросы являются самыми высокими и обычно являются случаями, когда "медленный режим", описанный в OP, срабатывает (как правило, с тактовой частотой 18,0 такта/итера). Мы замечаем следующее:

Из рисунка белых ячеек мы видим, что мы получаем результат быстрого цикла ~ 3.5, пока второй магазин находится в одной и той же строке кеша или следующей относительно первого хранилища. Это согласуется с вышеизложенной идеей, что хранилища в одной и той же строке кэша обрабатываются более эффективно. Причина, заключающаяся в том, что наличие второго хранилища в следующей строке кеша работает, заключается в том, что шаблон заканчивается тем же, за исключением первого первого доступа: 0, 0, 1, 1, 2, 2, ... vs 0, 1, 1, 2, 2, ... - где во втором случае это второй магазин, который первым затрагивает каждую строку кеша. Однако буфер хранилища не волнует. Как только вы попадаете в разные строки кэша, вы получаете шаблон типа 0, 2, 1, 3, 2, ... и, видимо, это отстой?
Фиолетовые "выбросы" никогда не появляются в белых областях, поэтому, по-видимому, они ограничены сценарием, который уже медленный (и медленнее здесь происходит примерно на 2,5x медленнее: от ~ 8 до 18 циклов).

Мы можем немного уменьшить масштаб и посмотреть на еще большие смещения:

Та же самая базовая модель, хотя мы видим, что производительность улучшается (зеленая область), так как второй магазин выходит дальше (впереди или позади) первого, вплоть до того, что он снова становится хуже со смещением около ~ 1700 байт. Даже в улучшенной области мы достигаем в лучшем случае 5,8 циклов/итераций, которые все еще намного хуже, чем производительность в 1,5 раза.

Если вы добавите какую-либо команду загрузки или предварительной выборки, которая проходит впереди ³ в магазинах, исчезают как общая медленная производительность, так и выбросы медленного режима:

Вы можете перенести это обратно на исходный шаг на 16 проблем - любой тип предварительной выборки или загрузки в цикле ядра, в значительной степени нечувствительный к расстоянию (даже если он по сути), устраняет проблему, и вы получаете 2,3 цикла/итерация, близкая к наилучшему идеалу 2.0 и равная сумме двух магазинов с отдельными контурами.

Таким образом, основное правило заключается в том, что хранилища для L2 без соответствующих нагрузок намного медленнее, чем если бы вы их предварительно отбирали, если только весь поток хранилища не обращается к линиям кэша одним последовательным шаблоном. Это противоречит идее, что линейный шаблон, подобный этому, никогда не выигрывает от предварительной выборки SW.

На самом деле у меня нет пояснения, но они могут включать следующие факторы:

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

Эти комментарии доктора МакКальпина на форумах Intel также весьма интересны.

⁰ В основном только достижимо, когда стример L2 отключен, поскольку в противном случае дополнительный конфликт на L2 замедляет это примерно до 1 строки за 3,5 цикла.

¹ Сравните это с хранилищами, где я получаю почти ровно 1,5 цикла на загрузку, для подразумеваемой полосы пропускания ~ 43 байта за цикл. Это имеет прекрасный смысл: полоса L1 ↔ L2 имеет длину 64 байта, но при условии, что L1 либо принимает линию от L2, либо обслуживает запросы нагрузки от ядра каждого цикла (но не параллельно), то у вас есть 3 цикла для двух нагрузок для разных линий L2: 2 цикла для приема строк из L2 и 1 цикл для удовлетворения двух инструкций загрузки.

² С предварительной выборкой. Как оказалось, предварительный сборщик L2 конкурирует за доступ к кэшу L2, когда он обнаруживает потоковый доступ: хотя он всегда находит строки-кандидаты и не переходит к L3, это замедляет код и увеличивает изменчивость. Выводы, как правило, выполняются с предварительной выборкой, но все просто немного медленнее (здесь большая доля результатовс предварительной выборкой - вы видите около 3,3 цикла на нагрузку, но с большой вариабельностью).

³ Это даже не нужно делать впереди - также выполняется предварительная выборка нескольких строк: я полагаю, что prefetch/load просто быстро запускаются впереди магазинов, которые являются узкими местами, поэтому они всегда идут вперед, Таким образом, предварительная выборка является своего рода самовосстановлением и, кажется, работает практически с любой ценностью, которую вы вложили.

Ответ 2

У Sandy Bridge есть "предварительные выборщики аппаратного обеспечения данных L1". Это означает, что изначально, когда вы делаете свой магазин, CPU должен извлекать данные из L2 в L1; но после того, как это произошло несколько раз, аппаратный предварительный выборщик замечает хороший последовательный шаблон и запускает предварительную выборку данных из L2 в L1 для вас, так что данные находятся либо в L1, либо "на полпути до L1", прежде чем ваш код выполнит свой магазин.