@ Ответ Алекса Лопатина показывает, как использовать _udiv64 для получения не страшного скалярного кода (несмотря на глупую пропущенную оптимизацию MSVC, смещающуюся влево / вправо).
Для компиляторов, которые поддерживают встроенный asm GNU C (включая ICC)), вы можете использовать это вместо неэффективного встроенного синтаксиса MSVC asm, который имеет много накладных расходов для переноса одной инструкции.См. В чем разница между «asm», «__asm» и «__asm __»? для примера переноса 64-бит / 32-бит => 32-бит idiv.(Используйте его для div, просто изменив мнемонику и типы на unsigned.) GNU C не имеет встроенной функции для деления 64/32 или 128/64;он должен оптимизировать чистый C. Но, к сожалению, GCC / Clang / ICC пропустили оптимизации для этого случая, даже используя if(a<=b) __builtin_unreachable();, чтобы пообещать, что a>b.
Но это все еще скалярное деление с довольно плохим
Может быть, вы можете использовать графический процессор для вашей задачи DSP?Если у вас достаточно большой пакет работ (а остальная часть вашего алгоритма совместима с графическим процессором), то, вероятно, стоит потратить время на обмен данными с графическим процессором.
Если вы используете процессор,тогда все, что мы можем предложить, выиграет от распараллеливания по нескольким ядрам, так что сделайте это для большей пропускной способности.
x86 SIMD (SSE4 / AVX2 / AVX512 *) не имеет целочисленного деления SIMD ваппаратное обеспечение .Функции Intel SVML _mm_div_epu64 и _mm256_div_epu64 являются , а не встроенными для реальной инструкции, это медленные функции, которые могут быть распакованы в скалярные или вычислить мультипликативные инверсии.Или любой другой трюк, который они используют;возможно, 32-битные функции деления преобразуются в векторы SIMD double, особенно если доступен AVX512.(Intel по-прежнему называет их «встроенными», возможно, потому, что они похожи на встроенную функцию, которую она понимает и может выполнять постоянное распространение. Они, вероятно, настолько эффективны, насколько это возможно, но это «не очень», и им нужнодля обработки общего случая, а не только вашего особого случая с младшей половиной одного делителя, равной нулю, и частным соответствием в 32 битах.)
Если у вас один и тот же делитель для многих элементов см. https://libdivide.com/ для SIMD, чтобы вычислить мультипликативное обратное значение один раз и применить его повторно.(Вы должны адаптировать эту технику, чтобы выпекать при сдвиге дивиденда, фактически не делая этого, оставляя малую половину с нулем неявной.)
Если ваш делитель всегда меняется, и это не средний шагв более крупном SIMD-дружественном алгоритме скалярное деление может быть лучшим выбором, если вам нужны точные результаты.
Вы можете получить большие ускорения от использования SIMD float, если достаточно точности 24-битной мантиссы
uint32_t ScaledDiv(uint32_t a, uint32_t b)
{
return ((1ULL<<32) * (float)b) / a;
}
(float)(1ULL<<32) - это константа времени компиляции 4294967296.0f.
Это автоматически векторизирует массив с gcc и clang даже без -ffast-math (но не MSVC). Посмотри на Годболт .Вы можете перенести ассемблер gcc или clang обратно на встроенные функции для MSVC;они используют некоторые трюки FP для упакованного преобразования целых чисел без знака в / из числа с плавающей запятой без AVX512.Невекторная скалярная FP, вероятно, будет медленнее, чем обычное целое число в MSVC, а также будет менее точной.
Например, пропускная способность Skylake div r32 составляет 1 на 6 циклов.Но его пропускная способность AVX vdivps ymm составляет одну инструкцию (из 8 float с) на 5 циклов.Или для 128-битного SSE2 divps xmm имеет пропускную способность один на 3 цикла. Таким образом, вы получаете примерно 10-кратную пропускную способность от AVX на Skylake.(8 * 6/5 = 9,6) Старые микроархитектуры имеют гораздо более медленное деление SIMD FP, но также и несколько более медленное целочисленное деление.Как правило, это соотношение меньше, поскольку старые процессоры не имеют таких широких разделителей SIMD, поэтому 256-битный vdivps должен пропускать 128-битные половины по отдельности.Но все еще есть много выгоды, как лучше, чем в 4 раза на Haswell.И у Ryzen vdivps ymm пропускная способность 6c, но div 32 пропускная способность 14-30 циклов.Так что это еще большее ускорение, чем Skylake.
Если остальная часть вашей задачи DSP может извлечь выгоду из SIMD, общее ускорение должно быть очень хорошим.float операции имеют более высокую задержку, поэтому выполнение вне очереди должно работать усерднее, чтобы скрыть эту задержку и выполнить перекрытие независимых итераций цикла.Итак, IDK, было бы лучше, если бы вы просто конвертировали в float и обратно для этой одной операции, или изменили свой алгоритм для работы с float везде .Это зависит от того, что еще нужно сделать с вашими номерами.
Если ваши числа без знака действительно соответствуют знаковым 32-разрядным целым числам, вы можете использовать прямую аппаратную поддержку дляупакованный SIMD int32 -> преобразование с плавающей точкой .В противном случае вам понадобится AVX512F для упакованного uint32 -> float с одной инструкцией, но это можно эмулировать с некоторой потерей эффективности.Это то, что делает gcc / clang при автоматической векторизации с AVX2, и почему MSVC не автоматически векторизирует.
MSVC выполняет автоматическую векторизацию с int32_t вместо uint32_t (и gcc / clang может сделать более эффективный код), поэтому предпочитайте, чтобы старший бит ваших целочисленных входов и / или выходов не мог быть установлен.(т. е. интерпретация дополнения 2 их битовых комбинаций будет неотрицательной.)
Особенно с AVX, vdivps достаточно медленный, чтобы скрыть затраты на конвертацию из целого числа и обратно, если только нет другихполезная работа, которая вместо этого могла бы перекрываться.
Точность с плавающей точкой:
A float сохраняет числа как significand * 2^exp, где значение и находится в диапазоне [1.0, 2.0).(Или [0, 1.0) для субнормалей).Одинарная точность float имеет 24 бита значимости и точности, включая неявный бит 1.
https://en.wikipedia.org/wiki/Single-precision_floating-point_format
Таким образом, можно представить 24 наиболее значимые цифры целого числа,остальное потеряно из-за ошибки округления.Целое число типа (uint64_t)b << 32 не является проблемой для float;это просто означает больший показатель.Все младшие биты равны нулю.
Например, b = 123105810 дает нам 528735427897589760 для b64 << 32.Преобразование этого значения в float непосредственно из 64-разрядного целого числа дает нам 528735419307655168, ошибка округления 0,0000016% или около 2 ^ -25,8.Это неудивительно: максимальная ошибка округления составляет 0,5 целых (единицы на последнем месте), или 2 ^ -25, и это число было даже таким, что оно все равно имело 1 конечный ноль.Это та же относительная ошибка, которую мы получили бы при конвертации 123105810;результирующий float также тот же, за исключением его поля экспоненты (которое выше на 32).
(я использовал https://www.h -schmidt.net / FloatConverter / IEEE754.html чтобы проверить это.) Максимальный показатель
float достаточно велик, чтобы содержать целые числа вне диапазона от INT64_MIN до INT64_MAX.Младшие биты больших целых чисел, которые может представлять float, равны нулю, но это именно то, что вы имеете с b<<32.Таким образом, вы теряете младшие 9 бит b только в худшем случае, когда он является полным диапазоном и нечетным.
Если важной частью вашего результата являются наиболее значимые биты, иналичие младших ~ 9 целых битов = ошибка округления в порядке после преобразования обратно в целое число, тогда float идеально подходит для вас.
Если float не работает, double может бытьопция.
divpd примерно вдвое медленнее, чем divps на многих процессорах, и выполняет вдвое меньше работы (2 double элементов вместо 4 float).Таким образом, вы теряете пропускную способность в 4 раза таким образом.
Но каждое 32-разрядное целое число может быть представлено в точности как double. И, возвращая обратно с усечением к нулю, я думаювы получите точное целочисленное деление для всех пар входных данных, если только не является двойным округлением (сначала до ближайшего double, затем усечение) .Вы можете проверить это с
// exactly correct for most inputs at least, maybe all.
uint32_t quotient = ((1ULL<<32) * (double)b) / a;
Длинная постоянная без знака (1ULL<<32) преобразуется в double, поэтому у вас есть 2x u32 -> двойные преобразования (a и b), двойное умножение, двойное деление и двойное -> Конвертация у32.x86-64 может делать все это эффективно с помощью скалярных преобразований (с нулевым расширением uint32_t в int64_t или игнорированием старших битов преобразования double-> int64_t), но, вероятно, оно все равно будет медленнее, чем div r32.
Преобразование u32 -> double и обратно (без AVX512) может быть даже дороже, чем преобразование u32 -> float, но clang делает его векторизацию автоматически.(Просто измените float на double в ссылке на крестик выше).Опять же, это очень помогло бы, если бы все ваши входные данные были <= INT32_MAX, чтобы их можно было рассматривать как целые числа со знаком для преобразования FP.
Если двойное округление является проблемой, вы можете установить режим округления FP на усечение.вместо стандартного округления до ближайшего, если вы не используете FP для чего-либо еще в потоке, где выполняется ваш код DSP.