SIMD уменьшить 4 вектора без хадда - PullRequest
Новая
       91

SIMD уменьшить 4 вектора без хадда

2 голосов
/ 21 марта 2020

Я пытаюсь оптимизировать некоторый код, и я нахожусь в состоянии, в котором у меня есть 4 вектора __m256d, и я хочу сохранить сумму каждого из них внутри другого __m256d. Так что в основном result = [sum(a), sum(b), sum(c), sum(d)]. Я знаю, что есть способ сделать это, используя 2 hasds - смесь и перестановку, но я понял, что hasd слишком дорог.

1 Ответ

2 голосов
/ 22 марта 2020

Три варианта:

  • 1 транспонирование матрицы, затем вертикальная сумма

хорошо: концептуально просто, с использованием общепринятого алгоритма (транспонирование матрицы), переносимый код

плохо: размер кода, задержка, пропускная способность

  • 2 с использованием vhaddpd эффективно

хорошо: небольшой код (хорошо для Icache), хорошая задержка и пропускная способность на Intel uArchs

плохо: требуется код архитектуры c, проблемный c на некоторых uArch

  • 3 частичное транспонирование, сумма, частичное транспонирование, сумма

хорошо: хорошая задержка, хорошая пропускная способность

плохо: не так мало, как vhaddpd -код, не так легко понять, как полная транспонирование матрицы

Matrix Transpose, Вертикальная сумма

Ваш компилятор оптимизирует это для вас. С gcc векторными расширениями * код для суммирования по транспонированной матрице может выглядеть следующим образом: 

#include <stdint.h>

typedef uint64_t v4u64 __attribute__((vector_size(32)));
typedef double v4f64  __attribute__((vector_size(32)));

v4f64 dfoo(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 tv[4];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});
  v4f64 fv[4];
  fv[0] = __builtin_shuffle(tv[0], tv[2], (v4u64){0,1,4,5});
  fv[1] = __builtin_shuffle(tv[0], tv[2], (v4u64){2,3,6,7});
  fv[2] = __builtin_shuffle(tv[1], tv[3], (v4u64){0,1,4,5});
  fv[3] = __builtin_shuffle(tv[1], tv[3], (v4u64){2,3,6,7});
  return fv[0]+fv[1]+fv[2]+fv[3];
}

gcc-9.2.1 создает следующую сборку: 

dfoo:
    vunpcklpd   %ymm3, %ymm2, %ymm5
    vunpcklpd   %ymm1, %ymm0, %ymm4
    vunpckhpd   %ymm1, %ymm0, %ymm0
    vinsertf128 $1, %xmm5, %ymm4, %ymm1
    vperm2f128  $49, %ymm5, %ymm4, %ymm4
    vunpckhpd   %ymm3, %ymm2, %ymm2
    vaddpd  %ymm4, %ymm1, %ymm1
    vinsertf128 $1, %xmm2, %ymm0, %ymm3
    vperm2f128  $49, %ymm2, %ymm0, %ymm0
    vaddpd  %ymm3, %ymm1, %ymm1
    vaddpd  %ymm0, %ymm1, %ymm0
    ret

Таблицы Агнера Фога говорят :

  • vunpck[h/l]pd: задержка 1 цикла, 1 пропускная способность на цикл, 1 порт uOP5.
  • vinsertf128: задержка 3 циклов, 1 пропускная способность на цикл, 1 порт uOP5.
  • vperm2f128: задержка 3 цикла, 1 пропускная способность на цикл, 1 порт uOP5.
  • vaddpd: задержка 4 цикла, 2 пропускная способность на цикл, 1 порт uOP01.

Всего имеется

  • 4 [распаковать] + 2 [вставить] + 2 [переставить] = 8 портов5 uOP.
  • 3 [добавить] = 3 port01 uOPs.

Пропускная способность будет узким местом на порту 5. Задержка довольно плоха в ~ 18 циклах. Размер кода составляет около 60 байт.

Горизонтальная сумма

Код (разумно) с использованием vhadd нелегко получить с помощью векторных расширений g cc, поэтому для кода требуется спецификация Intel c intrinsics: 

v4f64 dfoo_hadd(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 hv[2];
  hv[0] = __builtin_ia32_haddpd256(sv0, sv1); //[00+01, 10+11, 02+03, 12+13]
  hv[1] = __builtin_ia32_haddpd256(sv2, sv3); //[20+21, 30+31, 22+23, 32+33]
  v4f64 fv[2];
  fv[0] = __builtin_shuffle(hv[0], hv[1], (v4u64){0, 1, 4, 5}); //[00+01, 10+11, 20+21, 30+31]
  fv[1] = __builtin_shuffle(hv[0], hv[1], (v4u64){2, 3, 6, 7}); //[02+03, 12+13, 22+23, 32+33]
  return fv[0] + fv[1]; //[00+01+02+03, 10+11+12+13, 20+21+22+23, 30+31+32+33]
}

, при этом создается следующая сборка: 

dfoo_hadd:
    vhaddpd %ymm3, %ymm2, %ymm2
    vhaddpd %ymm1, %ymm0, %ymm0
    vinsertf128 $1, %xmm2, %ymm0, %ymm1
    vperm2f128  $49, %ymm2, %ymm0, %ymm0
    vaddpd  %ymm0, %ymm1, %ymm0
    ret

Согласно таблицам инструкций Agner Fog,

  • vhaddpd: 6 циклов задержка, пропускная способность 0,5 за цикл, 3 uOPS port01 + 2 * port5.

Всего всего

  • 4 [hadd] + 2 [insert / permute] = 6 uOPs port5.
  • 3 [hadd / add] = 3 uOPs port01.

Пропускная способность также ограничена портом 5, и это имеет большую пропускную способность, чем код транспонирования. Задержка должна составлять ~ 16 циклов, также быстрее, чем транспонирование кода. Размер кода составляет около 25 байт.

Частичное транспонирование, Сумма, Частичное транспонирование, Сумма

Реализация комментария @PeterCordes: 

v4f64 dfoo_PC(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 tv[4];
  v4f64 av[2];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});//[00, 10, 02, 12]
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});//[01, 11, 03, 13]
  av[0] = tv[0] + tv[1];//[00+01, 10+11, 02+03, 12+13]
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});//[20, 30, 22, 32]
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});//[21, 31, 23, 33]
  av[1] = tv[2] + tv[3];//[20+21, 30+31, 22+23, 32+33]
  v4f64 fv[2];
  fv[0] = __builtin_shuffle(av[0], av[1], (v4u64){0,1,4,5});//[00+01, 10+11, 20+21, 30+31]
  fv[1] = __builtin_shuffle(av[0], av[1], (v4u64){2,3,6,7});//[02+03, 12+13, 22+23, 32+33]
  return fv[0]+fv[1];//[00+01+02+03, 10+11+12+13, 20+21+22+23, 30+31+32+33]
}

Это создает: 

dfoo_PC:
    vunpcklpd   %ymm1, %ymm0, %ymm4
    vunpckhpd   %ymm1, %ymm0, %ymm1
    vunpcklpd   %ymm3, %ymm2, %ymm0
    vunpckhpd   %ymm3, %ymm2, %ymm2
    vaddpd  %ymm1, %ymm4, %ymm1
    vaddpd  %ymm2, %ymm0, %ymm2
    vinsertf128 $1, %xmm2, %ymm1, %ymm0
    vperm2f128  $49, %ymm2, %ymm1, %ymm1
    vaddpd  %ymm1, %ymm0, %ymm0
    ret

Всего имеется

  • 4 [распаковать] + 2 [вставить / переставить] = 6 портов5 uOP.
  • 3 [добавить] = 3 порта01 uOP.

Получает то же количество портов 5 uOP, что и hadd -код. Код все еще является узким местом на порту 5, задержка составляет около ~ 16 циклов. Размер кода составляет около 41 байта.

Если вы хотите увеличить пропускную способность, вам придется перенести работу с порта 5. К сожалению, почти все инструкции по перестановке / вставке / перемешиванию требуют порта 5, а инструкции по пересечению полос (которые здесь необходимы) имеют минимальную задержку в 3 цикла. Одна интересная инструкция, которую помогает почти , - это vblendpd, которая имеет пропускную способность 3 / цикла, задержку 1 цикла и может выполняться на порте 015, но для ее использования для замены одной из перестановок / вставки / перемешиваний потребуется 64-битное смещение 128-битной дорожки вектора, которое реализуется vpsrldq/vpslldq, который, как вы уже догадались, требует u5 порта (так что поможет с векторами 32-бит *) 1116 *, потому что vpsllq/vpsrlq делает не требует порт 5). Здесь нет бесплатного обеда.

* g cc векторные расширения Краткое описание:

Код использует векторные расширения g cc, которые позволяют использовать операторы basi c (+-*/=><>><< et c.) По векторам, работающим поэлементно. Они также включают в себя несколько __builtin_* функций, в частности __builtin_shuffle(), которая имеет форму с 3 операндами, где первые два представляют собой два (одинаковой длины N) вектора одного и того же типа T, которые (логически) объединяются в вектор двойной длины (2N) этого типа T, третий - это вектор целочисленного типа (IT) той же ширины и длины (N), что и тип исходных векторов. В результате получается вектор того же типа T и ширины N исходного вектора с элементами, выбранными по индексам в векторе целочисленного типа.

Первоначально мой ответ был о uint64_t, сохраненный здесь для context: 

 #include <stdint.h>

typedef uint64_t v4u64 __attribute__((vector_size(32)));

v4u64 foo(v4u64 sv0, v4u64 sv1, v4u64 sv2, v4u64 sv3)
{
  v4u64 tv[4];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});
  v4u64 fv[4];
  fv[0] = __builtin_shuffle(tv[0], tv[2], (v4u64){0,1,4,5});
  fv[1] = __builtin_shuffle(tv[0], tv[2], (v4u64){2,3,6,7});
  fv[2] = __builtin_shuffle(tv[1], tv[3], (v4u64){0,1,4,5});
  fv[3] = __builtin_shuffle(tv[1], tv[3], (v4u64){2,3,6,7});
  return fv[0]+fv[1]+fv[2]+fv[3];
}

Перевод, сгенерированный gcc-9.2.1 на skylake-avx2, может выглядеть следующим образом: 

foo:
    vpunpcklqdq %ymm3, %ymm2, %ymm5
    vpunpcklqdq %ymm1, %ymm0, %ymm4
    vpunpckhqdq %ymm3, %ymm2, %ymm2
    vpunpckhqdq %ymm1, %ymm0, %ymm0
    vperm2i128  $32, %ymm2, %ymm0, %ymm3
    vperm2i128  $32, %ymm5, %ymm4, %ymm1
    vperm2i128  $49, %ymm2, %ymm0, %ymm0
    vperm2i128  $49, %ymm5, %ymm4, %ymm4
    vpaddq  %ymm4, %ymm1, %ymm1
    vpaddq  %ymm0, %ymm3, %ymm0
    vpaddq  %ymm0, %ymm1, %ymm0
    ret

Обратите внимание, что сборка имеет почти строку для соответствия строки g cc векторные расширения.

Согласно таблицам инструкций Агнера Фога для Skylake,

  • vpunpck[h/l]qdq: задержка 1 цикла, пропускная способность 1 на цикл, порт 5.
  • vperm2i128: задержка 3 цикла, пропускная способность 1 на цикл, порт 5.
  • vpaddq: задержка 1 цикла, пропускная способность 3, порты 015.

Таким образом, транспонирование занимает 10 циклов (4 для распаковки, 4 пропускной способности + 2 задержки для перестановки). Из трех добавлений только два могут выполняться параллельно, так что потребуется 2 цикла, всего 12 циклов.

...