Войти
ПрограммированиеФорумОбщее

SIMD оптимизации

Страницы: 1 2 325 26 Следующая »
#0
0:39, 20 янв. 2018

Решил сравнить скорость скалярного кода vs SSE2 vs AVX. Для меня это актуально, так как у меня в синтезаторе почти половину времени занимает микширование звуков, которое в скалярном виде выглядит так:

void AddMultipliedScalar(float* dst, const float* src, int n, float coeff)
{
  while(n)
  {
    //Развёрнутый цикл на 15% быстрее
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    *dst++ += coeff * *src++;
    n -= 8;
  }
}
Попробовал переписать его на SSE2 интринсики:
void AddMultipliedSSE(float* dst, const float* src, int n, float coeff)
{
  auto c = _mm_set1_ps(coeff);
  auto srcEnd = src + n;
  auto dstEnd = dst + n;
  while(dst != dstEnd)
  {
    auto a = _mm_load_ps(dst);
    auto b = _mm_load_ps(src);
    auto d = _mm_add_ps(a, _mm_mul_ps(b, c));
    _mm_store_ps(dst, d);
    dst += 4;
    src += 4;

    //Развёрнутый цикл немного быстрее
    a = _mm_load_ps(dst);
    b = _mm_load_ps(src);
    d = _mm_add_ps(a, _mm_mul_ps(b, c));
    _mm_store_ps(dst, d);
    dst += 4;
    src += 4;
  }
}

И на AVX:

void AddMultipliedAVX(float* dst, const float* src, int n, float coeff)
{
  auto c = _mm256_set1_ps(coeff);
  auto srcEnd = src + n;
  auto dstEnd = dst + n;
  while(dst != dstEnd)
  {
    auto a = _mm256_load_ps(dst);
    auto b = _mm256_load_ps(src);
    auto d = _mm256_add_ps(a, _mm256_mul_ps(b, c));
    _mm256_store_ps(dst, d);
    src += 8;
    dst += 8;

    a = _mm256_load_ps(dst);
    b = _mm256_load_ps(src);
    d = _mm256_add_ps(a, _mm256_mul_ps(b, c));
    _mm256_store_ps(dst, d);
    src += 8;
    dst += 8;
  }
}
В моём тесте dst имеет размер 1024 float'а, src - 300000000 float'ов. Последовательно берётся по 1024 элемента из большого массива и все они суммируются в dst. Получается, что dst полностью помещается в L1 кеш и не выходит оттуда, а src не помещается ни в какой из кешей и каждый раз считывается из RAM. Именная такая ситуация в моём синтезаторе. Есть посчитанные ранее волновые таблицы, которые не влезают в кеш, и их фрагменты миксуются в массив размером 1024 семпла. Такой объём вычислений нужно произвести, чтобы посчитать 5 минут музыки при одновременном звучании 10 нот в среднем.
С учётом того, что у меня память двухканальная DDR3-1600, я ожидал, что я смогу максимум обработать 1600 МГц * 2 * 8 байт  = 25,6 ГБ\с = 6,4 миллиардов элементов в секунду.
Скалярная версия выполнялась 123 мс. К ней в принципе вопросов нет, если не считать то, что почему-то компилятор не смог векторизовать такой простой случай, при том, что в настройках включены полная оптимизация и AVX2.
SSE версия выполнялась 46 мс - почему в 3 раза быстрее, а не 4? Вроде идеальный случай. Все данные выровнены и даже никакие хвосты не обрабатываются, которые могли бы слегка исказить измерения. В память ещё не упирается, хотя почти впритык под расчитанный мной теоретический предел скорости памяти.
А вот AVX-версия меня удивила, она посчитала всё за 30 мс! 300000000 / 0.030 с * sizeof(float) = 40 ГБ\с! Как AVX смог превысить теоретическую пропускную способность памяти?

Ещё наверное завтра попробую FMA-инструкции. Интересно, будет ли ещё быстрее?


#1
1:06, 20 янв. 2018

gammaker
> если не считать то, что почему-то компилятор не смог векторизовать такой простой случай,
Компилятор не знает. что src и dst не пересекаются.

Кстати, какой компилятор? Дизасм покажешь?

> Ещё наверное завтра попробую FMA-инструкции. Интересно, будет ли ещё быстрее?
Вроде должно.

> 1600 МГц * 2 * 8 байт
Откуда 2 * 8?
https://en.wikipedia.org/wiki/DDR3_SDRAM

#2
(Правка: 1:23) 1:23, 20 янв. 2018

gcc, кстати, генерит проверку и 2 версии, для пересекающихся и нет
https://godbolt.org/g/h28HTg

А шланг все анроллит

#3
9:38, 20 янв. 2018

gammaker
0. Что CPU-Z говорит про твою память?

1. Как меняется результат от замены инкремента на смещение?

while(n)
  {
    //Развёрнутый цикл на 15% быстрее
    dst[0] += coeff * *src[0];
    dst[1] += coeff * *src[1];
    dst[2] += coeff * *src[2];
    dst[3] += coeff * *src[3];
    dst[4] += coeff * *src[4];
    dst[5] += coeff * *src[5];
    dst[6] += coeff * *src[6];
    dst[7] += coeff * *src[7];
    n -= 8;
    src+=8;
    dst+=8;
  }
и
while(dst != dstEnd)
  {
    auto a = _mm_load_ps(dst);
    auto b = _mm_load_ps(src);
    auto d = _mm_add_ps(a, _mm_mul_ps(b, c));
    _mm_store_ps(dst, d);

    //Развёрнутый цикл немного быстрее
    a = _mm_load_ps(dst+4);
    b = _mm_load_ps(src+4);
    d = _mm_add_ps(a, _mm_mul_ps(b, c));
    _mm_store_ps(dst+4, d);
    dst += 8;
    src += 8;
  }
GCC вроде генерирует одинаковый код, что здесь, что там.

2. Что говорит IACA?
https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

Faceroll
Не уверен, что отдельный edx быстрее, чем cmp rax.

#4
17:10, 20 янв. 2018

Оказалось, что я поторопился и вообще неправильный тест сделал. Забыл увеличивать указатель на src и соответственно всё читалось только из первых 1024 элементов первого массива - всё в L1 кеше. Тогда даже странно, чего это оно ещё быстрее не работало. Ну ладно, этот случай не типичный для моего синтезатора, поэтому мне не интересен.
А ещё я с оценками ошибся в 10 раз. Это не 5 минут звучания музыки, а всего лишь 31 секунда.

FordPerfect
> Компилятор не знает. что src и dst не пересекаются.
Поставил __restrict, теперь он векторизовал, но почему-то только при включённом AVX (SSE не хочет) и только в моём варианте развёрнутого цикла. Но ручной код через интринсики всё равно немного быстрее.

>Кстати, какой компилятор? Дизасм покажешь?
Я меряю на MSVC 2015. На godbolt есть только 2017, так что чтобы сравнивать наверняка, придётся мне починить 2017-ю студию. У меня уже много функций накопилось, я их распишу и дизасм ниже выложу. Ещё потом протестирую на GCC и Clang.

FordPerfect
> Откуда 2 * 8?
2 плашки на разных каналах, шина 64 бита (8 байт).

>0. Что CPU-Z говорит про твою память?
CPU-Z память | SIMD оптимизации

> 1. Как меняется результат от замены инкремента на смещение?
После того, как я поправил тест, разница между развёрнутым и не развёрнутым стала в пределах погрешности +-2%. И то и то скачет в районе 145 мс, и даже мой развёрнутый по-моему часто оказывается выше. Твой развёрнутый вариант тоже рядом, но всё же чуть быстрее и в среднем выигрывает у неоптимизированного варианта.

>2. Что говорит IACA?
Попозже посмотрю.

Ссылки на godbolt для MSVC 2017:
scalar.cpp - здесь расширенные инструкции процессора выключены
sse.cpp - здесь включено SSE2, соответственно компилятор мог бы векторизовать циклы, но почему-то не стал
avx.cpp - здесь включено AVX2 и компилятор векторизовал один из вариантов с развёрнутым циклом и с __restrict
main.cpp - код, запускающий тесты, на asm тут смысла смотреть нет
Сам я ещё не очень смотрел в асм, я с ним не очень дружу. Лучше пока больше тестов сделаю. Если кто увидит что интересное, пишите.


Вот результаты на моём ноуте:

Scalar
AddMultipliedScalar                    146.231 ms      7.64261 GB/s    sum = 20169
AddMultipliedScalarUnrolled            146.384 ms      7.63463 GB/s    sum = 20169
AddMultipliedScalarUnrolledRestrict    147.533 ms      7.57517 GB/s    sum = 20169
AddMultipliedScalarUnrolled2            145.375 ms      7.68761 GB/s    sum = 20169
AddMultipliedScalarUnrolled2Restrict    143.345 ms      7.79648 GB/s    sum = 20169

SSE
AddMultipliedSSE                        79.803 ms      14.0043 GB/s    sum = 20169
AddMultipliedRestrictSSE                79.836 ms      13.9985 GB/s    sum = 20169
AddMultipliedAutoSSE                    155.823 ms      7.17216 GB/s    sum = 20169
AddMultipliedUnrolledAutoSSE            146.698 ms      7.61828 GB/s    sum = 20169
AddMultipliedUnrolledRestrictAutoSSE    199.808 ms      5.5933 GB/s    sum = 20169
AddMultipliedUnrolled2AutoSSE          149.055 ms      7.49782 GB/s    sum = 20169
AddMultipliedUnrolled2RestrictAutoSSE  149.983 ms      7.45142 GB/s    sum = 20169

AVX
AddMultipliedAVX                        72.351 ms      15.4467 GB/s    sum = 20169
AddMultipliedRestrictAVX                72.248 ms      15.4688 GB/s    sum = 20169
AddMultipliedAutoAVX                    141.233 ms      7.91307 GB/s    sum = 20169
AddMultipliedUnrolledAutoAVX            144.317 ms      7.74397 GB/s    sum = 20169
AddMultipliedUnrolledRestrictAutoAVX    74.504 ms      15.0004 GB/s    sum = 20169
AddMultipliedUnrolled2AutoAVX          143.467 ms      7.78985 GB/s    sum = 20169
AddMultipliedUnrolled2RestrictAutoAVX  141.785 ms      7.88227 GB/s    sum = 20169


AVX не особо быстрее SSE2. Максимальная скорость чтения из src получилась 15.4 ГБ/с, как-то маловато. Первые пять скалярных функций скопипащены и в SSE и в AVX, чтобы посмотреть, как компилятор их оптимизирует при разных настройках оптимизации.
Сейчас ещё попробую FMA. И надо бы глянуть, что там в GCC и Clang. В них есть ещё удобные расширения языка с SIMD типами, надо их тоже протестировать.
А ещё чтобы до конца убедиться, что действительно упирается в память, надо попробовать несколько потоков.

#5
(Правка: 17:16) 17:16, 20 янв. 2018
Блин, какая крутая штука этот https://godbolt.org/, а я и не знал что такой есть!!!
#6
17:26, 20 янв. 2018

gammaker
> Сейчас ещё попробую FMA.

Думаю что лучше не станет. FMA - для точности, а не скорости

#7
17:36, 20 янв. 2018

innuendo
С чего бы? Вроде сейчас FMA обычно в ту же скорость, что и умножение.
Ну если memory-bound - тогда пофиг.

#8
17:39, 20 янв. 2018

https://stackoverflow.com/questions/15655835/flops-per-cycle-for-… sse2-avx-avx2 :

The newest Intel generation has a more balanced throughput. Floating point addition, multiplication and FMA all have a throughput of 2 instructions per clock cycle and a latency of 4. – A Fog

#9
18:13, 20 янв. 2018

FordPerfect
> The newest Intel generation has a more balanced throughput. Floating point
> addition, multiplication and FMA all have a throughput of 2 instructions per
> clock cycle and a latency of 4. – A Fog
Это видимо не про мой проц, у меня Haswell. Но вообще я больше хочу оптимизировать не под конкретные процессоры, а под все, включая ARM-старьё, которое скорее всего не потянет мой синтезатор в реальном времени в текущей его версии. Из спортивного интереса хочу оптимизировать его под Raspberry Pi 1 (или Zero). RPi интересен тем, что там есть сопроцессор (QPU), который работает с широкими регистрами - по 16 чисел в каждом. Но пока я решил в принципе реализовать все алгоритмы на SIMD и сделать кроссплатформенную реализацию SIMD в своей либе с возможностью реализации алгоритма один раз и компиляции его под SSE\AVX\FMA\AVX512\NEON и может быть даже QPU, если получится уместить его в свою абстракцию.

#10
18:26, 20 янв. 2018

gammaker
> gammaker

for(dst<mexDst){
dst0,dst1,dst2,dst3 = 0
 src = srcBase;
 srcBase+=4;
for(src<mexSrc){
  cpu закешируй данные по адрессу src+1024
  a = src[0]
  b = src[4]
  c = src[8]
  dst0+= a*coeff;
  dst1+= b*coeff;
  a = src[12]
  dst2+= c*coeff;
  dst3+= a*coeff;

  src+=1024
}
 dst[0] = dst0;  
 dst[1] = dst1;  
 dst[2] = dst2;  
 dst[3] = dst3;  
 dst += 4;
}
#11
18:35, 20 янв. 2018

susageP
Не очень понятен псевдокод. Можешь словами описать идею, что ты предлагаешь и для чего?

#12
18:36, 20 янв. 2018

gammaker
> мой проц
http://www.agner.org/optimize/blog/read.php?i=415

The Haswell and Broadwell have two execution units for floating point multiplication and FMA, but only one for addition. This is odd since most floating point code has more additions than multiplications. To get the maximum floating point throughput on these processors, one might have to replace some additions with FMA instructions with a multiplier of 1. Fortunately, the Skylake has fixed this imbalance and made two floating point arithmetic units, both of which can handle both addition, multiplication and FMA. This gives a maximum throughput of two floating point vector operations per clock cycle.

Векторные расширения GCC - кавайные, но в Студии нет.
Если выберешь себе обёртку над SIMD - интересно, которую.

#13
(Правка: 18:51) 18:49, 20 янв. 2018

FordPerfect
> To get the maximum floating point throughput on these processors, one might
> have to replace some additions with FMA instructions with a multiplier of 1.
Это видел ещё в прошлой твоей ссылке на stackoverflow. Сейчас реализую FMA-версию и посмотрим.

FordPerfect
> Векторные расширения GCC - кавайные, но в Студии нет.
>кавайные
Какие-какие?

FordPerfect
> Если выберешь себе обёртку над SIMD - интересно, которую.
Свою собственную. Собираюсь сделать классы float16Scalar, float16SSE, float16AVX, float16AVX512, float16Neon и в зависимости от настроек компиляции делать typedef float16{...} float16 для одной из них. У этих классов перегрузить операторы на реализации через соответствующие инструкции. Надо только будет сделать тесты, чтобы проверить, что всё хорошо инлайнится и нет оверхеда.
А в GCC и Clang можно просто использовать встроенные векторные расширения. Там уже такие типы встроенные есть, надо только typedef сделать.
Ещё нужно будет сделать функции типа Floor, Sqrt, Sin.
И все алгоритмы буду реализовывать в терминах float16.

#14
18:59, 20 янв. 2018

gammaker
> Не очень понятен псевдокод. Можешь словами описать идею, что ты предлагаешь и
> для чего?
gammaker
> В моём тесте dst имеет размер 1024 float'а, src - 300000000 float'ов.
> Последовательно берётся по 1024 элемента из большого массива и все они
> суммируются в dst.

Так как кеширование происходит по 64байта то можно кеш линию хранить в регистрах, в 4шт.
поэтому считай с начало первые 16 чисел для dst.  с шагом 1024float из src. и только потом сохраняй в памяти уже посчитанный полностью.
переходи к следующий 16числам. и так далее.

Есть инструкция кэшировать данные по такому адресу. вот ее надо вызывать в начале цикла для адреса по которому будет чтение в следующей итерации.

Страницы: 1 2 325 26 Следующая »
ПрограммированиеФорумОбщее