AVX-512 и ветвление
Я запутался в том, что маскировка может сделать в теории относительно ветвей. Допустим, у меня есть Skylake-SP (ха, я хочу..), и мы игнорируем возможности компилятора, то, что возможно в теории:
Если условное ветвление зависит от статического флага, и все ветви устанавливают массив для результата вычисления, предполагая, что компилятор не оптимизирует это для двух отдельных циклов в любом случае, может ли он векторизовать?
do i = 1, nx
if (my_flag .eq. 0) then
a(i) = b(i) ** 2
else
a(i) = b(i) ** 3
end if
end do
Если только в качестве подмножества ветвей задается рассматриваемое значение, может ли оно векторизоваться?
do i = 1, nx
if (my_flag .eq. 0) then
a(i) = b(i) ** 2
end if
end do
Если условный переход сам по себе зависит от векторных данных, может ли он векторизоваться?
do i = 1, nx
if (c(i) > 0) then
a(i) = b(i) ** 2
else
a(i) = b(i) ** 3
end if
end do
2 ответа
Примечание. В этом ответе в основном обсуждается очень специфическая проблема доступа к памяти, когда речь идет о векторизации, и он применяется в основном на концептуальном уровне для преобразования серии скалярных обращений к массивам в векторизованные доступы, не предполагая ничего о том, какие части базовых массивов отображаются, В таких языках, как Fortran, семантика самого языка может гарантировать непрерывное сопоставление массивов или проверки границ перед входом в цикл может быть достаточно, чтобы избежать проблемы, упомянутой ниже.
Этот ответ не следует рассматривать как хороший подход к векторизации в целом и, конечно, не к фортрану. Более подробное рассмотрение проблем векторизации приведено в другом ответе, который также конкретно касается AVX-512.
Одна из часто пропускаемых проблем с условиями векторизации заключается в том, что компиляторы могут векторизовать условные циклы интересующего вас типа с помощью смешивания или других поэлементных методов предикации, только если они могут доказать, что векторизация получает доступ к тем же элементам, что и в скалярная поэлементная реализация. Если набор команд не предлагает поэлементного способа выполнения векторных нагрузок с учетом этого условия или если компилятор не может их использовать, это может эффективно блокировать векторизацию.
Другими словами, компиляторы могут в целом полностью векторизоваться только с простыми векторными нагрузками, если все пути в теле цикла обращаются к одним и темже элементам.
Основная причина заключается в том, что скомпилированный кодне должен обращаться к элементам, к которым нет доступа по семантике исходного кода, даже если они позднее "смешиваются", поскольку это может привести к ошибке! Если набор инструкций не содержит инструкций для условного доступа к элементам в памяти и подавления отказов из невыбранных элементов, это является существенным препятствием для оптимизации.
В приведенных вами примерах это означает, что (1) и (3) можно векторизовать "без поднятия условия", а (2) - нет, так как (2) осуществляет доступ a[i] а также b[i] только в if тело, но не еслиifне выполнен Конечно, настоящий компилятор просто выводит из цикла тривиальный флажок и просто не выполняет цикл вmyflag == falseслучай, так что это не очень хороший пример.
Давайте просто посмотрим на пару случаев, которые включают все ваши примеры. Во-первых, нам нужен флаг, который нельзя поднять - давайте просто использовать массив bool ценности. Итак, интересный, несколько общий цикл с выходным массивом a, два входных массива b а такжеcи массив флаговfможет выглядеть примерно так:
do i = 1, nx
if (f(i) > 0) then
a(i) = g(b(i), c(i));
else
a(i) = h(b(i), c(i));
end if
end do
В зависимости от флага f(i) в соответствии с каждым элементом, мы применяем либо функцию g или же hк элементам ввода b(i)а такжеc(i), По моему условию выше мы можем векторизовать только если оба g а также hна самом деле получить доступ к тем же элементамbа такжеc,
Давайте перейдем к двум реальным рабочим примерам выше:
void example1(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
for (size_t i = 0; i < n; i++) {
if (f[i]) {
a[i] = b[i];
} else {
a[i] = c[i];
}
}
}
void example2(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
for (size_t i = 0; i < n; i++) {
if (f[i]) {
a[i] = b[i] + c[i] ;
} else {
a[i] = b[i] - c[i] * 2 + 1 ;
}
}
}
Оба имеют одинаковую базовую форму, но что сложнее векторизовать? Первое - это простое прямое назначение b[i]или жеc[i] в зависимости от флага. Второй является более сложной функциейобоих b[i]а такжеc[i]которые значительно различаются в обоих направлениях.
Ну, вторую гораздо проще векторизовать, так как она b[i] а также c[i] безусловно. По факту, gcc не удается векторизовать ни один по какой-то причине. clangтолько векторизовал второй. Несколько удивительноicc удается векторизовать оба- так как он достаточно умен, чтобы использоватьvpmaskmovdкоторая является маскированной нагрузкой, которая подавляет неисправности для незагруженных элементов.
Вы можете исследовать сгенерированную сборку на Godbolt.
Я изначально начал этот ответ с идеи, что доступ к различным элементам массива в настоящее время является непреодолимым барьером для векторизации для современных компиляторов, но это потому, что я обычно не проверяюicc, Это на самом деле для меня новость, чтоiccиспользует маскированные движения таким образом. Таким образом, барьер существует, но, по крайней мере, некоторые компиляторы могут ошибиться над ним2.
Как разработчик, вы обычно знаете, что оба массива полностью доступны, так что доступ ко всем элементам b а также c В диапазоне [0, n) и было бы неплохо сообщить об этом компилятору. Я попытался добавить безусловные фиктивные заявления, такие какb[i] = b[i]; c[i] = c[i];или же... + c[i] * 0который должен ничего не компилировать, но, по крайней мере, позволить компилятору видеть, что семантически все элементы доступны. Они действительно "компилируются", но генерация кода не улучшается: дополнительная векторизация не происходит. Вероятно, они уже устранены на ранних этапах процесса компиляции до того, как будет выполнен анализ векторизации, так что информация будет потеряна для векторизатора.
Кроме инструкций маскируемого перемещения, которые не являются бесплатными и не полностью общими, есть ли другие способы улучшить эту ситуацию? Что ж, компилятор может воспользоваться своими знаниями о модели защиты памяти платформы. Например, как только любой байт на странице 4K на x86 был доступен, он может читать все остальные байты на этой странице. Можно представить себе сложную реализацию, которая начиналась в безопасном скалярном коде, но как только "заметили" запись в оба массива, она переключилась на векторизованный цикл для остальной части страницы.
Подобные трюки можно было бы воспроизвести, если доступ к массиву был выровнен: векторизованный цикл мог бы проверить, что если массив флагов был равномерно 0 или равномерно 1, в противном случае можно безопасно использовать прямую безусловную реализацию без масок чтения, в противном случае он вернется к более тщательная реализация. Такое преобразование, очевидно, было бы выгодно только в том случае, если маски были редко однородными или почти всегда однородными3, и, вероятно, вряд ли будут реализованы на практике.
2 По крайней мере, если AVX доступен:iccпо-прежнему не удастся векторизовать первый пример, если вы ограничите его инструкциями pre-AVX, поскольку именно тогдаvpmaskmovd/q а также vmaskmovps/pd были введены.
3 Так как в этом случае, если вы уже определили, что маска однородна, вы можете выполнить операцию безоговорочно, просто выполнив выбранную сторону if без маскировки / смешивания в зависимости от того,0 или равномерно1, Таким образом, вы получаете три внутренних цикла: регистр флага "все нули", регистр флага "все единицы" и регистр смешанного флага со скачками между ними, когда следующий вектор флагов не совпадает с текущим циклом,
Да, эффективная реализация asm возможна с любым из SSE2 / SSE4.1 (для blendps) / AVX / AVX-512, для всех ваших циклов и компиляторов на практике выполняют автоматическую векторизацию, но все gcc7.2 / clang5.0 / ICC18 пропустили оптимизацию.
Согласно статическому анализу для Skylake-AVX512 (см. Ниже), эффективная развернутая реализация вашего последнего цикла может выполняться с одним 64-байтовым вектором результатов на 1,25 такта (плюс издержки цикла в зависимости от того, сколько вы развернули). На практике, вероятно, достижимы 1,33 или 1,5 такта на вектор, если ваши данные горячие в кеше L1D. В противном случае вы легко станете узким местом в полосе пропускания L2, потому что вы загружаете 2x 64B на хранилище vector 64B хранилища.
Для C-версии вашего цикла, gcc, clang и ICC все более или менее автоматически векторизованы, как я делал вручную: см. Source + asm в проводнике компилятора Godbolt.
Я должен был использовать -ffast-math с gcc для его автоматической векторизации. IDK почему он не осознает, что может безопасно автоматически векторизоваться, не нарушая строгих правил FP.
Clang, кажется, оценивает tmp*tmp а также tmp*tmp*tmp отдельно и смешивая эти два результата вместо условного выполнения 2-го умножения.
gcc делает оба умножения и использует отдельные movaps для слияния другим способом, потому что не понимает, как инвертировать условие.
ICC использует KNOTW чтобы инвертировать условие, но затем 2-е умножается с маскированием слиянием точно так же, как я.
Изменение кода для дополнительного умножения ( **3 вместо **2 ) в if ветвь вместо else В результате ветвления все 3 компилятора сгенерировали лучший код без каждой их пропущенной оптимизации. (Есть еще пропущенные оптимизации для gcc, но ICC и clang выглядят солидно, и в сущности делают то же самое, что и мой рукописный код.)
ICC выбирает только автоматическую векторизацию с 256b векторами. Может быть, это делает это по умолчанию, чтобы избежать снижения максимальной скорости турбо тактовой частоты? Может быть, есть возможность использовать полноразмерные векторы? Снимок gcc 8.0 также делает это, но gcc7.2 использует векторы ZMM.
Регистры маски AVX-512 и маскирование слиянием делают его еще более эффективным, но в обоих случаях использование SIMD (или даже не SIMD-кода без ответвлений) долгое время выполнялось в обоих направлениях. например, для условного добавления на основе результата сравнения векторов, используйте этот результат сравнения векторов как маску AND, чтобы оставить некоторые элементы нетронутыми, а другие элементы обнулить.
0 это аддитивная идентичность: x + 0 = x, Так x + (y&mask) не работает, если маска все ноль, или это x+y если маска все-один. См. Как использовать условие if в intrinsics. (Забавный прием: используйте результат упакованного сравнения как целое число -1 или 0, так что вы можете считать совпадения, но вычитая маску сравнения).
Это менее просто для умножения, потому что 1 это мультипликативная идентичность, но вы можете решить это путем смешивания.
при условии, что компилятор не оптимизирует это для двух отдельных циклов в любом случае, он может векторизовать?
В этом первом случае вы должны быть недовольны вашим компилятором, если он не выводит условие из цикла и создает два цикла. Особенно во втором случае, когда требуется только один цикл, потому что если условие ложно, массив не изменяется.
Давайте просто поговорим о третьем случае, потому что это только один случай, когда компилятор не должен просто поднимать условие. (И если ваш компилятор чувствует себя глупым, он может использовать эту версию с циклически-инвариантной маской "все ноль" или "все-один" для других версий).
if (c(i) > 0)
Поэтому нам нужно загрузить вектор элементов из c и сравнить с нолем. AVX512 может сделать это для вектора 16 одинарной точности float с одной инструкцией с адресом регистра маски и операндом источника памяти.
; with zmm0 = 0.0 in all elements, from vxorps xmm0,xmm0,xmm0 outside the loop.
vcmpps k1, zmm0, [rdx], _CMP_NLT_UQ ; !(0 < c(i))
Я знаю (от написания уже следующей части), что я хочу k1 быть верным для элементов, где c(i) > 0 условие ложное. Только 2-й векторный операнд может быть памятью, а не регистром, поэтому мне пришлось обратить его вспять и использовать не менее чем вместо не более. (И я не могу просто использовать >= вместо < потому что это поместило бы неупорядоченный случай (один или оба NaN) в неправильную категорию. Сравнения FP имеют 4 возможных результата: выше / ниже / равно / неупорядочено, поэтому вы должны выбрать предикат, который делает то, что вы хотите (то есть, что говорит источник, если вы компилятор) для всех 4 случаев. Если вы компилируете с -ffast-math компилятору разрешено игнорировать возможность NaN.
Если вам нужно соединить два условия вместе, инструкции сравнения в маске AVX512 могут маскировать операцию записи в маску с нулевой маскировкой или маскированием слиянием.
vcmpltps k1, zmm1, zmm2 ; k1 = zmm1<zmm2
vcmpltps k2{k1}{z}, zmm3, zmm4 ; k2 = (zmm3<zmm4) & (zmm1<zmm2)
k2 0 везде, что это zmm3k1 было ноль, потому что мы использовали k1 в качестве нулевой маски.
if (c(i) > 0) then
a(i) = b(i) ** 2
else
a(i) = b(i) ** 3
end if
Общее подвыражение здесь b(i) * b(i), Мы можем получить b(i)**3 от этого путем умножения на b(i) одно дополнительное время
vmovups zmm1, [rsi] ; load a vector from b(i)
vmulps zmm2, zmm1, zmm1 ; zmm2 = zmm1*zmm1 = b(i)**2
AVX-512 может объединяться на основе маски как часть (почти) любой другой инструкции.
vmulps zmm2{k1}, zmm2, zmm1 ; zmm2 *= zmm1 for elements where k1 is true
vmovups [rdi], zmm2 ; store all 16 elements into a(i)
Кстати, AVX512 имеет слияния-маски для магазинов. Предыдущие наборы команд SIMD будут загружаться из [rdi], смешайте, затем сохраните обратно в [rdi], Это означает, что вы можете реализовать свой второй цикл (иногда оставить a(i) без изменений) с условием для каждого элемента более эффективно, чем с AVX1/ AVX2.
Собираем все это вместе: (синтаксис NASM)
; x86-64 System V calling convention
; args: rdi = a() output array.
; rsi = b() input array
; rdx = c() array to be tested for positive numbers
; rcx = count (in elements)
; preferably all 64-byte aligned, but will work slowly if some aren't
; rcx must be >= 16, and a multiple of 16, because I didn't write any cleanup code
global square_or_cube
square_or_cube:
vxorps xmm0, xmm0,xmm0
.loop: ; do {
vcmpps k1, zmm0, [rdx], 21 ; _CMP_NLT_UQ ; !(0 < c(i))
vmovups zmm1, [rsi] ; load a vector from b(i)
vmulps zmm2, zmm1, zmm1 ; zmm2 = zmm1*zmm1 = b(i)**2
vmulps zmm2{k1}, zmm2, zmm1 ; zmm2 *= zmm1 for elements where k1 is true, otherwise unmodified.
vmovups [rdi], zmm2 ; store all 16 elements into a(i)
; TODO: unroll some and/or use indexed addressing mode tricks to save instructions
add rdi, 64 ; pointer increments
add rsi, 64
add rdx, 64
sub rcx, 16 ; count -= 16
ja .loop ; } while(count>0);
Я проанализировал это с помощью IACA (без инструкций по приращению указателя, чтобы имитировать развертывание и более умные трюки asm). Согласно IACA, даже маскировка слиянием vmulps это один моп, и инструкции источника памяти микроплавкие предохранители к одному мопу для внешнего интерфейса. (То же самое относится и к магазину.) Это то, на что я надеялся, и вывод IACA выглядит правильно для этого случая, хотя у меня нет доступа к счетчикам производительности на оборудовании SKL-SP, чтобы это проверить.
$ iaca.sh -arch SKX avx512-conditional
Intel(R) Architecture Code Analyzer Version - 2.3 build:246dfea (Thu, 6 Jul 2017 13:38:05 +0300)
Analyzed File - avx512-conditional
Binary Format - 64Bit
Architecture - SKX
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 1.50 Cycles Throughput Bottleneck: FrontEnd
Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
---------------------------------------------------------------------------------------
| Cycles | 1.5 0.0 | 0.0 | 1.0 1.0 | 1.0 1.0 | 1.0 | 1.5 | 1.0 | 1.0 |
---------------------------------------------------------------------------------------
N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | |
---------------------------------------------------------------------------------
| 2^ | | | 1.0 1.0 | | | 1.0 | | | CP | vcmpps k1, zmm0, zmmword ptr [rdx], 0x15
| 1 | | | | 1.0 1.0 | | | | | | vmovups zmm1, zmmword ptr [rsi]
| 1 | 1.0 | | | | | | | | CP | vmulps zmm2, zmm1, zmm1
| 1 | 0.5 | | | | | 0.5 | | | CP | vmulps zmm2{k1}, zmm2, zmm1
| 2^ | | | | | 1.0 | | | 1.0 | | vmovups zmmword ptr [rdi], zmm2
| 1 | | | | | | | 1.0 | | | sub rcx, 0x10
| 0F | | | | | | | | | | jnbe 0xffffffffffffffdd
Total Num Of Uops: 8
AVX-512 на самом деле имеет vfpclassps (C/C++ свойственный [_mm512_fpclass_ps_mask ] 4, документация asm с таблицей в соответствующей vfpclasspd (упакованный двойной)) для классификации значений FP в соответствии с вашим выбором предикатов. Это может быть немного более эффективно, чем использование полного сравнения с другим регистром, который оказывается равным нулю.
(На самом деле, согласно IACA, это не так. Обе таблицы указаны в таблице с задержкой в 3 цикла в таблице InstLatx64. Измерение Агнера Фога для AVX2 cmpps на Skylake-S (не для настольных микросхем AVX512) показывается 4 такта, поэтому странно, что версия AVX512 имеет меньшую задержку при выдаче результата регистра маски вместо вектора.
Я хочу, чтобы результат был ложным только для положительных чисел, и я думаю, vfpclassps можно сделать это, установив почти все биты предиката для получения -Inf, конечного отрицания, тишины и сигнализации NaN, -0.0 и +0.0.
vfpclassps k1, [rdx], 0x1 | 0x2 | 0x4 | 0x10 | 0x40 | 0x80 ; QNaN | -0.0 | +0.0 | -Infinity | Negative (finite) | SNaN
; k1 = a 16-bit bitmap of which elements (from memory at [rdx]) need an extra multiply
vpfclassps интересен тем, что позволяет различать +0.0 и -0.0, как вы могли бы, проверяя бит знака в двоичном представлении (как вы могли бы с AVX2 vblendps использовать бит знака в качестве контроля смешивания, не проводя сравнение сначала).
Кроме того, в этом случае он сохраняет одну инструкцию вне цикла, настраивая регистр из всех нулей.
связанные: AVX512 имеет инструкции для умножения на 2**floor(x) (vscalefpd), но не для возведения числа в произвольную степень (целое или иное). Xeon Phi имеет AVX512ER, который дает вам быстрые приближения для 2**x (без настила x), но мы также не можем напрямую использовать экспоненциальную функцию, и SKL-SP все равно не имеет AVX512ER.
Макросы NASM для IACA_start / end:
Я написал это на основе iaca_marks.h Заголовок C / C++.
%if 1
%macro IACA_start 0
mov ebx, 111
db 0x64, 0x67, 0x90
%endmacro
%macro IACA_end 0
mov ebx, 222
db 0x64, 0x67, 0x90
%endmacro
%else
%define IACA_start
%define IACA_end
%endif
Оберните их вокруг любого кода, который вы хотите проанализировать.
Условная ветвь на петлеинвариантном условии внутри цикла
Компилятор может переходить внутри цикла. IDK, если кто-нибудь сделает код, подобный этому, но они, конечно, могут.
; rdi = destination
; rsi = source
; edx = condition
; rcx = element count
global square_or_cube
square_or_cube:
.loop: ; do {
vmovups zmm1, [rsi] ; load a vector from b(i)
vmulps zmm2, zmm1, zmm1 ; zmm2 = zmm1*zmm1 = b(i)**2
test edx,edx
jz .only_square ; test-and-branch to conditionally skip the 2nd multiply
vmulps zmm2, zmm2, zmm1 ; zmm2 *= zmm1
.only_square:
vmovups [rdi], zmm2 ; store all 16 elements into a(i)
add rdi, 64 ; pointer increments
add rsi, 64
sub rcx, 16 ; count -= 16
ja .loop ; } while(count>0);