Основываясь на статическом анализе для Haswell / Skylake, я предложил версию, которая работает с ~ 5 циклами на значения 4 i вместо 8 циклов при компиляции с помощью gcc.Среднее для больших размеров, не считая времени на объединение нескольких копий Out[] и предполагающего случайное распределение индексов, которое не приводит к тому, что какие-либо цепочки хранения / перезагрузки работают достаточно долго, чтобы иметь значение.
IDK, если вам небезразличен Ryzen или Excavator (две другие основные микроархитектуры AVX2).
Я не провел тщательный анализ вручную, но IACA не подходит для HSW / SKL и считает, чтонекоторые инструкции не имеют микроплавкого предохранителя, хотя на самом деле они это делают (проверено на i7-6700k со счетчиками производительности), поэтому он считает, что узкое место в интерфейсе более серьезное, чем на самом деле.например, movhps загрузить + объединить микроплавкие предохранители, но IACA считает, что это невозможно даже при простых режимах адресации.
Мы должны иметь незначительные пропуски кеша, поскольку uint64_t Out[4][256] составляет всего 8 кБ.Таким образом, размер нашего кэша составляет всего 1/4 от размера L1d на большинстве современных процессоров, и он должен быть в основном нормальным даже при гиперпоточном разделении L1d между двумя логическими потоками.Циклы по data[] и Indices[] должны хорошо выбирать, и, надеюсь, не сильно изгонят Out[].Таким образом, статический анализ имеет хорошие шансы быть несколько точным, и он быстрее, чем тщательный микро-бенчмаркинг, и, что более важно, точно определяет узкие места.
Но, конечно, мы в значительной степени полагаемся навыполнение заказа и несовершенное планирование или другие неожиданные узкие места могут легко произойти.Я не чувствовал, что на самом деле микробенчмаркинг, если мне не платят.
Можем ли мы реализовать это более эффективно с помощью инструкций AVX2?
Этоэто в основном проблема гистограммы.Обычная оптимизация гистограммы с использованием нескольких таблиц и объединением в конце применяется .SIMD XOR полезен для объединения в конец (если вы используете Out[4][256], а не Out[256][4]. Последнее также замедляет индексирование, требуя масштабирования на 8*4 вместо 8 (что можетбыть сделано с одним LEA в режиме адресации с масштабированным индексом)).
Но в отличие от обычной гистограммы, вы XOR вводите некоторые данные из памяти вместо того, чтобы ДОБАВЛЯТЬ константу 1. Поэтому вместо немедленного 1, код должен загрузить data[i] в регистр в качестве источника для xor.(Или загрузите, затем xor reg, data[i] / store).Это даже больше операций с памятью, чем у гистограммы.
Мы вышли вперед из «ручного» сбора / разброса по векторам SIMD (используя movq / movhps загрузки / сохранения), что позволяет намиспользовать SIMD для загрузки data[i] и XOR.Это уменьшает общее количество операций загрузки и, таким образом, уменьшает нагрузку на порт загрузки, не требуя дополнительной полосы пропускания внешнего интерфейса.
Ручное объединение в 256-битные векторы, вероятно, не стоит дополнительной перестановки (дополнительный vinserti128 / vextracti128, чтобы мы могли объединить 2 источника памяти vpxor в один 256-битный).128-битные векторы должны быть хорошими.Пропускная способность внешнего интерфейса также является серьезной проблемой, поскольку (на процессорах семейства Intel SnB) вы хотите избежать индексированных режимов адресации для магазинов.gcc использует lea инструкции для вычисления адресов в регистрах вместо использования индексированных загрузок / хранилищ.clang / LLVM с -march=skylake решает не делать этого, что является плохим решением в этом случае, потому что узкие места в цикле на порте 2 / порту 3, и дополнительные траты ALU на то, чтобы позволить мерам хранилища с адресом использовать порт 7, являются выигрышем.Но если вы на не находитесь в узком месте на p23, тратить дополнительные мопы, чтобы избежать индексированных магазинов, нехорошо.(И в тех случаях, когда они могут оставаться микроплавкими , определенно не только для того, чтобы избежать индексированных нагрузок; глупые gcc).Возможно, модели стоимости в режиме адресации gcc и LLVM не очень точны, или они не моделируют конвейер достаточно подробно, чтобы выяснить, когда узкие места цикла во внешнем интерфейсе по сравнению с конкретным портом.
Выбор режимов адресации и других вариантов кода ассемблера является критически важным для оптимальной работы семейства SnB.Но запись в C не дает вам никакого контроля над этим ;вы в основном зависите от компилятора, если только вы не можете настроить исходный код, чтобы он сделал другой выбор.например, gcc vs. clang имеет здесь существенное значение.
В семействе SnB для нагрузки movhps требуется порт 5 для перемешивания / смешивания (хотя он выполняет микросопряжение в одном мопе), но *Магазин 1059 * - это чистый магазин без ALU UOP.Так что это безубыточность, и мы можем использовать одну SIMD-загрузку / XOR для двух элементов данных.
В AVX для ALU-мопов допускаются невыровненные операнды источника памяти, поэтому нам не нужно требовать выравнивания дляdata[].Но Intel HSW / SKL может поддерживать режим индексированной адресации с микроплавлением с pxor, но не vpxor.Таким образом, компиляция без включенного AVX может быть лучше , что позволяет компилятору использовать режим индексированной адресации вместо увеличения отдельного указателя.(Или сделать это быстрее, если компилятор не знает об этом и все равно использует индексированный режим адресации.) TL: DR: , вероятно, лучше всего потребовать выровненный по 16 байт data[] и скомпилировать эту функцию с отключенным AVX, для лучшего макро-синтеза.(Но тогда мы упускаем 256-битную SIMD для объединения Out срезов в конце, если мы не поместим это в другую функцию, скомпилированную с AVX или AVX2)
Избегание невыровненных загрузок позволит избежать кеш-памятиразделение строк тоже, что не требует дополнительных мопов, но мы, вероятно, близки к узким местам по пределам пропускной способности L1d, а не только к пределам пропускной способности загрузки / хранения исполнительного блока.
Я также посмотрелпри загрузке сразу 4 индекса и распаковке с инструкциями ALU .например, с memcpy в struct { uint8_t idx[4]; } idx;.Но gcc генерирует несколько ненужных инструкций для распаковки.Жаль, что у x86 нет хороших инструкций для битового поля, таких как ARM ubfx или , особенно PowerPC rlwinm (которые могут оставить результат смещенным влево бесплатно, поэтому, если бы у x86 это было, статический Outмог бы использовать режим адресации base + disp32 в коде, отличном от PIC.)
Распаковка меча с помощью shift / movzx из AL / AH - это победа, если мы используем скалярный XOR, но похоже, что это не таккогда мы используем SIMD для data[] и тратим интерфейсную пропускную способность на инструкции lea, чтобы разрешить выполнение мопов с адресом магазина на порту 7. Это делает нас интерфейсным узким местом, а не порт2 / 3 с узким местом, поэтому при использовании 4xmovzx загрузка из памяти выглядит лучше всего согласно статическому анализу.Стоит сравнить оба способа, если вы потратите время на ручное редактирование asm.(Генерируемый gcc ассемблер с дополнительными мопами просто плох, включая полностью избыточный movzx после сдвига вправо на 24, оставляя верхние биты уже нулевыми.)
Код
(см. в проводнике компилятора Godbolt вместе со скалярной версией):
#include <immintrin.h>
#include <stdint.h>
#include <string.h>
#include <stdalign.h>
#ifdef IACA_MARKS
#include "/opt/iaca-3.0/iacaMarks.h"
#else
#define IACA_START
#define IACA_END
#endif
void hist_gatherscatter(unsigned idx0, unsigned idx1,
uint64_t Out0[256], uint64_t Out1[256],
__m128i vdata) {
// gather load from Out[0][?] and Out[1][?] with movq / movhps
__m128i hist = _mm_loadl_epi64((__m128i*)&Out0[idx0]);
hist = _mm_castps_si128( // movhps into the high half
_mm_loadh_pi(_mm_castsi128_ps(hist), (__m64*)&Out1[idx1]));
// xorps could bottleneck on port5.
// Actually probably not, using __m128 the whole time would be simpler and maybe not confuse clang
hist = _mm_xor_si128(hist, vdata);
// scatter store with movq / movhps
_mm_storel_epi64((__m128i*)&Out0[idx0], hist);
_mm_storeh_pi((__m64*)&Out1[idx1], _mm_castsi128_ps(hist));
}
void ext(uint64_t*);
void xor_histo_avx(uint8_t *Indices, const uint64_t *data, size_t len)
{
alignas(32) uint64_t Out[4][256] = {{0}};
// optional: peel the first iteration and optimize away loading the old known-zero values from Out[0..3][Indices[0..3]].
if (len<3) // not shown: cleanup for last up-to-3 elements.
return;
for (size_t i = 0 ; i<len ; i+=4) {
IACA_START
// attempt to hand-hold compiler into a dword load + shifts to extract indices
// to reduce load-port pressure
struct { uint8_t idx[4]; } idx;
#if 0
memcpy(&idx, Indices+i, sizeof(idx)); // safe with strict-aliasing and possibly-unaligned
//gcc makes stupid asm for this, same as for memcpy into a struct,
// using a dword load into EAX (good),
// then AL/AH for the first 2 (good)
// but then redundant mov and movzx instructions for the high 2
// clang turns it into 4 loads
/*
//Attempt to hand-hold gcc into less-stupid asm
//doesn't work: same asm as the struct
uint32_t tmp;
memcpy(&tmp, Indices+i, sizeof(tmp)); // mov eax,[mem]
idx.idx[0] = tmp; //movzx reg, AL
idx.idx[1] = tmp>>8; //movzx reg, AH
tmp >>= 16; //shr eax, 16
idx.idx[2] = tmp; //movzx reg, AL
idx.idx[3] = tmp>>8; //movzx reg, AH
*/
#else
// compiles to separate loads with gcc and clang
idx.idx[0] = Indices[i+0];
idx.idx[1] = Indices[i+1];
idx.idx[2] = Indices[i+2];
idx.idx[3] = Indices[i+3];
#endif
__m128i vd = _mm_load_si128((const __m128i*)&data[i]);
hist_gatherscatter(idx.idx[0], idx.idx[1], Out[0], Out[1], vd);
vd = _mm_load_si128((const __m128i*)&data[i+2]);
hist_gatherscatter(idx.idx[2], idx.idx[3], Out[2], Out[3], vd);
}
IACA_END
// hand-hold compilers into a pointer-increment loop
// to avoid indexed addressing modes. (4/5 speedup on HSW/SKL if all the stores use port7)
__m256i *outp = (__m256i*)&Out[0];
__m256i *endp = (__m256i*)&Out[3][256];
for (; outp < endp ; outp++) {
outp[0] ^= outp[256/4*1];
outp[0] ^= outp[256/4*2];
outp[0] ^= outp[256/4*3];
}
// This part compiles horribly with -mno-avx, but does compile
// because I used GNU C native vector operators on __m256i instead of intrinsics.
/*
for (int i=0 ; i<256 ; i+=4) {
// use loadu / storeu if Out isn't aligned
__m256i out0 = _mm256_load_si256(&Out[0][i]);
__m256i out1 = _mm256_load_si256(&Out[1][i]);
__m256i out2 = _mm256_load_si256(&Out[2][i]);
__m256i out3 = _mm256_load_si256(&Out[3][i]);
out0 = _mm256_xor_si256(out0, out1);
out0 = _mm256_xor_si256(out0, out2);
out0 = _mm256_xor_si256(out0, out3);
_mm256_store_si256(&Out[0][i], out0);
}
*/
//ext(Out[0]); // prevent optimizing away the work
asm("" :: "r"(Out) : "memory");
}
Скомпилировано с gcc7.3 -std=gnu11 -DIACA_MARKS -O3 -march=skylake -mno-avx и проанализированос IACA-3.0:
$ /opt/iaca-3.0/iaca xor-histo.iaca.o Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-23;16:42:45
Analyzed File - xor-histo.iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 5.79 Cycles Throughput Bottleneck: FrontEnd
Loop Count: 22 (this is fused-domain uops. It's actually 20, so a 5 cycle front-end bottleneck)
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 2.0 0.0 | 3.0 | 5.5 5.1 | 5.5 4.9 | 4.0 | 3.0 | 2.0 | 3.0 |
--------------------------------------------------------------------------------------------------
DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - 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 |
-----------------------------------------------------------------------------------------
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movzx r8d, byte ptr [rdi]
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movzx edx, byte ptr [rdi+0x2]
| 1 | | | | | | | 1.0 | | add rdi, 0x4
| 1 | | | | | | | 1.0 | | add rsi, 0x20
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movzx eax, byte ptr [rdi-0x1]
| 1 | | 1.0 | | | | | | | lea r12, ptr [rcx+r8*8]
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movzx r8d, byte ptr [rdi-0x3]
| 1 | | 1.0 | | | | | | | lea rdx, ptr [r10+rdx*8]
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movq xmm0, qword ptr [r12]
| 1 | | | | | | 1.0 | | | lea rax, ptr [r9+rax*8]
| 1 | | 1.0 | | | | | | | lea r8, ptr [r11+r8*8]
| 2 | | | 0.5 0.5 | 0.5 0.5 | | 1.0 | | | movhps xmm0, qword ptr [r8] # Wrong, 1 micro-fused uop on SKL
| 2^ | 1.0 | | 0.5 0.5 | 0.5 0.5 | | | | | pxor xmm0, xmmword ptr [rsi-0x20]
| 2^ | | | 0.5 | 0.5 | 1.0 | | | | movq qword ptr [r12], xmm0 # can run on port 7, IDK why IACA chooses not to model it there
| 2^ | | | | | 1.0 | | | 1.0 | movhps qword ptr [r8], xmm0
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | movq xmm0, qword ptr [rdx]
| 2 | | | 0.5 0.5 | 0.5 0.5 | | 1.0 | | | movhps xmm0, qword ptr [rax] # Wrong, 1 micro-fused uop on SKL
| 2^ | 1.0 | | 0.5 0.5 | 0.5 0.5 | | | | | pxor xmm0, xmmword ptr [rsi-0x10]
| 2^ | | | | | 1.0 | | | 1.0 | movq qword ptr [rdx], xmm0
| 2^ | | | | | 1.0 | | | 1.0 | movhps qword ptr [rax], xmm0
| 1* | | | | | | | | | cmp rbx, rdi
| 0*F | | | | | | | | | jnz 0xffffffffffffffa0
Total Num Of Uops: 29 (This is unfused-domain, and a weird thing to total up).
gcc8.1 на Godbolt использует режим адресации с масштабированным индексом для pxor, используя тот же счетчик для индексов и data[], так что сохраняет add.
clang не использует LEA и узкие места при 4 i с за 7 циклов, потому что ни один из хранилищ не может работать на порту 7.
Скалярная версия (по-прежнему используется 4 среза Out[4][256]):
$ iaca.sh -mark 2 xor-histo.iaca.o
Intel(R) Architecture Code Analyzer Version - 2.3 build:246dfea (Thu, 6 Jul 2017 13:38:05 +0300)
Analyzed File - xor-histo.iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
*******************************************************************
Intel(R) Architecture Code Analyzer Mark Number 2
*******************************************************************
Throughput Analysis Report
--------------------------
Block Throughput: 7.24 Cycles Throughput Bottleneck: FrontEnd
Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
---------------------------------------------------------------------------------------
| Cycles | 3.0 0.0 | 3.0 | 6.2 4.5 | 6.8 4.5 | 4.0 | 3.0 | 3.0 | 0.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 | |
---------------------------------------------------------------------------------
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | mov eax, dword ptr [rdi]
| 1 | 0.4 | 0.5 | | | | 0.1 | | | | add rdi, 0x4
| 1 | | 0.7 | | | | 0.3 | | | | add rsi, 0x20
| 1* | | | | | | | | | | movzx r9d, al
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | mov rdx, qword ptr [rbp+r9*8-0x2040]
| 2^ | | 0.3 | 0.5 0.5 | 0.5 0.5 | | 0.3 | 0.4 | | | xor rdx, qword ptr [rsi-0x20]
| 2 | | | 0.5 | 0.5 | 1.0 | | | | | mov qword ptr [rbp+r9*8-0x2040], rdx # wrong, HSW/SKL can keep indexed stores fused
| 1* | | | | | | | | | | movzx edx, ah
| 1 | | | | | | 0.4 | 0.6 | | | add rdx, 0x100
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | mov r9, qword ptr [rbp+rdx*8-0x2040]
| 2^ | 0.6 | 0.2 | 0.5 0.5 | 0.5 0.5 | | 0.2 | 0.1 | | | xor r9, qword ptr [rsi-0x18]
| 2 | | | 0.2 | 0.8 | 1.0 | | | | | mov qword ptr [rbp+rdx*8-0x2040], r9 # wrong, HSW/SKL can keep indexed stores fused
| 1* | | | | | | | | | | mov edx, eax # gcc code-gen isn't great, but not as bad as in the SIMD loop. No extra movzx, but not taking advantage of AL/AH
| 1 | 0.4 | | | | | | 0.6 | | | shr eax, 0x18
| 1 | 0.8 | | | | | | 0.2 | | | shr edx, 0x10
| 1 | | 0.6 | | | | 0.3 | | | | add rax, 0x300
| 1* | | | | | | | | | | movzx edx, dl
| 1 | 0.2 | 0.1 | | | | 0.5 | 0.2 | | | add rdx, 0x200
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | mov r9, qword ptr [rbp+rdx*8-0x2040]
| 2^ | | 0.6 | 0.5 0.5 | 0.5 0.5 | | 0.3 | 0.1 | | | xor r9, qword ptr [rsi-0x10]
| 2 | | | 0.5 | 0.5 | 1.0 | | | | | mov qword ptr [rbp+rdx*8-0x2040], r9 # wrong, HSW/SKL can keep indexed stores fused
| 1 | | | 0.5 0.5 | 0.5 0.5 | | | | | | mov rdx, qword ptr [rbp+rax*8-0x2040]
| 2^ | | | 0.5 0.5 | 0.5 0.5 | | 0.6 | 0.4 | | | xor rdx, qword ptr [rsi-0x8]
| 2 | | | 0.5 | 0.5 | 1.0 | | | | | mov qword ptr [rbp+rax*8-0x2040], rdx # wrong, HSW/SKL can keep indexed stores fused
| 1 | 0.6 | | | | | | 0.4 | | | cmp r8, rdi
| 0F | | | | | | | | | | jnz 0xffffffffffffff75
Total Num Of Uops: 33
Цикл на 4 мопа слитых доменов короче, чем рассчитывает IACA, потому что он не знает, что только без ламината SnB / IvBпроиндексированные магазины.HSW / SKL нет.Однако такие магазины по-прежнему не могут использовать порт 7, поэтому для 4 элементов это будет не лучше, чем ~ 6,5 циклов.
(И, кстати, с наивной обработкой индексов [i], загружая каждый из них).отдельно с movzx вы получаете 8 циклов для 4 элементов, насыщая порты 2 и 3. Несмотря на то, что gcc не генерирует оптимальный по пропускной способности код для распаковки структуры, 4-байтная загрузка + распаковка должна быть чистым выигрышем, снимая некоторую нагрузку-порт давления.)
Цикл очистки :
Здесь действительно сияет AVX2: мы зацикливаемся на самом нижнем срезе гистограммы, а XOR на других срезах.Этот цикл состоит из 8 входных мопов с 4 нагрузками на Skylake и должен работать с 1 итером на 2 такта:
.L7:
vmovdqa ymm2, YMMWORD PTR [rax+4096]
vpxor ymm0, ymm2, YMMWORD PTR [rax+6144]
vmovdqa ymm3, YMMWORD PTR [rax]
vpxor ymm1, ymm3, YMMWORD PTR [rax+2048]
vpxor ymm0, ymm0, ymm1
vmovdqa YMMWORD PTR [rax], ymm0
add rax, 32
cmp rax, rdx
jne .L7
Я попытался еще больше уменьшить количество мопов, выполнив XOR в одной цепочке, ноgcc настаивает на том, чтобы сделать две vmovdqa загрузки и сделать один vpxor без операнда памяти.(OoO exec будет скрывать задержку этой крошечной цепочки / дерева VPXOR, поэтому это не имеет значения.)
Как бы я использовал рассеяние с AVX-512?Есть ли какая-то инструкция scatters, которая вместо xors перезаписывает xors?
Нет, вы использовали бы набор для получения старых значений, затем SIMD XOR, а затем рассредоточили обновленные элементы в местах, откуда они пришли.
Чтобы избежать конфликтов, вам может потребоваться out[8][256], чтобы каждый элемент вектора мог использовать свою таблицу.(В противном случае у вас возникнет проблема, если Indices[i+0] и Indices[i+4] будут равны, потому что хранилище разброса будет просто хранить самый высокий векторный элемент с этим индексом.
Для команд Scatter / collect требуется один базовый регистр, но выможно просто добавить _mm256_setr_epi64(0, 256, 256*2, ...); после выполнения vpmovzxbq нулевой нагрузки.
Примечания
Я использовал IACA2.3 для скалярного анализа, потому что IACA3Похоже, что .0 удалил опцию -mark, чтобы выбрать цикл для анализа, когда у вас есть несколько меток в одном файле. IACA3.0 не исправил ни одного из способов, которыми IACA2.3 ошибочна в отношении конвейера SKL в этом случае.