Vectorize 2d-array access (GCC)

Question

Я понимаю основные идеи векторизации. Я думаю преобразовать одну из моих программ в векторизованную версию. Но это кажется сложным.

Существует таблица (2d-массив) table[M][N] и два вектора X[1..4] и Y[1..4]. Могу ли я выполнять операции, как показано ниже? Есть предположения?

X[1..4] = table[X[1..4]][Y[1..4]] 

(последовательная версия: X[i] = table[X[i]][Y[i]])

В другом слове, может следующий цикл векторизовать?

for(k=0; k<4; k++) { 
     tmp1 = X[k]; 
     tmp2 = Y[k]; 
     X[k] = table[tmp1][tmp2]; 
    } 

Примечание: X[] всегда содержит различные значения.

В настоящее время он реализован на языке C.

Answer 1

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

Answer 2

Теоретически это прекрасно, но это зависит от того, какой процессор у вас есть. Вам нужна vector gather функциональность, которая была добавлена ​​в x86-процессоры через AVX2 и впервые появилась в микроархитектуре Haswell. Псевдокод будет выглядеть примерно так

vr1 := simd_load4(x) 
vr2 := simd_load4(y) 
vr3 := vr1 * 4; // multiply by the number of rows 
vr4 := vr3 + vr2; 
vr5 := simd_gather(base=&table, offsets=vr4) 
simd_store(x, vr5) 

версия SSE/AVX может выглядеть следующим образом

__m128i vr1 = _mm_load_si128 (x); 
__m128i vr2 = _mm_load_si128 (y); 
__m128i vr3 = _mm_mul_epi32 (vr1, _mm_set1_epi32 (4)); 
__m128i vr4 = _mm_add_epi32 (vr3, vr2); 
__m128i vr5 = _mm_i32gather_epi32 (table, vr4, 1); 
_mm_store_si128 (x, vr5); 

Answer 3

1) Технически hayesti уже ответил на ваш вопрос (вкладыши/hoirzontal инструкции на SSE/AVX из vgather на AVX2 сделает это возможным). Но обратите внимание также, что как GCC4.9, так и ICC будут векторизовать данный фрагмент кода (поэтому нет необходимости в intrinsics/hand-encoding для реального произвольного доступа), хотя для GCC вам, вероятно, понадобится #pragma omp simd, и вам также может понадобиться -vec-threshold0 для ICC на машинах SSE.

2) Практически, если у вас есть векторизовать данный код «как есть», он никогда не будет очень хорошая скорость вверх, потому что вам нужно «ammortize» большие накладные расходы (латентность) из vgather или vinsert -s с достаточным векторным вычислением (которого у вас нет в вашем примере) для векторизации «прибыльный». И не нужно говорить, что вам также понадобятся соответствующие подсчеты цикла и т. Д.

Я только что проверил оценку статической стоимости модели для векторизованной версии вашего кода, используя один из выводов report (или «Intel Vectorization Advisor») ICC.

• Для SSE генерации кода это было: 0.5x (т.е. замедление)
• Для AVX генерации кода это было: 1.1x скорость вверх (как верхняя граница)
• Для AVX2 генерация кода это было: 1.3x - 1.4x ускорение (как верхняя граница).

Итак, помните, что все эти скоростные окна являются оптимистические верхние границы, предоставляемые очень хороший оптимизирующий компилятор (я не знаю, если GCC будет лучше или хуже). В зависимости от ваших макетов индексов, размера матрицы и общего баланса латентности, а также некоторых других причин - вы часто будете ниже, чем 1.4x, даже для AVX2, вряд ли ожидая значительных ускорений. Чтобы сделать такой шаблон доступа действительно прибыльным, вам нужны дополнительные (векторизованные) вычисления с X [k] в теле цикла, чтобы амортизировать накладные расходы (в отличие от простого копирования данных из одного места в другое).

В то же время есть хорошие новости. Для краткосрочного будущего AVX-512 машины (KNL Xeon Phi, некоторые будущие Xeon) производительность vgather, скорее всего, изменится/улучшится, так что даже простая копия данных может дать дополнительные ускорения, но в любом случае это не то, что вы будете наблюдать на сегодняшних машинах AVX/AVX2.

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

Answer 4

Это можно сделать на ARM NEON через инструкцию VTBL.

NEON может обрабатывать LUT до 32 байт довольно быстро.