256-битный код AVX работает немного хуже, чем эквивалентный 128-битный код SSSE3

Я пытаюсь написать очень эффективный код расстояния Хемминга. Вдохновленный Войцех Мулы очень умный SSE3 попконт реализация, Я кодировал решение, эквивалентное AVX2, на этот раз с использованием 256-битных регистров. Я ожидал улучшения как минимум на 30-40% на основе удвоенного параллелизма задействованных операций, однако, к моему удивлению, код AVX2 немного медленнее (около 2%)!

Может кто-то объяснить мне возможные причины, почему я не получаю ожидаемого повышения производительности?

Развернутая SSE3 дистанция Хэмминга двух 64-байтовых блоков:

INT32 SSE_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {

__m128i paccum  = _mm_setzero_si128();

__m128i a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA));
__m128i b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB));
__m128i err     = _mm_xor_si128   (a, b);
__m128i lo      = _mm_and_si128   (err, low_mask);
__m128i hi      = _mm_srli_epi16  (err, 4);
hi      = _mm_and_si128   (hi, low_mask);
__m128i popcnt1 = _mm_shuffle_epi8(lookup, lo);
__m128i popcnt2 = _mm_shuffle_epi8(lookup, hi);
paccum  = _mm_add_epi8(paccum, popcnt1);
paccum  = _mm_add_epi8(paccum, popcnt2);

a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 4));
b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 4));
err     = _mm_xor_si128   (a, b);
lo      = _mm_and_si128   (err, low_mask);
hi      = _mm_srli_epi16  (err, 4);
hi      = _mm_and_si128   (hi, low_mask);
popcnt1 = _mm_shuffle_epi8(lookup, lo);
popcnt2 = _mm_shuffle_epi8(lookup, hi);
paccum  = _mm_add_epi8(paccum, popcnt1);
paccum  = _mm_add_epi8(paccum, popcnt2);

a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 8));
b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 8));
err     = _mm_xor_si128   (a, b);
lo      = _mm_and_si128   (err, low_mask);
hi      = _mm_srli_epi16  (err, 4);
hi      = _mm_and_si128   (hi, low_mask);
popcnt1 = _mm_shuffle_epi8(lookup, lo);
popcnt2 = _mm_shuffle_epi8(lookup, hi);
paccum  = _mm_add_epi8(paccum, popcnt1);
paccum  = _mm_add_epi8(paccum, popcnt2);

a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 12));
b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 12));
err     = _mm_xor_si128   (a, b);
lo      = _mm_and_si128   (err, low_mask);
hi      = _mm_srli_epi16  (err, 4);
hi      = _mm_and_si128   (hi, low_mask);
popcnt1 = _mm_shuffle_epi8(lookup, lo);
popcnt2 = _mm_shuffle_epi8(lookup, hi);
paccum  = _mm_add_epi8(paccum, popcnt1);
paccum  = _mm_add_epi8(paccum, popcnt2);

paccum  = _mm_sad_epu8(paccum, _mm_setzero_si128());
UINT64  result =  paccum.m128i_u64[0] + paccum.m128i_u64[1];
return (INT32)result;
}

Неуправляемая эквивалентная версия с использованием 256-битных регистров AVX:

INT32 AVX_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {
__m256i paccum =  _mm256_setzero_si256();

__m256i a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA));
__m256i b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB));
__m256i err     = _mm256_xor_si256   (a, b);
__m256i lo      = _mm256_and_si256   (err, low_mask256);
__m256i hi      = _mm256_srli_epi16  (err, 4);
hi      = _mm256_and_si256   (hi, low_mask256);
__m256i popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
__m256i popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
paccum  = _mm256_add_epi8(paccum, popcnt1);
paccum  = _mm256_add_epi8(paccum, popcnt2);

a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA + 8));
b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB + 8));
err     = _mm256_xor_si256   (a, b);
lo      = _mm256_and_si256   (err, low_mask256);
hi      = _mm256_srli_epi16  (err, 4);
hi      = _mm256_and_si256   (hi, low_mask256);
popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
paccum  = _mm256_add_epi8(paccum, popcnt1);
paccum  = _mm256_add_epi8(paccum, popcnt2);

paccum  = _mm256_sad_epu8(paccum, _mm256_setzero_si256());
UINT64  result =  paccum.m256i_i64[0] + paccum.m256i_u64[1] + paccum.m256i_i64[2] + paccum.m256i_i64[3];
return (INT32)result;
}

Я уже проверил выходной код сборки, выданный компилятором, и он выглядит хорошо, с ожидаемым прямым переводом внутренней инструкции в машинную инструкцию. Единственное, что я заметил, это то, что в версии AVX2, последней строке, в которой накоплен счетчик чисел 4-х четырех слов, он генерирует более сложный код, чем в версии SSE3 (где для получения нужно только 2 четырех слова). численность населения), однако я все еще ожидал бы более высокую пропускную способность.

Код AVX2, сгенерированный для накопления четырех слов

vextractf128 xmm0, ymm2, 1
psrldq  xmm0, 8
movd    ecx, xmm2
movd    eax, xmm0
vextractf128 xmm0, ymm2, 1
psrldq  xmm2, 8
add eax, ecx
movd    ecx, xmm0
add eax, ecx
movd    ecx, xmm2
add eax, ecx

Код SSE3, сгенерированный для накопления четырех слов

movd    ecx, xmm2
psrldq  xmm2, 8
movd    eax, xmm2
add eax, ecx

Моя тестовая программа вызывает миллион раз каждую процедуру с разными входными значениями, но повторно использует два статических буфера для хранения данных pA а также pB параметры. В моем ограниченном понимании архитектуры ЦП эта местность (повторное использование одних и тех же буферов памяти снова и снова) должна хорошо подогревать кэш ЦП и не быть связана с проблемой пропускной способности памяти, но кроме возможной пропускной способности памяти, я не могу понять, почему нет улучшения производительности.

Тестовая программа

int _tmain(int argc, _TCHAR* argv[]) {

lookup = _mm_setr_epi8(
/* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
/* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
/* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
/* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
);
low_mask = _mm_set1_epi8(0xf);

lookup256 = _mm256_setr_epi8(
/* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
/* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
/* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
/* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,
/* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
/* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
/* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
/* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
);

low_mask256 = _mm256_set1_epi8(0xf);std::default_random_engine generator;
generator.seed(37);
std::uniform_int_distribution<UINT32> distribution(0, ULONG_MAX);
auto dice = std::bind( distribution, generator);UINT32 a[16];
UINT32 b[16];

int count;
count = 0;
{
cout << "AVX PopCount\r\n";
boost::timer::auto_cpu_timer t;
for( int i = 0; i < 1000000; i++ ) {
for( int j = 0; j < 16; j++ ) {
a[j] = dice();
b[j] = dice();
}
count+= AVX_PopCount(a, b);
}
}

cout << count << "\r\n";std::default_random_engine generator2;
generator2.seed(37);
std::uniform_int_distribution<UINT32> distribution2(0, ULONG_MAX);
auto dice2 = std::bind( distribution2, generator2);count = 0;
{
cout << "SSE PopCount\r\n";
boost::timer::auto_cpu_timer t;
for( int i = 0; i < 1000000; i++ ) {
for( int j = 0; j < 16; j++ ) {
a[j] = dice2();
b[j] = dice2();
}
count+= SSE_PopCount(a, b);
}
}
cout << count << "\r\n";

getch();
return 0;
}

Тестовый компьютер — Intel Corei7 4790, и я использую Visual Studio 2012 Pro.

17

Решение

Помимо мелких вопросов в комментариях (составление для /arch:AVXВаша основная проблема — генерирование случайных входных массивов на каждой итерации. Это ваше узкое место, поэтому ваш тест не позволяет эффективно оценивать ваши методы. Примечание — я не использую повышение, но GetTickCount работает для этого. Рассмотрим просто:

int count;
count = 0;
{
cout << "AVX PopCount\r\n";
unsigned int Tick = GetTickCount();
for (int i = 0; i < 1000000; i++) {
for (int j = 0; j < 16; j++) {
a[j] = dice();
b[j] = dice();
}
count += AVX_PopCount(a, b);
}
Tick = GetTickCount() - Tick;
cout << Tick << "\r\n";
}

производит вывод:

AVX PopCount
2309
256002470

Итак, 2309 мс до завершения … но что произойдет, если мы вообще избавимся от вашей рутины AVX? Просто сделайте входные массивы:

int count;
count = 0;
{
cout << "Just making arrays...\r\n";
unsigned int Tick = GetTickCount();
for (int i = 0; i < 1000000; i++) {
for (int j = 0; j < 16; j++) {
a[j] = dice();
b[j] = dice();
}
}
Tick = GetTickCount() - Tick;
cout << Tick << "\r\n";
}

производит вывод:

Просто делаю массивы …
2246

Как насчет этого. Не удивительно, потому что вы генерируете 32 случайных числа, которые могут быть довольно дорогими, а затем выполняете только некоторые довольно быстрые целочисленные математические вычисления и тасования.

Так…

Теперь давайте добавим в 100 раз больше итераций и выведем генератор случайных чисел из замкнутого цикла. Компиляция здесь с отключенными оптимизациями запустит ваш код, как и ожидалось, и не будет отбрасывать «бесполезные» итерации — вероятно, код, который нас интересует, уже (вручную) оптимизирован!

    for (int j = 0; j < 16; j++) {
a[j] = dice();
b[j] = dice();
}

int count;
count = 0;
{
cout << "AVX PopCount\r\n";
unsigned int Tick = GetTickCount();
for (int i = 0; i < 100000000; i++) {
count += AVX_PopCount(a, b);
}
Tick = GetTickCount() - Tick;
cout << Tick << "\r\n";
}

cout << count << "\r\n";

count = 0;
{
cout << "SSE PopCount\r\n";
unsigned int Tick = GetTickCount();
for (int i = 0; i < 100000000; i++) {
count += SSE_PopCount(a, b);
}
Tick = GetTickCount() - Tick;
cout << Tick << "\r\n";
}
cout << count << "\r\n";

производит вывод:

AVX PopCount
3744
730196224
SSE PopCount
5616
730196224

Так что поздравляю — вы можете похлопать себя по спине, ваша подпрограмма AVX действительно примерно на треть быстрее, чем подпрограмма SSE (тестируется на Haswell i7 здесь). Урок состоит в том, чтобы убедиться, что вы на самом деле профилируете то, что, по вашему мнению, профилируете!

13

Другие решения

Вы должны рассмотреть возможность использования обычного _mm_popcnt_u64 инструкция вместо взлома в SSE или AVX. Я тщательно протестировал все методы поп-бухгалтерии, включая версию SSE и AVX (что в конечном итоге привело к моей более или менее известной вопрос о попконте). _mm_popcnt_u64 значительно превосходит SSE и AVX, особенно когда вы используете компилятор, который предотвращает ошибку Intel popcount, обнаруженную в моем вопросе. Без ошибки мой Haswell может подсчитать 26 ГБ / с, что почти достигает пропускной способности шины.

Причина по которой _mm_popcnt_u64 Быстрее, это просто из-за того, что он подсчитывает 64 бита за раз (так уже 1/4 версии AVX), при этом требуется только одна дешевая инструкция процессора. Это стоит всего несколько циклов (задержка 3, пропускная способность 1 для Intel). Даже если для каждой используемой вами инструкции AVX требуется только один цикл, вы все равно получите худшие результаты из-за огромного количества инструкций, необходимых для поп-монтирования 256 бит.

Попробуйте это, это должно быть быстрее:

int popcount256(const uint64_t* u){
return _mm_popcnt_u64(u[0]);
+ _mm_popcnt_u64(u[1]);
+ _mm_popcnt_u64(u[2]);
+ _mm_popcnt_u64(u[3]);
}

Я знаю, что это не отвечает на ваш основной вопрос, почему AVX медленнее, но, поскольку ваша конечная цель — быстрое создание поп-музыки, AVX <-> Сравнение SSE не имеет значения, так как оба уступают встроенному попконту.

10

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector