Горизонтальный минимум и максимум с использованием SSE

У меня есть функция, использующая SSE, чтобы делать много вещей, и профилировщик показывает мне, что часть кода, которую я использую для вычисления горизонтального минимума и максимума, занимает большую часть времени.

Например, я использовал следующую реализацию для минимума:

static inline int16_t hMin(__m128i buffer) {
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m1));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m2));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m3));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi8(buffer, m4));
    return ((int8_t*) ((void *) &buffer))[0];
}

Как видите, мне нужно вычислить минимум и максимум 16 1-байтовых целых чисел.

Любые хорошие предложения высоко ценятся :)

Спасибо


c++ max avx minimum sse
person user46317    schedule 07.03.2014    source источник
comment
Каковы значения масок m1, m2, m3, and m4?   -  person Z boson    schedule 07.03.2014
comment
Я не знаю, есть ли лучший способ. Без горизонтального оператора max min вы должны сделать это в четыре двоичных шага (что, я думаю, вы делаете): сравните 8 с 8, затем 4 с 4, затем 2 с 2 и затем 1 с 1. С int4 это занимает два шага : stackoverflow.com/questions/9877700/   -  person Z boson    schedule 07.03.2014
comment
Да, извините, я забыл перетасовать контрольные маски. Они используются в качестве Z-бозона, предполагаемого ранее.   -  person user46317    schedule 08.03.2014
comment
Как указано в ответе Марата Духана в качестве основной причины, использование адреса вектора SIMD не является правильным способом извлечения значений элементов в регистр ЦП, поскольку этот стиль заставит значение быть записанным в память. (Ни один из них не обращается к значению структуры напрямую.) Лучше всего будет изменить код на _mm_cvtsi128_si32.   -  person rwong    schedule 08.03.2014
comment
Вероятно, стоит упомянуть, что если ваш вызывающий код имеет (намного) более 16 1-байтовых целых чисел для нахождения общего минимума, вы можете сделать это намного быстрее, просто аккумулируя результаты одной операции _mm_min_epi8 в значение __m128i и выполняя шаг в вашей функции объединения результатов один раз в конце.   -  person Apriori    schedule 13.03.2014
comment
@Apriori Отличное предложение! Обязательно попробую позже   -  person user46317    schedule 13.03.2014
comment
@Apriori Я был слишком оптимистичен, векторы, которые я использую (и в других частых случаях использования), являются результатом операции сканирования побайтового подсчета населения или аналогичной операции, т.е. если длина превышает 16 байт, вы не будете возможность хранить сумму в крайних случаях. В тех случаях, когда это можно сделать без шага суммы префиксов, это наверняка будет огромным улучшением.   -  person user46317    schedule 13.03.2014
comment
Рад слышать, что это хоть частично помогает. Спасибо за описание, я думаю, что мне нужно немного больше информации, чтобы полностью понять проблему. Я думаю, вы имеете в виду, что целочисленный ролловер будет происходить в векторных компонентах в некоторых случаях. Имейте в виду, что вы можете притворяться, что отрицательные битовые комбинации положительны для некоторых операций. Говоря в целом, вы, возможно, могли бы где-то ограничить некоторые входные данные, чтобы избежать всего этого случая. Или вы могли бы, возможно, распаковать в 16-битные значения и выполнить свои вычисления на этом. Это все еще должно быть победой, если это позволяет вам объединить один раз в конце.   -  person Apriori    schedule 13.03.2014

Ответы (2)


arrow_upward
8
arrow_downward

Предлагаю два изменения:

  • Замените ((int8_t*) ((void *) &buffer))[0] на _mm_cvtsi128_si32.

  • Замените _mm_shuffle_epi8 на _mm_shuffle_epi32/_mm_shufflelo_epi16, которые имеют меньшую задержку на последних процессорах AMD и Intel Atom и сэкономят вам операции загрузки памяти:

    static inline int16_t hMin(__m128i buffer)
{
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi32(buffer, _MM_SHUFFLE(3, 2, 3, 2)));
    buffer = _mm_min_epi8(buffer, _mm_shuffle_epi32(buffer, _MM_SHUFFLE(1, 1, 1, 1)));
    buffer = _mm_min_epi8(buffer, _mm_shufflelo_epi16(buffer, _MM_SHUFFLE(1, 1, 1, 1)));
    buffer = _mm_min_epi8(buffer, _mm_srli_epi16(buffer, 8));
    return (int8_t)_mm_cvtsi128_si32(buffer);
}
person Marat Dukhan    schedule 07.03.2014
comment
Я протестировал этот метод сегодня, он работает в большинстве случаев, но не может найти минимум, когда он находится в первой позиции, например. если вы проверите его с вектором (0,1,..,15), он вернет, что минимум равен 1. Во всех других случаях это работает! - person user46317; 09.03.2014
comment
@ user46317 Вы правы, была ошибка. Теперь это исправлено. - person Marat Dukhan; 09.03.2014

arrow_upward
13
arrow_downward

В SSE 4.1 есть инструкция, которая делает почти то, что вы хотите. Его имя — PHMINPOSUW, встроенное в C/C++ — _mm_minpos_epu16. Он ограничен 16-битными беззнаковыми значениями и не может дать максимум, но эти проблемы можно легко решить.

  1. Если вам нужно найти минимум неотрицательных байтов, ничего не делайте. Если байты могут быть отрицательными, добавьте 128 к каждому. Если вам нужно максимум, вычтите каждое из 127.
  2. Используйте либо _mm_srli_pi16, либо _mm_shuffle_epi8, а затем _mm_min_epu8, чтобы получить 8 попарных минимальных значений в четных байтах и ​​нулей в нечетных байтах некоторого регистра XMM. (Эти нули создаются инструкцией сдвига/тасовки и должны оставаться на своих местах после _mm_min_epu8).
  3. Используйте _mm_minpos_epu16, чтобы найти минимум среди этих значений.
  4. Извлеките полученное минимальное значение с помощью _mm_cvtsi128_si32.
  5. Отмените действие шага 1, чтобы получить исходное значение байта.

Вот пример, который возвращает максимум 16 байтов со знаком:

static inline int16_t hMax(__m128i buffer)
{
    __m128i tmp1 = _mm_sub_epi8(_mm_set1_epi8(127), buffer);
    __m128i tmp2 = _mm_min_epu8(tmp1, _mm_srli_epi16(tmp1, 8));
    __m128i tmp3 = _mm_minpos_epu16(tmp2);
    return (int8_t)(127 - _mm_cvtsi128_si32(tmp3));
}
person Evgeny Kluev    schedule 08.03.2014
comment
Я также попробовал ваш метод в своих тестах, он действительно немного быстрее, чем другие методы. - person user46317; 09.03.2014
comment
Отлично, мне нравится, как _mm_min_epu8 оставляет нули в старшей половине каждого 16-битного элемента, поскольку unsigned_min(0,x) = 0. Таким образом, не требуется никаких инструкций, затрачиваемых только на расширение нулями до 16-битных. - person Peter Cordes; 22.12.2016
comment
Обратите внимание, что вычитание 128 — это то же самое, что сложение или операция XOR с 128 (поскольку переносу некуда деваться). pxor работает на большем количестве портов, чем psubb (и является коммутативным, что дает оптимизатору больше гибкости при распределении регистров), поэтому вам следует предпочесть это при смещении диапазона к беззнаковому. - person Peter Cordes; 22.12.2016