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

Question

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

__m128* A, B;
__m128 dot0, dot1, dot2, dot3 = _mm_set_ps1(0);
for(size_t i=0; i<1048576;i+=4) {
    dot0 = _mm_add_ps( dot0, _mm_mul_ps( A[i+0], B[i+0]);
    dot1 = _mm_add_ps( dot1, _mm_mul_ps( A[i+1], B[i+1]);
    dot2 = _mm_add_ps( dot2, _mm_mul_ps( A[i+2], B[i+2]);
    dot3 = _mm_add_ps( dot3, _mm_mul_ps( A[i+3], B[i+3]);
}
... // add dots, then shuffle/hadd result.

Я слышал, что использование инструкций предварительной выборки может помочь ускорить процесс, поскольку он может извлекать дополнительные данные "в фоновом режиме", при этом выполнять муллы и добавлять данные, находящиеся в кеше. Однако мне не удалось найти примеры и объяснения того, как использовать _mm_prefetch(), когда, с какими адресами и с какими попаданиями. Не могли бы вы помочь в этом?

Answer 1

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

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

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

Это работает с гранулярностью строки кэша¹: вам нужно всего лишь выполнить одну предварительную выборку для каждой строки кэша: больше - это просто трата. Это означает, что в общем случае вы должны попытаться развернуть цикл достаточно, чтобы можно было выполнить только одну предварительную выборку для каждой строки кэша. В случае 16-байтового __m128 значения, это означает, что разверните как минимум на 4 (что вы сделали, так что вы хорошо там).

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

for(size_t i=0; i<1048576;i+=4) {
    dot0 = _mm_add_ps( dot0, _mm_mul_ps( A[i+0], B[i+0]);
    dot1 = _mm_add_ps( dot1, _mm_mul_ps( A[i+1], B[i+1]);
    dot2 = _mm_add_ps( dot2, _mm_mul_ps( A[i+2], B[i+2]);
    dot3 = _mm_add_ps( dot3, _mm_mul_ps( A[i+3], B[i+3]);
    _mm_prefetch(A + i + PF_A_DIST, HINT_A);
    _mm_prefetch(B + i + PF_B_DIST, HINT_B);
}

Вот PF_[A|B]_DIST расстояние до предварительной выборки перед текущей итерацией и HINT_ временная подсказка для использования. Вместо того, чтобы пытаться вычислить правильное значение расстояния из первых принципов, я бы просто определил хорошие значения PF_[A|B]_DIST экспериментально⁴. Чтобы уменьшить пространство поиска, вы можете начать с установки их обоих равными, так как логически подобное расстояние, вероятно, будет идеальным. Вы можете обнаружить, что только предварительная выборка одного из двух потоков является идеальной.

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

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

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

• Вы могли бы исследовать, помогает ли предварительная выборка только в начале границ страницы 4K³. Это усложнит структуру вашего цикла: вам, вероятно, понадобится вложенный цикл для разделения случаев "ближний край страницы" и "глубоко внутри страницы", чтобы выдавать только предварительные выборки вблизи границ страницы. Вы также захотите выровнять свои входные массивы по страницам, иначе это станет еще сложнее.
• Вы можете попробовать отключить некоторые / все аппаратные средства предварительной выборки. Это обычно ужасно для общей производительности, но при сильно настроенной загрузке с программной предварительной загрузкой вы можете повысить производительность, исключив помехи от аппаратной предварительной выборки. Выбор отключения предварительной выборки также дает вам важный ключевой инструмент, помогающий понять, что происходит, даже если вы в конечном итоге оставите все предварительные выборки включенными.
• Убедитесь, что вы используете огромные страницы, так как для больших смежных блоков, как это, они являются идеей.
• Есть проблемы с предварительной выборкой в ​​начале и в конце основного цикла вычислений: в начале вы пропустите предварительную выборку всех данных в начале каждого массива (в пределах начальной PF_DIST окно), и в конце цикла вы будете предварительно выбирать дополнительные и PF_DIST за пределами вашего массива. В лучшем случае это бесполезная выборка и пропускная способность команд, но они могут также вызвать (в конечном итоге отбрасывать) сбои страниц, которые могут повлиять на производительность. Вы можете исправить как с помощью специальных вступительных и выходных циклов для обработки этих случаев.

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

---

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

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

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

⁴ Обратите внимание, что "единицы" PF_DIST значение sizeof(__mm128)16 байтов из-за способа, которым я рассчитал адрес.