Найдите 4 минимальных значения в 4 регистрах __m256d

Возможно, было бы лучше сделать некоторые сравнения SIMD, чтобы уменьшить до 8 или 4 (как у вас сейчас) кандидатов, а затем распаковать в скалярные двойники в векторных регистрах. Это не должно включать обход памяти: vextractf128 старшая половина (_mm256_extractf128_pd) и преобразование младшей половины. Возможно, используйте movhlps (_mm_movehl_ps), чтобы преобразовать старшую половину __m128 в младшую половину (хотя на процессорах с AVX вы экономите только один или два байта кода от использования этого вместо случайного перемешивания с немедленным; это не быстрее, чем это есть на некоторых старых процессорах).

IDK, распаковка с перетасовкой или просто сохранение - это путь. Возможно, сочетание того и другого, чтобы порты перемешивания и порты сохранения / загрузки были заняты, было бы хорошо. Очевидно, что младший двойник в каждом векторе уже присутствует как скаляр, так что вам не нужно его загружать. (И компиляторы плохо разбираются в том, как хранить и перезагружать как скаляры, чтобы воспользоваться этим, даже для локального массива.)

Даже не сильно сужая набор кандидатов, некоторые SIMD-компараторы перед распаковкой могут уменьшить количество перестановок/перетасовок, ожидаемых от разветвленного скалярного кода, уменьшая штрафы за неправильное предсказание ветвления.

Как я описал в комментариях к ответу Пола Р., в скалярном коде вы, вероятно, преуспеете с алгоритмом сортировки вставкой. Но это больше похоже на приоритетную очередь: вставлять только в первые 4 элемента. Если новый кандидат больше, чем самый большой существующий кандидат, просто двигайтесь дальше. В противном случае отсортируйте его вставкой в ​​​​список из 4 кандидатов, которые вы поддерживаете в отсортированном порядке.

Я нашел действительно хорошую статью о сетях сортировки SIMD с конкретными обсуждение AVX. Они подробно рассказывают о необходимых перетасовках при использовании SIMD-инструкций Packed-min/Packed-Max для сортировки пары векторных регистров данных. Они даже используют встроенные функции, такие как _mm512_shuffle_epi32, в своих примерах. Они говорят, что их результаты применимы к AVX, хотя в своих примерах они используют регистры маски AVX-512.

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

Кстати, я написал предыдущий ответ с некоторыми не очень хорошими идеями о сортировке 64-битных структур по члену float, но это здесь это не совсем применимо, поскольку я рассматривал только сложности работы с полезной нагрузкой (которой у вас нет).

У меня сейчас нет времени, чтобы закончить этот ответ, поэтому я просто опубликую краткое изложение своей идеи:

Адаптируйте двухрегистровый метод из этого документа к AVX (или AVX2). Я не уверен, как лучше всего эмулировать их минимальные/максимальные инструкции AVX512 в маске. :/ Я могу обновить это позже. Возможно, вы захотите написать авторам по электронной почте и спросить о коде, который они использовали для тестирования процессора настольного компьютера.

В любом случае, используйте функцию 2 регистров на парах регов, чтобы уменьшить с 4 до 2 рег, а затем снова уменьшить до 1 рег. В отличие от вашей версии, их версия создает полностью отсортированный выходной регистр.

Попытка избежать перетасовки между дорожками, когда это возможно, может быть сложной задачей. Я не уверен, что вы можете получить что-то от использования shufpd (__m256d _mm256_shuffle_pd (__m256d a, __m256d b, const int select);) для объединения данных из двух исходных регистров во время перетасовки. Версия 256b может делать разные перетасовки на каждой дорожке, используя 4 бита imm8 вместо 2.

Это интересная проблема, но я, к сожалению, не должен тратить время на то, чтобы написать полное решение самостоятельно. Если бы у меня было время, я бы хотел сравнить приоритетную очередь сортировки вставками и полностью развернутую реализацию той же очереди сортирующей сети с 4, 8, 12 и 16 элементами в каждой. (разные уровни сети сортировки SIMD, прежде чем перейти к скаляру).

Ссылки, которые я нашел:

• Еще одна статья о сортировке SSE с некоторым кодом, использующим palignr для объединения двух два индивидуально отсортированных вектора в отсортированную пару векторов из 8 элементов. Неприменимо напрямую к 256b векторам двойников.
• Еще один документ о сортировке SSE с результатами тестирования процессоров Core2. Он использует неэффективную смесь/смешивание/перетасовку для перетасовки между двумя векторами из-за ограничений shufps. На полосе shufpd действуют немного другие ограничения. Возможно, этот документ стоит внимательно изучить. У них есть алгоритмы, которые работают с реальными векторами SSE, с доступными операциями перемешивания.
• Документ Xiaochen, Rocki и Suda уже связан
• Как выглядит глава о сортировке сетей из учебник по алгоритмам CLR.
• Генератор сети сортировки с возможностью выбора алгоритма. Не для SIMD
• https://en.wikipedia.org/wiki/Bitonic_sorter пример диаграммы имеет 16- входная сортировочная сеть. Битонные сортировки используют шаблоны, которые в некоторой степени могут SIMD. Верхнюю часть конца сети можно опустить, так как нас интересует только порядок младших 4.
• Самая быстрая сортировка массива фиксированной длины 6 int. Популярный вопрос, на который есть множество ответов.

Это чисто "горизонтальная" операция и не очень подходит для SIMD - я подозреваю, что будет быстрее просто спрятать четыре вектора в памяти, отсортировать 16 значений, а затем загрузить первые четыре в результирующий вектор:

__m256d min(__m256d A, __m256d B, __m256d C, __m256d D)
{
    double buff[16] __attribute__ ((aligned(32)));

    _mm256_store_pd(&buff[0], A);
    _mm256_store_pd(&buff[4], B);
    _mm256_store_pd(&buff[8], C);
    _mm256_store_pd(&buff[12], D);

    std::partial_sort(buff, buff+4, buff+16);

    return _mm256_load_pd(&buff[0]);    
}

Для повышения производительности вы можете реализовать встроенную пользовательскую процедуру сортировки, которая жестко закодирована для 16 элементов.