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

Основываясь на ответах на этот вопрос, я написал тест производительности с gcc 4.9.2 (MinGW64), чтобы оценить, какой способ множественного целочисленного деления выполняется быстрее:

#include  // SSE2 static unsigned short x[8] = {0, 55, 2, 62003, 786, 5555, 123, 32111}; // Dividend __attribute__((noinline)) static void test_div_x86(unsigned i){ for(; i; --i) x[0] /= i, x[1] /= i, x[2] /= i, x[3] /= i, x[4] /= i, x[5] /= i, x[6] /= i, x[7] /= i; } __attribute__((noinline)) static void test_div_sse(unsigned i){ for(; i; --i){ __m128i xmm0 = _mm_loadu_si128((const __m128i*)x); __m128 xmm1 = _mm_set1_ps(i); _mm_storeu_si128( (__m128i*)x, _mm_packs_epi32( _mm_cvtps_epi32( _mm_div_ps( _mm_cvtepi32_ps(_mm_unpacklo_epi16(xmm0, _mm_setzero_si128())), xmm1 ) ), _mm_cvtps_epi32( _mm_div_ps( _mm_cvtepi32_ps(_mm_unpackhi_epi16(xmm0, _mm_setzero_si128())), xmm1 ) ) ) ); } } int main(){ const unsigned runs = 40000000; // Choose a big number, so the compiler doesn't dare to unroll loops and optimize with constants test_div_x86(runs), test_div_sse(runs); return 0; } 

Результаты по параметрам GNU Gprof и инструментам.

 /* gcc -O? -msse2 -pg -o test.o -c test.c g++ -o test test.o -pg test gprof test.exe gmon.out ----------------------------------- test_div_sse(unsigned int) test_div_x86(unsigned int) -O0 2.26s 1.10s -O1 1.41s 1.07s -O2 0.95s 1.09s -O3 0.77s 1.07s */ 

Теперь я смущен, почему тест x86 едва ли оптимизирован, и SSE-тест становится быстрее, хотя дорогостоящее преобразование в & с плавающей запятой. Кроме того, я хотел бы знать, сколько результатов зависит от компиляторов и архитектур.

Подводя итог этому: что быстрее в конце: деление один на один или объезд с плавающей запятой?

Разделение всех элементов вектора на один и тот же скаляр можно сделать с помощью целочисленного умножения и сдвига. libdivide (C / C ++, zlib license) предоставляет некоторые встроенные функции для этого для скаляров (например, int ) и для деления векторов на скаляры. Также см. Целочисленное деление SSE? (как вы упомянули в своем вопросе) для подобной методики, дающей приблизительные результаты. Это более эффективно, если один и тот же скаляр будет применяться к множеству векторов. libdivide ничего не говорит о том, что результаты неточны, но я не исследовал.

re: ваш код: вы должны быть осторожны в проверке того, что на самом деле производит компилятор, когда он дает тривиальный цикл. например, действительно ли она загружается / сохраняется обратно в ОЗУ на каждой итерации? Или он поддерживает переменные в реестрах и хранит их только в конце?

Ваш бенчмарк искажен в пользу цепочки с целым делением, потому что векторный делитель не сохраняется на 100% в векторном цикле, но целочисленный делитель сохраняется на 100% в цикле int. (Эти абзацы были добавлены после обсуждения в комментариях. В предыдущем ответе не было объяснено так много о сохранении кормов с разделителями и цепочек зависимостей.)

У вас есть только одна цепочка зависимостей в векторном цикле, поэтому векторный разделитель сидит без дела в течение нескольких циклов на каждой итерации после получения второго результата, в то время как цепочка преобразования fp-> si, pack, unpack, convert si-> fp происходит. Вы установили все, чтобы ваша пропускная способность была ограничена длиной всей цепочки зависимостей, связанной с циклом, а не пропускной способностью разделителей FP. Если каждая итерация данных была независимой (или было по крайней мере несколько независимых значений, например, как у вас есть 8 элементов массива для цикла int), то распаковка / преобразование и преобразование / пакет одного набора значений будут перекрываться с выполнением divps время для другого вектора. Разделитель векторов только частично конвейерный, но все остальное, если он полностью конвейерный.

В этом разница между пропускной способностью и задержкой, и почему это имеет значение для конвейерного процессора вне очереди.

Другие вещи в вашем коде:

У вас есть __m128 xmm1 = _mm_set1_ps(i); во внутреннем цикле. _set1 с аргументом arg, который не является константой времени компиляции, обычно составляет как минимум 2 команды: movd и pshufd . И в этом случае также преобразование int-to-float. Было бы лучше сохранить векторный вариант вашего счетчика циклов, который вы увеличиваете путем добавления вектора 1.0 . (Хотя это, вероятно, еще не отбрасывает ваш тест скорости, потому что это избыточное вычисление может перекрываться с другими вещами.)

Распаковка с нуля работает отлично. SSE4.1 __m128i _mm_cvtepi16_epi32 (__m128i a) – это еще один способ. pmovsxwd имеет одинаковую скорость, но не нуждается в нулевом регистре.

Если вы собираетесь конвертировать в FP для разделения, считаете ли вы, что просто сохраняете свои данные как FP на некоторое время? Зависит от вашего алгоритма, как вам нужно округлить.

производительности на последних процессорах Intel

divps (упакованный одиночный поплавок) – это 10-13 циклов с пропускной способностью по одному на 7 циклов, по новейшим проектам Intel. div / idiv r16 ((беззнаковое) целочисленное деление в div / idiv r16 GP) составляет 23-26 циклов задержки, по одному на 9 или 8 циклов. div – 11 uops, поэтому он даже мешает другим вещам, выпускающим / выполняющим в течение некоторого времени, когда он проходит через конвейер. ( divps – это единственный uop.) Таким образом, процессоры Intel на самом деле не предназначены для быстрого разделения на целое, но прилагают усилия для разделения FP.

Таким образом, только для деления одно целое деление медленнее, чем векторное FP-деление. Вы собираетесь выйти вперед даже с преобразованием в / из float и распаковкой / пакетом.

Если вы можете сделать другие целые ops в векторных regs, это будет идеально. В противном случае вы должны получить целые числа в / из векторных regs. Если ints находятся в ОЗУ, векторная нагрузка прекрасна. Если вы генерируете их по одному, PINSRW – это опция, но вполне возможно, что простое сохранение в памяти для установки векторной загрузки было бы более быстрым способом загрузки полного вектора. Аналогично для получения данных, с PEXTRW или путем хранения в ОЗУ. Если вам нужны значения в регистрах GP, пропустите pack после преобразования обратно в int и просто MOVD / PEXTRD из того, что из двух векторных регистров находится в вашем значении. Инструкции для вставки / извлечения занимают два компьютера на Intel, что означает, что они занимают два «слота», по сравнению с большинством инструкций, в которых принимается только один объединенный домен.

Ваши результаты синхронизации, показывающие, что скалярный код не улучшается с оптимизацией компилятора, заключается в том, что ЦП может перекрывать подробные неоптимизированные инструкции загрузки / хранения для других элементов, в то время как блок разделения является узким местом. С другой стороны, векторный цикл имеет только одну или две цепи зависимостей, причем каждая итерация зависит от предыдущей, поэтому дополнительные инструкции, добавляющие латентность, не могут быть перекрыты ничем. Тестирование с помощью -O0 практически никогда не бывает полезным.