AVX 256-битный код, выполняющий несколько хуже, чем эквивалентный 128-битный код SSSE3

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

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

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

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

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

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

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

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

Тест-машина - это Intel Corei7 4790, и я использую Visual Studio 2012 Pro.

Ответы

Ответ 1

В дополнение к незначительным проблемам в комментариях (компиляция для /arch:AVX) основной проблемой является генерация случайных входных массивов на каждой итерации. Это ваше узкое место, поэтому ваш тест неэффективно оценивает ваши методы. Примечание. Я не использую boost, но 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

Итак, 2309ms для завершения... но что произойдет, если мы вообще избавимся от вашей обычной программы 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 здесь). Урок должен быть уверен, что вы на самом деле профилируете то, что, по вашему мнению, профилируете!

Ответ 2

Вам следует использовать обычную команду _mm_popcnt_u64 вместо того, чтобы взломать ее в SSE или AVX. Я тестировал все методы для полномасштабного заполнения, включая версию SSE и AVX (что в конечном итоге привело к моему более или менее известному вопросу о popcount). _mm_popcnt_u64 значительно превосходит SSE и AVX, особенно когда вы используете компилятор, который предотвращает ошибку popcount Intel, обнаруженную в моем вопросе. Без ошибки мой Хасуэлл может собрать 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 работает медленнее, но поскольку ваша конечная цель - быстрый popcount, сравнение AVX ↔ SSE не имеет значения, поскольку оба уступают встроенному popcount.