Как найти горизонтальный максимум в 256-битном векторе AVX

У меня есть вектор __m256d, содержащий четыре 64-битных значения с плавающей запятой.
Мне нужно найти горизонтальный максимум элементов вектора и сохранить результат в скалярном значении с двойной точностью;

Все мои попытки закончились использованием большого количества перетасовок векторных элементов, что сделало код не очень элегантным и эффективным. Также я обнаружил, что невозможно оставаться только в домене AVX. В какой-то момент мне пришлось использовать 128-битные инструкции SSE для извлечения окончательного 64-битного значения. Тем не менее, я хотел бы, чтобы последнее утверждение было ошибочным.

Итак, идеальное решение будет:
1) использовать только инструкции AVX.
2) минимизировать количество инструкций. (Надеюсь не более 3-4 инструкций)

При этом будет принято любое элегантное / эффективное решение, даже если оно не соответствует приведенным выше рекомендациям.

Спасибо за любую помощь.

-Луиджи


x86 simd avx avx2 vector-processing
person Luigi Castelli    schedule 20.03.2012    source источник
comment
Это сложный вопрос ... Вы делаете это только с одним вектором? Или у вас есть много векторов, для которых нужно найти максимум? Вы можете (довольно) эффективно выполнить 4 из них параллельно с транспонированием вектора 4 x 4 ...   -  person Mysticial    schedule 21.03.2012
comment
@Mysticial: Ну ... я имею дело со многими векторами. Однако простота обработки не оправдывает двух операций транспонирования 4x4 для каждой итерации. Итак, я обрабатываю все по горизонтали без транспонирования. Таким образом, я получаю большое ускорение, почти в 4 раза, потому что я избегаю накладных расходов на транспонирование. Все в тугой петле раскатывается вручную 4 раза. Однако, когда цикл заканчивается, у меня остается последний вектор AVX. Мне нужно найти наибольший из четырех его элементов, чтобы сохранить результат в моем скалярном значении двойной точности. Отсюда мой вопрос ...   -  person Luigi Castelli    schedule 21.03.2012
comment
Если это не в замкнутом цикле, критично ли это даже для производительности?   -  person Mysticial    schedule 21.03.2012
comment
На этот раз не совсем ... :) но я знаю, что столкнусь с ситуацией, когда производительность будет критичной. Поэтому я так и сформулировал вопрос ...   -  person Luigi Castelli    schedule 21.03.2012
comment
Ах :) В этом случае лучший способ сделать это, вероятно, будет сильно зависеть от того, как он используется. Другими словами, его нельзя векторизовать на этом уровне, но можете ли вы переместить его на более высокий уровень ...   -  person Mysticial    schedule 21.03.2012
comment
Что вы имеете в виду, поднимая его на более высокий уровень?   -  person Luigi Castelli    schedule 21.03.2012
comment
позвольте нам продолжить это обсуждение в чате   -  person Luigi Castelli    schedule 21.03.2012
comment
Обратите внимание, что вы можете оставаться в домене AVX, используя 128-битные инструкции. На самом деле существует 3 вида инструкций: AVX256, AVX128 и устаревший SSE128. Следует избегать переключения между первыми двумя и последними, это дорого для Intel (не для AMD), но первые два можно смешивать почти свободно (иногда вам, возможно, придется вставить vzeroupper)   -  person Gunther Piez    schedule 21.03.2012

Ответы (3)


arrow_upward
20
arrow_downward

Я не думаю, что вы можете сделать что-то лучше, чем 4 инструкции: 2 перетасовки и 2 сравнения.

__m256d x = ...; // input

__m128d y = _mm256_extractf128_pd(x, 1); // extract x[2], and x[3]
__m128d m1 = _mm_max_pd(x, y); // m1[0] = max(x[0], x[2]), m1[1] = max(x[1], x[3])
__m128d m2 = _mm_permute_pd(m1, 1); // set m2[0] = m1[1], m2[1] = m1[0]
__m128d m = _mm_max_pd(m1, m2); // both m[0] and m[1] contain the horizontal max(x[0], x[1], x[2], x[3])

Тривиальная модификация для работы только с 256-битными векторами:

__m256d x = ...; // input

__m256d y = _mm256_permute2f128_pd(x, x, 1); // permute 128-bit values
__m256d m1 = _mm256_max_pd(x, y); // m1[0] = max(x[0], x[2]), m1[1] = max(x[1], x[3]), etc.
__m256d m2 = _mm256_permute_pd(m1, 5); // set m2[0] = m1[1], m2[1] = m1[0], etc.
__m256d m = _mm256_max_pd(m1, m2); // all m[0] ... m[3] contain the horizontal max(x[0], x[1], x[2], x[3])

(непроверено)

person Norbert P.    schedule 21.03.2012
comment
Да, согласен ... Хорошее решение. Спасибо. - person Luigi Castelli; 21.03.2012
comment
Версия all-256 хороша на процессорах Intel, если вам нужно транслировать результат, но на Ryzen она намного медленнее. См. Получение суммы значений, хранящихся в __m256d, с помощью SSE / AVX. (И, кстати, _mm_unpackhi_pd на 2 байта короче, чем _mm_permute_pd, поэтому используйте это, если вам нужен только скалярный результат. Сразу не требуется, и можно использовать 2-байтовый префикс VEX.) - person Peter Cordes; 05.05.2018

arrow_upward
12
arrow_downward

Общий способ сделать это для вектора v1 = [A, B, C, D]:

  1. Переставить v1 на v2 = [C, D, A, B] (поменять местами 0-й и 2-й элементы, а также 1-й и 3-й)
  2. Возьми максимум; т.е. v3 = max(v1,v2). Теперь у вас есть [max(A,C), max(B,D), max(A,C), max(B,D)]
  3. Переставьте v3 на v4, поменяв местами 0-й и 1-й элементы, а также 2-й и 3-й.
  4. Снова возьмем максимум, т.е. v5 = max(v3,v4). Теперь v5 содержит горизонтальный максимум во всех своих компонентах.

В частности, для AVX перестановки могут быть выполнены с помощью _mm256_permute_pd, а максимальные значения могут быть выполнены с помощью _mm256_max_pd. У меня нет под рукой точных пермутирующих масок, но их довольно легко понять.

Надеюсь, это поможет.

person celion    schedule 21.03.2012
comment
Мне особенно нравится ваше решение, потому что пока оно единственное, которое использует исключительно инструкции AVX, не покидая 256-битного домена. Спасибо. - person Luigi Castelli; 21.03.2012
comment
извините, я заговорил слишком рано ... Вы не можете этого сделать с AVX. Большинство операций AVX не пересекают 128-битную границу. Таким образом, в этом случае вы не можете поменять местами 0-й и 2-й элементы, а также 1-й и 3-й. Операция перестановки AVX позволяет вам менять местами только 0-й и 1-й элементы или 2-й и 3-й элементы. - person Luigi Castelli; 21.03.2012
comment
@LuigiCastelli: мое решение можно написать так, чтобы никогда не покидать 256-битный домен, если хотите. Заменить _mm256_extractf128_pd на _mm256_permute2f128_pd(x, x, 1), __m128d на __m256d и _mm_... на _mm256_..., _mm_permute_pd(m1, 1) на _mm256_permute_pd(m1, 5). - person Norbert P.; 21.03.2012

arrow_upward

arrow_downward

person    schedule
comment
Для векторов с плавающей запятой потребуется один дополнительный шаг, но сохранение в массиве и выполнение скалярного сравнения не являются одним из шагов. Вы по-прежнему хотите начать с extractf128 / 128-битного maxps. Выполнение внутренних задач в первую очередь ничуть не лучше на процессорах Intel, и определенно хуже на процессорах AMD, где операции AVX 256b в два раза дороже, чем операции AVX 128b. В любом случае, хранилище 256 байт, а затем две загрузки - ›скалярное сравнение просто глупо и медленнее, чем extractf128. - person Peter Cordes; 21.01.2016