Почему число мопов за итерацию увеличивается с увеличением потоковой загрузки?

Question

Рассмотрим следующий цикл:

.loop:
    add     rsi, OFFSET    
    mov     eax, dword [rsi]
    dec     ebp
    jg .loop

, где OFFSET - некоторое неотрицательное целое число, а rsi содержит указатель на буфер, определенный в разделе bss.Этот цикл является единственным циклом в коде.То есть он не инициализируется и не затрагивается до цикла.Предположительно, в Linux все виртуальные страницы 4K буфера будут отображаться по требованию на одну и ту же физическую страницу.Следовательно, единственным ограничением размера буфера является количество виртуальных страниц.Таким образом, мы можем легко экспериментировать с очень большими буферами.

Цикл состоит из 4 инструкций.Каждая инструкция декодируется в один моп в слитном и неиспользованном домене в Haswell.Между последовательными экземплярами add rsi, OFFSET также существует зависимость, переносимая циклами.Следовательно, в условиях простоя, когда нагрузка всегда находится в L1D, цикл должен выполняться примерно за 1 цикл на итерацию.Для небольших смещений (шагов) это ожидается благодаря IP потоковому предварительному считывателю L1 и потоковому предварительному извлечению L2.Однако оба средства предварительной выборки могут выполнять предварительную выборку только на странице 4K, и максимальный шаг, поддерживаемый средством предварительной выборки L1, составляет 2K.Таким образом, для небольших шагов, должно быть около 1 L1 промах на 4K страницы.По мере увеличения шага общее число пропусков L1 и пропусков TLB будет увеличиваться, и производительность соответственно будет ухудшаться.

На следующем графике показаны различные интересные счетчики производительности (за одну итерацию) для шагов от 0 до 128. Обратите внимание, чтоколичество итераций является постоянным для всех экспериментов.Изменяется только размер буфера для размещения указанного шага.Кроме того, учитываются только события производительности в пользовательском режиме.

Единственная странная вещь здесь - количество отставленных мопов увеличивается с ходом.Он идет от 3 мопов за итерацию (как и ожидалось) до 11 для шага 128. Почему это так?

С большими шагами все становится только страннее, как показано на следующем графике.На этом графике шаги варьируются от 32 до 8192 с шагом 32 байта.Во-первых, количество удаленных инструкций линейно увеличивается с 4 до 5 на шаге 4096 байт, после чего оно остается постоянным.Количество загрузок увеличивается с 1 до 3, а количество обращений к нагрузке L1D остается равным 1 на каждую итерацию.Только количество пропусков нагрузки L1D имеет смысл для всех шагов.

Два очевидных эффекта больших шагов:

• Время выполнения увеличивается, и поэтому будет происходить больше аппаратных прерываний.Однако я считаю события в пользовательском режиме, поэтому прерывания не должны мешать моим измерениям.Я также повторил все эксперименты с taskset или nice и получил те же результаты.
• Количество просмотров страниц и ошибок страниц увеличивается.(Я проверил это, но я опущу графики для краткости.) Ошибки страницы обрабатываются ядром в режиме ядра.Согласно этому ответу, обход страниц осуществляется с использованием специального оборудования (на Haswell?).Хотя ссылка, на которой основан ответ, устарела.

Для дальнейшего изучения, на следующем графике показано количество мопов из вспомогательных микрокодов.Число вспомогательных операций микрокода на одну итерацию увеличивается, пока не достигнет максимального значения на шаге 4096, как и в случае других событий производительности.Число операций ввода микрокода на виртуальную страницу 4K составляет 506 для всех шагов.В строке «Extra UOPS» отображается количество выбывших мопов минус 3 (ожидаемое количество мопов за итерацию).

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

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

---

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

cycles = 0.1773 * stride + 0.8521
uops = 0.0672 * stride + 2.9277

Принимая производные обеих функций:

d(cycles)/d(stride) = 0.1773
d(uops)/d(stride) = 0.0672

Это означает, что число циклов увеличится на 0,1773, а число удаленных мопов увеличитсяна 0,0672 с каждым шагом в 1 байт.Если прерывания и сбои страниц действительно были (единственной) причиной возмущения, не должны ли обе скорости быть очень близкими?

Answer 1

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

Легко увидеть, посмотрев код, который занимает 3 мопавыполнить одну итерацию.Первые несколько загрузок могут отсутствовать в кэше L1, но затем все последующие загрузки будут попадать в кэш, поскольку все виртуальные страницы отображаются на одну и ту же физическую страницу, а L1 в процессорах Intel физически помечены и проиндексированы.Итак, 3 мопса.Теперь рассмотрим событие производительности UOPS_RETIRED.ALL, которое происходит, когда моп удаляется.Мы ожидаем увидеть около 3 * number of iterations таких событий.Аппаратные прерывания и сбои страниц, возникающие во время выполнения, требуют помощи микрокода для обработки, что, вероятно, нарушит производительность.Следовательно, для конкретного измерения события X производительности источником каждого подсчитанного события может быть:

• Инструкции профилируемого кода.Давайте назовем это X ₁ .
• Упс, используемый для вызова сбоя страницы, который произошел из-за доступа к памяти, предпринятого профилируемым кодом.Давайте назовем это X ₂ .
• Uops, используемый для вызова обработчика прерываний из-за асинхронного аппаратного прерывания или для вызова программной исключительной ситуации.Давайте назовем это X ₃ .

Следовательно, X = X ₁ + X ₂ + X ₃ .

Поскольку код прост, мы смогли определить с помощью статического анализа, что X ₁ = 3. Но мы ничего не знаем о X ₂ и X ₃ , который не может быть постоянным на одну итерацию.Мы можем измерить X, используя UOPS_RETIRED.ALL.К счастью, для нашего кода количество сбоев страниц соответствует регулярному шаблону: ровно по одному на каждую страницу (что можно проверить с помощью perf).Разумно предположить, что для устранения каждой ошибки на странице требуется одинаковый объем работы, поэтому каждый раз он будет оказывать одинаковое влияние на X.Обратите внимание, что это отличается от количества сбоев страниц за итерацию, которое отличается для разных шагов загрузки.Число мопов, удаленных как прямой результат выполнения цикла для каждой страницы, является постоянным.Наш код не вызывает никаких программных исключений, поэтому нам не нужно о них беспокоиться.Как насчет аппаратных прерываний?Что ж, в Linux, пока мы запускаем код на ядре, которое не предназначено для обработки прерываний мыши / клавиатуры, единственное прерывание, которое действительно имеет значение, это локальный таймер APIC.К счастью, это прерывание также происходит регулярно.Пока количество времени, затрачиваемое на страницу, одинаково, влияние прерывания таймера на X будет постоянным для каждой страницы.

Мы можем упростить предыдущее уравнение до:

X =X ₁ + X ₄ .

Таким образом, для всех нагрузок

(X на страницу) - (X ₁ на страницу) = (X ₄ на страницу) = константа.

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

ec = total number of performance events (measured)
np = total number of virtual memory mappings used = minor page faults + major page faults (measured)
exp = expected number of performance events per iteration *on average* (unknown)
iter = total number of iterations. (statically known)

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

На основе аргументов и предположений, изложенных выше, мы можем вывести следующее уравнение:

C = (ec/np) - (exp*iter/np) = (ec - exp*iter)/np

Здесь есть два неизвестных: константа C и интересующее нас значение exp.Итак, нам нужно два уравнения, чтобы можно было вычислить неизвестные.Поскольку это уравнение выполняется для всех шагов, мы можем использовать измерения для двух разных шагов:

C = (ec ₁ - exp * iter) / np ₁
C = (ec ₂ - exp * iter) / np ₂

Мы можем найти exp:

(ec ₁ - exp * iter) / np ₁ = (ec ₂ - exp * iter) / np ₂
ec ₁ * np ₂ - exp * iter * np ₂ = ec ₂ * np ₁ - exp * iter * np ₁
ec ₁ * np ₂ - ec ₂ * np ₁ = exp * iter * np ₂ - exp * iter * np ₁
ec ₁ * np ₂ - ec ₂ * np ₁ = exp * iter * (np ₂ - np ₁ )

Таким образом,

exp = (ec ₁ * np ₂ - ec ₂ * np ₁ ) / (iter * (np ₂ - np ₁ ))

Давайте применим это уравнение кUOPS_RETIRED.ALL.

шаг ₁ = 32
iter = 10 миллионов
np ₁ = 10 миллионов * 32/4096 = 78125
ес ₁ = 51410801

шаг ₂ = 64
iter = 10 миллионов
np ₂ = 10 миллионов * 64/4096 = 156250
ec ₂ = 72883662

exp = (51410801* 156250 - 72883662 * 78125) / (10 м * (156250 - 78125))
= 2,99

Отлично!Очень близко к ожидаемым 3 пенсиям в отставке за итерацию.

C = (51410801 - 2,99 * 10 м) / 78125 = 275,3

Я рассчитал C для всех шагов.Это не совсем константа, но это 275 + -1 для всех шагов.

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

MEM_LOAD_UOPS_RETIRED.L1_MISS: exp = 0
MEM_LOAD_UOPS_RETIRED.L1_HIT: exp = 1
MEM_UOPS_RETIRED.ALL_LOADS: exp = 1
UOPS_RETIRED.RETIRE_SLOTS: exp = 3

Так работает ли это для всех событий производительности?Что ж, давайте попробуем что-то менее очевидное.Рассмотрим, например, RESOURCE_STALLS.ANY, который измеряет циклы задержки распределителя по любой причине.Трудно сказать, сколько должно быть exp, просто взглянув на код.Обратите внимание, что для нашего кода RESOURCE_STALLS.ROB и RESOURCE_STALLS.RS равны нулю.Только RESOURCE_STALLS.ANY здесь имеет значение.Вооружившись уравнением для exp и экспериментальными результатами для разных шагов, мы можем рассчитать exp.

шаг ₁ = 32
iter = 10 миллионов
np ₁ = 10 миллионов * 32/4096 = 78125
ec ₁ = 9207261

шага ₂ = 64
iter = 10миллион
np ₂ = 10 миллионов * 64/4096 = 156250
ec ₂ = 16111308

exp = (9207261 * 156250 - 16111308 * 78125) / (10 м * (156250 - 78125))
= 0,23

C = (9207261 - 0,23 * 10 м) / 78125 = 88,4

Я рассчитал C для всехшагает.Ну, это не выглядит постоянным.Возможно, мы должны использовать разные шаги?Без вреда при попытках.

шаг ₁ = 32
iter ₁ = 10 миллионов
np ₁ = 10 миллионов *32/4096 = 78125
ec ₁ = 9207261

шага ₂ = 4096
iter ₂ = 1 миллион
np ₂ = 1 миллион * 4096/4096 = 1 м
ec ₂ = 122563371

exp = (9207261 * 1 м - 102563371 * 78125) / (1м * 1м - 10м * 78125))
= 0,01

C = (9207261 - 0,23 * 10м) / 78125 = 88,4

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

Мы получили другое значение для exp.Я рассчитал C для всех шагов, и он все еще не выглядит постоянным, как показано на следующем графике.Он значительно варьируется для более мелких шагов, а затем немного после 2048 года. Это означает, что одно или несколько предположений о наличии фиксированного количества циклов задержки распределителя на страницу не являются действительными в такой степени.Другими словами, стандартное отклонение циклов задержки распределителя для разных шагов является значительным.

Для события производительности UOPS_RETIRED.STALL_CYCLES, exp = -0,32 и стандартное отклонение также значимо.Это означает, что одно или несколько предположений о наличии фиксированного количества циклов отставания на одной странице недействительны.

---

Я разработал простой способ исправить измеренное количество вышедших на пенсию инструкций. Каждый сбой вызванной страницы добавляет ровно одно дополнительное событие к счетчику удаленных команд. Например, предположим, что сбой страницы происходит регулярно после некоторого фиксированного числа итераций, например 2. То есть, каждые две итерацииошибка вызвана.Это происходит для кода в вопросе, когда шаг равен 2048. Поскольку мы ожидаем, что 4 инструкции будут отменены за одну итерацию, общее число ожидаемых удаленных инструкций до появления ошибки страницы будет равно 4 * 2 = 8. Поскольку ошибка страницы добавляет однудополнительное событие для счетчика удаленных команд, оно будет измеряться как 9 для двух итераций вместо 8. То есть 4,5 за итерацию.Когда я на самом деле измеряю количество выбывших инструкций для случая с шагом 2048, оно очень близко к 4,5.Во всех случаях, когда я применяю этот метод для статического прогнозирования значения измеренной удаленной инструкции за одну итерацию, ошибка всегда составляет менее 1%.Это очень точно, несмотря на аппаратные прерывания.Я думаю, что пока общее время выполнения составляет менее 5 миллиардов циклов ядра, аппаратные прерывания не будут оказывать существенного влияния на счетчик удаленных команд.(Каждый из моих экспериментов занимал не более 5 миллиардов циклов, вот почему.) Но, как объяснялось выше, всегда следует обращать внимание на количество возникших неисправностей.

Как я уже говорил выше, существует многосчетчики производительности, которые можно исправить, рассчитав значения для каждой страницы.С другой стороны, счетчик удаленных команд может быть исправлен с учетом количества итераций, чтобы получить ошибку страницы.RESOURCE_STALLS.ANY и UOPS_RETIRED.STALL_CYCLES, возможно, могут быть исправлены аналогично счетчику удаленных команд, но я не исследовал эти два.

Answer 2

Эффект, который вы неоднократно видите на многих счетчиках производительности, когда значение увеличивается линейно до шага 4096, после которого оно остается постоянным, имеет смысл, если вы предполагаете, что эффект вызван исключительно увеличением количества ошибок страниц с увеличением шага.Ошибки страниц влияют на наблюдаемые значения, поскольку многие счетчики не являются точными при наличии прерываний, ошибок страниц и т. Д.

Например, возьмите счетчик instructions, который изменяется от 4до 5 по мере продвижения от шага 0 к 4096. Из других источников мы знаем, что каждая ошибка страницы в Haswell будет учитывать одну дополнительную инструкцию в пользовательском режиме (и еще одну дополнительную в режиме ядра).

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

MIN(OFFSET / 4096, 1)

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

4 + 1 * MIN(OFFSET / 4096, 1)

, который полностью соответствует вашему графику.

Итак, грубая форма наклонного графика объясняется для всех счетчиков одновременно: наклон зависит только от величиныперерасчет на страницу ошибки.Тогда единственный оставшийся вопрос - почему ошибка страницы влияет на каждый счетчик так, как вы определили.Мы уже рассмотрели instructions, но давайте взглянем на другие:

MEM_LOAD_UOPS.L1_MISS

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

MEM_UOPS_RETIRED.ALL_LOADS

Это показывает 3 мопа (2 дополнительных) за ошибку страницы.

Я не уверен на 100%, как это событие работает в присутствии мопапереигровка.Всегда ли учитывается фиксированное количество мопов на основе инструкции, например, числа, которое вы видите в инструкции Агнера -> таблицы мопов?Или это подсчитывает фактическое количество мопов, отправленных от имени инструкции?Обычно это то же самое, но загрузки воспроизводят свои мопы, когда они пропускают на разных уровнях кэша.

Например, я обнаружил, что на Haswell и Skylake ² , когда загрузка пропускает в L1, нопопадания в L2, вы видите всего 2 мопа между портами загрузки (port2 и port3).Предположительно, что происходит, это то, что UOP отправляется с предположением, что оно попадет в L1, и когда этого не происходит (результат не готов, когда планировщик этого ожидал), он воспроизводится с новым временем, ожидающим попадание L2.Это «облегченный» вариант, поскольку он не требует какого-либо конвейера очистки, поскольку не выполнялись никакие инструкции неправильного пути.

Аналогично для пропуска L3 я наблюдал 3 мопа на нагрузку.

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

UOPS_RETIRED.ALL и IDQ.MS_UOPS

Остальная странность - большое количество мопов, связанных с каждой страницей,Кажется вполне возможным, что это связано с механизмом сбоя страницы.Вы можете попробовать аналогичный тест, который отсутствует в TLB, но не принимает ошибку страницы (убедитесь, что страницы уже заполнены, например, используя mmap с MAP_POPULATE).

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

Возможно, в этом случае также имеется утечка между счетчиками режима пользователя и режима ядра.

Циклы по сравнению спроизводная мопа

В последней части вашего вопроса вы показываете, что «крутизна» циклов по сравнению со смещением примерно в 2,6 раза больше, чем уклон вышедших мопов по сравнению со смещением.

Как и выше,эффект здесь останавливается на 4096, и мы снова ожидаем, что этот эффект полностью связан с ошибками страницы.Таким образом, разница в уклоне означает, что ошибка страницы стоит в 2,6 раза больше циклов, чем мопс.

Вы говорите:

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

Я не понимаю, почему.Соотношение между мопами и циклами может варьироваться в широких пределах, возможно, на три порядка: ЦП может выполнять четыре мопа за такт, или может потребоваться 100 секунд циклов для выполнения одного мопа (например, из-за отсутствия кэша).

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

Исследования по чрезмерному подсчету

Любой, кто заинтересован в избыточном подсчете из-за сбоев страниц и других событийможет быть интересен этот репозиторий github , который имеет исчерпывающие тесты на "детерминизм" различных событий PMU, и где было отмечено много результатов такого рода, в том числе на Haswell.Однако он не охватывает все счетчики, упомянутые здесь Хади (иначе у нас уже был бы наш ответ). Вот соответствующая бумага и некоторые более простые в использовании связанные слайды - в них, в частности, упоминается, что для каждой ошибки страницы требуется одна дополнительная инструкция.

Вот цитата длярезультаты от Intel :

Conclusions on the event determinism:
1.  BR_INST_RETIRED.ALL (0x04C4)
a.  Near branch (no code segment change): Vince tested 
    BR_INST_RETIRED.CONDITIONAL and concluded it as deterministic. 
    We verified that this applies to the near branch event by using 
    BR_INST_RETIRED.ALL - BR_INST_RETIRED.FAR_BRANCHES.
b.  Far branch (with code segment change): BR_INST_RETIRED.FAR_BRANCHES 
    counts interrupts and page-faults. In particular, for all ring 
    (OS and user) levels the event counts 2 for each interrupt or 
    page-fault, which occurs on interrupt/fault entry and exit (IRET).
    For Ring 3 (user) level,  the counter counts 1 for the interrupt/fault
    exit. Subtracting the interrupts and faults (PerfMon event 0x01cb and
    Linux Perf event - faults), BR_INST_RETIRED.FAR_BRANCHES remains a 
    constant of 2 for all the 17 tests by Perf (the 2 count appears coming
    from the Linux Perf for counter enabling and disabling). 
Consequently, BR_INST_RETIRED.FAR_BRANCHES is deterministic. 

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

---

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

² Я не хочу ограничивать это двумя микроархитектурами: они просто случаются сбудь теми, кого я проверял.