Самый быстрый способ вычисления абсолютного значения с использованием SSE

Мне известны 3 метода, но, насколько я знаю, обычно используются только первые 2:

  1. Маска от знака бит, используя andps или же andnotps,

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

  2. Вычтите значение от нуля до отрицания, а затем получите максимум оригинала и отрицайте.

    • Плюсы: фиксированная стоимость, потому что ничего не нужно для извлечения, как маска.
    • Минусы: всегда будет медленнее, чем метод маски, если условия идеальны, и мы должны ждать subps завершить перед использованием maxps инструкция.

  3. Подобно варианту 2, вычтите исходное значение от нуля до отрицания, но затем "поразрядно" и результат с исходным, используя andps, Я провел тест, сравнивая его со способом 2, и он, похоже, ведет себя идентично методу 2, за исключением случаев, когда NaNс, в этом случае результат будет другим NaN чем результат метода 2.

    • Плюсы: должно быть немного быстрее, чем метод 2, потому что andps обычно быстрее чем maxps,
    • Минусы: это может привести к непреднамеренному поведению, когда NaNучаствуют? Может быть нет, потому что NaN все еще NaN, даже если это другое значение NaN, право?

Мысли и мнения приветствуются.

Источник

1 ответ

TL;DR: почти во всех случаях используйте pcmpeq/shift для генерации маски и andps для ее использования. У него самый короткий критический путь (связанный с постоянной из памяти), и он не может пропустить кеш.

Как это сделать с помощью встроенных функций

Получение компилятора для излучения pcmpeqd в неинициализированном регистре может быть сложно. (Годболт). Лучший способ для GCC / ICC выглядит

__m128 abs_mask(void){
  // with clang, this turns into a 16B load,
  // with every calling function getting its own copy of the mask
  __m128i minus1 = _mm_set1_epi32(-1);
  return _mm_castsi128_ps(_mm_srli_epi32(minus1, 1));
}
// MSVC is BAD when inlining this into loops
__m128 vecabs_and(__m128 v) {
  return _mm_and_ps(abs_mask(), v);
}


__m128 sumabs(const __m128 *a) { // quick and dirty no alignment checks
  __m128 sum = vecabs_and(*a);
  for (int i=1 ; i < 10000 ; i++) {
      // gcc, clang, and icc hoist the mask setup out of the loop after inlining
      // MSVC doesn't!
      sum = _mm_add_ps(sum, vecabs_and(a[i])); // one accumulator makes addps latency the bottleneck, not throughput
  }
  return sum;
}

clang 3.5 и более поздние версии "оптимизируют" set1 / shift для загрузки константы из памяти. Будет использовать pcmpeqd реализовать set1_epi32(-1), хоть. TODO: найдите последовательность встроенных функций, которая производит желаемый машинный код с помощью clang. Загрузка константы из памяти не является причиной падения производительности, но использование каждой функции с использованием другой копии маски довольно ужасно.

MSVC: VS2013:

  • _mm_uninitialized_si128() не определено.

  • _mm_cmpeq_epi32(self,self) на неинициализированной переменной будет испускать movdqa xmm, [ebp-10h] в этом тестовом примере (то есть загрузить некоторые неинициализированные данные из стека. Это имеет меньший риск пропуска кеша, чем просто загрузка окончательной константы из памяти. Однако, Кумпутер говорит, что MSVC не удалось вывести pcmpeqd / psrld из цикла (Я предполагаю, что при встраивании vecabs), так что это непригодно, если вы сами не включите и не вытащите константу из цикла.

  • С помощью _mm_srli_epi32(_mm_set1_epi32(-1), 1) приводит к тому, что movdqa загружает вектор со всеми -1 (поднятый вне цикла), и psrld внутри петли. Так что это совершенно ужасно. Если вы собираетесь загрузить константу 16B, это должен быть последний вектор. Наличие целочисленных инструкций, генерирующих маску на каждой итерации цикла, также ужасно.

Рекомендации для MSVC: отказаться от создания маски на лету и просто написать

const __m128 absmask = _mm_castsi128_ps(_mm_set1_epi32(~(1<<31));

Возможно, вы просто сохраните маску в памяти как константу 16B. Надеюсь, не дублируется для каждой функции, которая его использует. Наличие маски в константе памяти, скорее всего, будет полезно в 32-битном коде, где у вас есть только 8 регистров XMM, поэтому vecabs может просто ANDPS с операндом источника памяти, если у него нет свободного регистра для сохранения постоянной константы.

TODO: узнайте, как избежать дублирования константы везде, где она указана. Вероятно, используя глобальную константу, а не анонимный set1, было бы хорошо. Но тогда вам нужно инициализировать его, но я не уверен, что встроенные функции работают в качестве инициализаторов для глобального __m128 переменные. Вы хотите, чтобы он входил в раздел данных только для чтения, чтобы не иметь конструктора, который запускается при запуске программы.

В качестве альтернативы используйте

__m128i minus1;  // undefined
#if _MSC_VER && !__INTEL_COMPILER
minus1 = _mm_setzero_si128();  // PXOR is cheaper than MSVC's silly load from the stack
#endif
minus1 = _mm_cmpeq_epi32(minus1, minus1);  // or use some other variable here, which will probably cost a mov insn without AVX, unless the variable is dead.
const __m128 absmask = _mm_castsi128_ps(_mm_srli_epi32(minus1, 1));

Дополнительный PXOR довольно дешевый, но он все еще на высоте и все равно 4 байта по размеру кода. Если у кого-то есть лучшее решение для преодоления нежелания MSVC испускать нужный нам код, оставьте комментарий или отредактируйте. Это не очень хорошо, если встроить в цикл, потому что pxor/pcmp/psrl все будет внутри цикла.

Загрузка 32-битной константы с movd и вещание с shufps может быть, все в порядке (опять же, вам, вероятно, придется вручную выводить это из цикла). Это 3 инструкции (mov-немедленно для GP reg, movd, shufps), и movd работает медленно на AMD, где векторная единица делится между двумя целочисленными ядрами. (Их версия гиперпоточности.)

Выбор лучшей последовательности asm

Хорошо, давайте посмотрим на это, скажем, Intel Sandybridge через Skylake, с небольшим упоминанием Nehalem. Посмотрите, как я справлялся с микроархитектами и инструкциями Агнера Фога. Я также использовал номера Skylake, на которые кто-то ссылался в сообщении на форумах http://realwordtech.com/.

Скажем, вектор, который мы хотимabs()вxmm0и является частью длинной цепочки зависимостей, что типично для кода FP.

Итак, давайте предположим, что любые операции, которые не зависят отxmm0может начать несколько циклов, прежде чемxmm0готов. Я протестировал, и инструкции с операндами памяти не добавляют дополнительную задержку в цепочку зависимостей, предполагая, что адрес операнда памяти не является частью цепочки dep (то есть не является частью критического пути).

Я не совсем понимаю, как рано может начаться операция с памятью, когда она является частью микроплавкого мопа. Насколько я понимаю, Re-Order Buffer (ROB) работает со слитными мопами и отслеживает мопы от выпуска до выхода на пенсию (от 168(SnB) до 224(SKL) записей). Есть также планировщик, который работает в незанятом домене, хранит только мопы, у которых готовые входные операнды еще не выполнены. Мопы могут выдавать в ROB (объединенный) и планировщик (не используется) одновременно, когда они декодируются (или загружаются из кэша UOP). Если я правильно понимаю, это от 54 до 64 записей в Sandybridge в Broadwell и 97 в Skylake. Есть некоторые необоснованные предположения о том, что он больше не является унифицированным (ALU/load-store) планировщиком.

Также говорят о том, что Скайлэйк обрабатывает 6 мопов за час. Насколько я понимаю, Skylake будет считывать целые строки UOP-кэша (до 6 UOP) за такт в буфер между кэшем UOP и ROB. Проблема в ROB/ планировщик по-прежнему в 4 раза. (Четноеnop по-прежнему 4 за часы). Этот буфер помогает, когда выравнивание кода / границы строк кэша uop вызывают узкие места для предыдущих разработок Sandybridge-microarch. Раньше я думал, что эта "очередь выдачи" была этим буфером, но, очевидно, это не так.

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

1а: маска с операндом памяти

ANDPS  xmm0, [mask]  # in the loop
  • байт: 7 insn, 16 данных. (AVX: 8 insn)
  • Число мопов в слитном домене: 1 * n
  • задержка добавлена ​​к критическому пути: 1с (при условии попадания в кэш L1)
  • пропускная способность: 1/ с. (Skylake: 2 / c) (ограничено 2 нагрузками / c)
  • "задержка", если xmm0 был готов, когда этот insn выдал: ~4c при попадании в кэш L1.

1b: маска из регистра

movaps   xmm5, [mask]   # outside the loop

ANDPS    xmm0, xmm5     # in a loop
# or PAND   xmm0, xmm5    # higher latency, but more throughput on Nehalem to Broadwell

# or with an inverted mask, if set1_epi32(0x80000000) is useful for something else in your loop:
VANDNPS   xmm0, xmm5, xmm0   # It's the dest that's NOTted, so non-AVX would need an extra movaps
  • байт: 10 insn + 16 данных. (AVX: 12 байт insn)
  • Число мопов в слитном домене: 1 + 1*n
  • задержка добавлена ​​в цепочку деп: 1с (с тем же предупреждением о пропадании кэша в начале цикла)
  • пропускная способность: 1/ с. (Скайлэйк: 3/ с)

PAND пропускная способность 3/c на Nehalem to Broadwell, но латентность =3c (если используется между двумя операциями домена FP, и еще хуже на Nehalem). Я предполагаю, что только порт 5 имеет проводку для прямой передачи побитовых операций непосредственно к другим исполнительным блокам FP (до Skylake). До Nehalem и в AMD побитовые операции FP обрабатываются идентично целым операциям FP, поэтому они могут работать на всех портах, но с задержкой пересылки.

1c: создать маску на лету:

# outside a loop
PCMPEQD  xmm5, xmm5  # set to 0xff...  Recognized as independent of the old value of xmm5, but still takes an execution port (p1/p5).
PSRLD    xmm5, 1     # 0x7fff...  # port0
# or PSLLD xmm5, 31  # 0x8000...  to set up for ANDNPS

ANDPS    xmm0, xmm5  # in the loop.  # port5
  • байт: 12 (AVX: 13)
  • Число мопов в слитном домене: 2 + 1*n (нет операций памяти)
  • задержка, добавленная в цепочку деп: 1с
  • пропускная способность: 1/ с. (Скайлэйк: 3/ с)
  • пропускная способность для всех 3 мопов: 1/c насыщает все 3 векторных порта ALU
  • "задержка", если xmm0 был готов, когда эта последовательность выдана (без цикла): 3c (+1c возможная задержка обхода на SnB/IvB, если ANDPS должен ждать готовности целочисленных данных. Agner Fog говорит, что в некоторых случаях нет дополнительной задержки для целого числа ->FP- логическое значение на SnB/IvB.)

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

"Задержка обхода" не должна быть проблемой. Если xmm0 является частью длинной цепочки зависимостей, инструкции по генерации маски будут выполняться задолго до времени, поэтому целочисленный результат в xmm5 успеет достичь ANDPS до того, как xmm0 будет готов, даже если он займет медленную полосу.

У Haswell нет задержки обхода для целочисленных результатов -> булево значение FP, согласно тестированию Agner Fog. Его описание для SnB/IvB говорит, что это имеет место с выводами некоторых целочисленных инструкций. Таким образом, даже в случае "начала с нуля", где начинается цепочка, где xmm0 готово, когда эта последовательность команд выдает, только 3c на * хорошо, 4c на *Bridge. Задержка, вероятно, не имеет значения, если исполнительные блоки очищают отставание от мопов так же быстро, как они выпускаются.

В любом случае выход ANDPS будет находиться в домене FP и не будет иметь задержки обхода, если используется в MULPS или что-то.

На Nehalem задержки обхода составляют 2с. Таким образом, в начале цепочки деп (например, после неверного прогнозирования ветки или пропуска I$) на Nehalem, "задержка", если xmm0 был готов, когда эта последовательность выдана 5с. Если вы беспокоитесь о Nehalem и ожидаете, что этот код будет первым, что запускается после частых неправильных прогнозов ветвлений или аналогичных остановок конвейера, из-за которых механизм OoOE не может начать вычисление маски до xmm0 готов, тогда это может быть не лучшим выбором для нецикличных ситуаций.

2a: AVX max (x, 0-x)

VXORPS  xmm5, xmm5, xmm5   # outside the loop

VSUBPS  xmm1, xmm5, xmm0   # inside the loop
VMAXPS  xmm0, xmm0, xmm1
  • байт: AVX: 12
  • Число мопов в слитном домене: 1 + 2*n (нет операций памяти)
  • задержка добавлена ​​в цепочку деп: 6c (Skylake: 8c)
  • пропускная способность: 1 на 2с (два порта1 мопс). (Скайлэйк: 1/ с, при условии MAXPS использует те же два порта, что и SUBPS.)

Skylake отбрасывает отдельную единицу добавления вектора-FP и добавляет вектор в единицах FMA на портах 0 и 1. Это удваивает пропускную способность добавления FP, за счет увеличения задержки на 1с. Задержка FMA уменьшена до 4 (с 5 в * лунке). x87 FADD по-прежнему 3-тактная задержка, так что есть еще 3-тактный скалярный сумматор 80 бит-FP, но только на одном порту.

2b: то же самое, но без AVX:

# inside the loop
XORPS  xmm1, xmm1   # not on the critical path, and doesn't even take an execution unit on SnB and later
SUBPS  xmm1, xmm0
MAXPS  xmm0, xmm1
  • байт: 9
  • Число мопов в слитном домене: 3*n (нет операций памяти)
  • задержка добавлена ​​в цепочку деп: 6c (Skylake: 8c)
  • пропускная способность: 1 на 2с (два порта1 мопс). (Скайлэйк: 1/ с)
  • "задержка", если xmm0 был готов, когда эта последовательность выдана (без цикла): то же самое

Обнуление регистра с помощью языка обнуления, который распознает процессор (например, xorps same,same) обрабатывается во время переименования регистров на микроархитектурах семейства Sandbridge и имеет нулевую задержку и пропускную способность 4/c. (То же, что и reg->reg, которые IvyBridge и позже могут устранить.)

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

3: ANDPS (х, 0-х)

VXORPS  xmm5, xmm5, xmm5   # outside the loop.  Without AVX: zero xmm1 inside the loop

VSUBPS  xmm1, xmm5, xmm0   # inside the loop
VANDPS  xmm0, xmm0, xmm1
  • байт: AVX: 12, не AVX: 9
  • Число операций в домене слияния: 1 + 2*n (нет операций памяти). (Без AVX: 3*n)
  • задержка, добавленная к цепочке депо: 4c (Skylake: 5c)
  • пропускная способность: 1/ с (насыщать р1 и р5). Skylake: 3/2c: (3 векторных мопа / цикл) / (uop_p01 + uop_p015).
  • "задержка", если xmm0 был готов, когда эта последовательность выдана (без цикла): то же самое

Это должно работать, но IDK либо то, что происходит с NaN. Замечательно, что ANDPS имеет меньшую задержку и не требует добавления порта FPU.

Это самый маленький размер с не AVX.

4: сдвиг влево / вправо:

PSLLD  xmm0, 1
PSRLD  xmm0, 1
  • байт: 10 (AVX: 10)
  • uops в слитых доменах: 2*n
  • задержка добавлена ​​в цепочку деп: 4с (2с + обходные задержки)
  • пропускная способность: 1/2c (насыщенная p0, также используется FP mul). (Skylake 1/c: удвоенная пропускная способность векторного сдвига)

  • "задержка", если xmm0 был готов, когда эта последовательность выдана (без цикла): то же самое

    Это самый маленький (в байтах) с AVX.

    У этого есть возможности, где вы не можете сэкономить регистр, и он не используется в цикле. (В цикле без регистров, чтобы сэкономить, пробное использование andps xmm0, [mask]).

Я предполагаю, что есть задержка обхода 1c от FP до целочисленного сдвига, а затем еще один 1c на обратном пути, так что это так же медленно, как SUBPS/ANDPS. Он действительно сохраняет uop без порта выполнения, поэтому он имеет преимущества, если пропускная способность uop в домене fused является проблемой, и вы не можете вытащить генерацию маски из цикла. (Например, потому что это в функции, которая вызывается в цикле, а не в строке).

Когда что использовать: Загрузка маски из памяти делает код простым, но может привести к потере кэша. И занимает 16B ro-данных вместо 9 байтов инструкции.

  • Необходим в цикле: 1c: генерировать маску вне цикла (с pcmp/shift); использовать один andps внутри. Если вы не можете сэкономить регистр, вылейте его в стек и 1a: andps xmm0, [rsp + mask_local], (Генерирование и хранение менее вероятно приведет к пропаданию кэша, чем к константе). Только добавляет 1 цикл к критическому пути в любом случае, с 1 инструкцией с одним мопом внутри цикла. Это порт 5, так что если ваш цикл насыщает порт случайного воспроизведения и не связан с задержкой, PAND может быть лучше. (У SnB/IvB есть единицы тасования на p1/p5, но Haswell/Broadwell/Skylake может тасовать только на p5. Skylake действительно увеличил пропускную способность для (V)(P)BLENDV, но не другие операции в случайном порядке. Если числа AIDA верны, то значение, отличное от AVX BLENDV, составляет 1c lat ~3/c tput, но AVX BLENDV составляет 2c lat, 1/c tput (все еще улучшение tput по сравнению с Haswell))

  • Необходим один раз в часто называемой непериодической функции (так что вы не можете амортизировать создание маски при многократном использовании):

    1. Если пропускная способность UOP является проблемой: 1a: andps xmm0, [mask], Случайная ошибка кэша должна амортизироваться из-за экономии в мопах, если это действительно было узким местом.
    2. Если задержка не является проблемой (функция используется только как часть коротких цепочек dep, не переносимых в цикле, например arr[i] = abs(2.0 + arr[i]);), и вы хотите избежать постоянной в памяти: 4, потому что это только 2 моп. Если abs приходит в начале или в конце цепочки депов, не будет задержки обхода от загрузки или до магазина.
    3. Если пропускная способность UOP не является проблемой: 1c: генерировать на лету с целым числом pcmpeq / shift, Отсутствует потеря кеша, и только добавляет 1с к критическому пути.

  • Необходим (вне каких-либо циклов) в редко вызываемой функции: просто оптимизируйте по размеру (ни одна маленькая версия не использует константу из памяти). не AVX: 3. AVX: 4. Они не плохие и не могут промахнуться. Задержка в 4 цикла для критического пути хуже, чем в версии 1c, поэтому, если вы не думаете, что 3 байта инструкции - это большое дело, выберите 1c. Версия 4 интересна для ситуаций с регистрацией давления, когда производительность не важна, и вы хотели бы избежать чего-либо.

  • Процессоры AMD: есть задержка обхода ANDPS (что само по себе имеет задержку 2с), но я думаю, что это все еще лучший выбор. Это все еще бьет 5-6 задержек цикла SUBPS, MAXPS задержка 2с С высокими задержками операций FP на процессорах семейства Bulldozer вы даже более склонны к выполнению не по порядку, чтобы иметь возможность генерировать вашу маску на лету, чтобы она была готова, когда другой операнд ANDPS является. Я предполагаю, что Bulldozer через Steamroller не имеет отдельного модуля добавления FP, а вместо этого делает векторное добавление и умножение в модуле FMA. 3 всегда будет плохим выбором для процессоров семейства AMD Bulldozer. 2 выглядит лучше в этом случае из-за более короткой задержки обхода от домена fma к домену fp и обратно. См. Руководство по микроархам Agner Fog, стр.182. (15.11. Задержка данных между различными доменами выполнения).

  • Сильвермонт: Схожие задержки с SnB. Еще иди с 1с для петель и проб. также для одноразового использования. Сильвермонт вышел из строя, поэтому он может заранее подготовить маску, добавив всего 1 цикл к критическому пути.

Источник
Другие вопросы по тегам