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

Question

Я не могу понять, как реализовать:

__m256d min(__m256d A, __m256d B, __m256d C, __m256d D) 
{ 
    __m256d result; 

    // result should contain 4 minimal values out of 16 : A[0], A[1], A[2], A[3], B[0], ... , D[3] 
    // moreover it should be result[0] <= result[1] <= result[2] <= result[2] 

    return result; 
} 

Любые идеи о том, как использовать _mm256_min_pd, _mm256_max_pd и перемешивает/переставляет в умный способ?

=============================================================================================================================================== ====

Это где я получил до сих пор, после того, как:

__m256d T = _mm256_min_pd(A, B); 
    __m256d Q = _mm256_max_pd(A, B); 
    A = T; B = Q; 
    T = _mm256_min_pd(C, D); 
    Q = _mm256_max_pd(C, D); 
    C = T; D = Q; 
    T = _mm256_min_pd(B, C); 
    Q = _mm256_max_pd(B, C); 
    B = T; C = Q; 
    T = _mm256_min_pd(A, B); 
    Q = _mm256_max_pd(A, B); 
    A = T; D = Q; 
    T = _mm256_min_pd(C, D); 
    Q = _mm256_max_pd(C, D); 
    C = T; D = Q; 
    T = _mm256_min_pd(B, C); 
    Q = _mm256_max_pd(B, C); 
    B = T; C = Q; 

мы имеем: A [0] < B [0] < C [0] < D [0], [1] < В [1] < С [1] < D [1], А [2] < В [2] < С [2] < D [2], А [3] < B [3] < C [3] < D [3],

поэтому минимальное значение среди й, второй минимальный является одним из элементов а или Б, ... Не знает, куда идти оттуда ...

=============================================================================================================================================== ==========

Вторая идея заключается в том, что проблема сводима к себе, но с 2-мя входами __m256 элементами. Если это можно сделать, просто сделайте min4 (A, B) -> P, min4 (C, D) -> Q, min4 (P, Q) -> возвращаемое значение.

Понятия не имею, как к тому, что для двух векторов, хотя :)

=============================== =================================================

Обновление 2: проблема почти решена - следующая функция вычисляет 4 минимальных значения.

__m256d min4(__m256d A, __m256d B, __m256d C, __m256d D) 
{ 
    __m256d T; 
    T = _mm256_min_pd(A, B); 
    B = _mm256_max_pd(A, B);    
    B = _mm256_permute_pd(B, 0x5); 
    A = _mm256_min_pd(T, B);    
    B = _mm256_max_pd(T, B);    
    B = _mm256_permute2f128_pd(B, B, 0x1); 
    T = _mm256_min_pd(A, B); 
    B = _mm256_max_pd(A, B); 
    B = _mm256_permute_pd(B, 0x5); 
    A = _mm256_min_pd(A, B); 

    T = _mm256_min_pd(C, D); 
    D = _mm256_max_pd(C, D);    
    D = _mm256_permute_pd(D, 0x5); 
    C = _mm256_min_pd(T, D);    
    D = _mm256_max_pd(T, D);    
    D = _mm256_permute2f128_pd(D, D, 0x1); 
    T = _mm256_min_pd(C, D); 
    D = _mm256_max_pd(C, D); 
    D = _mm256_permute_pd(D, 0x5); 
    C = _mm256_min_pd(C, D); 

    T = _mm256_min_pd(A, C); 
    C = _mm256_max_pd(A, C);    
    C = _mm256_permute_pd(C, 0x5); 
    A = _mm256_min_pd(T, C);    
    C = _mm256_max_pd(T, C);    
    C = _mm256_permute2f128_pd(C, C, 0x1); 
    T = _mm256_min_pd(A, C); 
    C = _mm256_max_pd(A, C); 
    C = _mm256_permute_pd(C, 0x5); 
    A = _mm256_min_pd(A, C); 

    return A; 
}; 

Осталось только отсортировать значения в порядке возрастания внутри А перед возвратом.

Answer 1

Это чисто «горизонтальная» операция и не очень подходит для 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 элементов.

Answer 2

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

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

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

---

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

---

Я нашел номер really nice paper on SIMD sorting networks, with specific discussion of AVX. Они подробно описывают требуемые перетасовки при использовании инструкций SIMD упакованный-мин/упакованный-макс для сортировки пары векторных регистров данных. Они даже используют внутренние функции, такие как _mm512_shuffle_epi32 в своих примерах. Они говорят, что их результаты применимы к AVX, хотя они используют регистры маски AVX-512 в своих примерах.

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

Кстати, я написал предыдущую answer with some not-very-great ideas о сортировке 64-битных структур на float члена, но это на самом деле не применимо здесь, так как я только устранение осложнений работе с полезной нагрузкой (что вы не имеете).

---

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

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

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

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

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

ссылки я нашел:

• Another paper on SSE sorting, с некоторым кодом, используя palignr объединить два два индивидуально упорядоченные векторы в отсортированной 8-элементной пару векторов. Не применимо непосредственно к 256b векторам удвоений.
• Another paper on SSE sorting, с результатами испытаний от процессоров Core2. Он использует неэффективные blend/blend/shuffle для перетасовки между двумя векторами из-за ограничений shufps. In-line shufpd имеет несколько иные ограничения. Эта статья, вероятно, стоит внимательно рассмотреть. У них есть алгоритмы, которые работают на реальных векторах SSE, с доступными операциями в случайном порядке.
• Xiaochen, Rocki, and Suda's paper linked already
• What looks like a chapter on sorting networks от the CLR algorithms textbook.
• Sorting network generator, с выбором алгоритмов. Не для SIMD
• https://en.wikipedia.org/wiki/Bitonic_sorter примерная диаграмма имеет сортировочную сеть с 16 входами. Битонные сорта используют шаблоны, которые могут SIMD в некоторой степени. Верхнюю часть конца сети можно опустить, поскольку мы заботимся только о порядке наименьшего значения 4.
• Fastest sort of fixed length 6 int array. Популярный вопрос со многими ответами.