Деление с плавающей запятой против умножения с плавающей запятой

Ответ 1

Да, многие процессоры могут выполнять умножение в 1 или 2 тактовых циклах, но деление всегда занимает больше времени (хотя разделение FP иногда быстрее, чем целочисленное деление).

Если вы посмотрите на этот ответ, вы увидите, что разделение может превышать 24 цикла.

Почему деление занимает гораздо больше времени, чем умножение? Если вы помните назад в старшую школу, вы можете вспомнить, что умножение может быть выполнено с помощью многих одновременных дополнений. Отдел требует итеративного вычитания, которое невозможно выполнить одновременно, поэтому требуется больше времени. Фактически, некоторые единицы FP ускоряют деление, выполняя обратное приближение и умножая на это. Это не совсем точно, но несколько быстрее.

Ответ 2

Подразделение по своей сути намного медленнее, чем умножение.

И это может быть что-то, что компилятор не может (и вы не захотите) оптимизировать во многих случаях из-за неточностей с плавающей запятой. Эти два утверждения:

double d1 = 7 / 10.;
double d2 = 7 * 0.1;

не являются семантически идентичными - 0.1 не может быть точно представлен как double, поэтому в конечном итоге будет использовано немного другое значение - замена умножения для деления в этом случае даст другой результат!

Ответ 3

Да. Каждый FPU, о котором я знаю, выполняет умножения намного быстрее, чем деления.

Однако современные ПК очень быстрые. Они также содержат конвейерные артефакты, которые могут принести немаловажное значение при многих обстоятельствах. В довершение всего, любой достойный компилятор выполнит операцию деления, которую вы показали во время компиляции, при включенной оптимизации. Для вашего обновленного примера любой достойный компилятор выполнил бы это преобразование.

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

Ответ 4

Подумайте о том, что требуется для умножения двух n бит-чисел. С помощью простейшего метода вы берете одно число x и многократно меняете и условно добавляете его в накопитель (на основе бит в другом числе y). После n дополнений вы закончили. Ваш результат соответствует 2n бит.

Для деления вы начинаете с x из 2n бит и y из n бит, вы хотите вычислить x/y. Простейшим методом является длинное деление, но в двоичном. На каждом этапе вы выполняете сравнение и вычитание, чтобы получить еще один бит частного. Это потребует n шагов.

Некоторые отличия: каждый шаг умножения должен смотреть только на 1 бит; каждый этап деления должен смотреть на n бит во время сравнения. Каждый этап умножения не зависит от всех остальных этапов (неважно, в какой порядок вы добавляете частичные продукты); для деления каждый шаг зависит от предыдущего шага. Это большое дело в оборудовании. Если что-то можно сделать независимо, то они могут произойти одновременно с часовым циклом.

Ответ 5

Будьте очень осторожны с разделением и избегайте его, когда это возможно. Например, float inverse = 1.0f/divisor; из цикла и умножить на inverse внутри цикла. (Если допустима ошибка округления в inverse)

Обычно 1.0/x не будет точно представлен как float или double. Это будет точно, когда x является степенью 2. Это позволяет компиляторам оптимизировать x/2.0f до x * 0.5f без каких-либо изменений в результате.

Чтобы позволить компилятору сделать эту оптимизацию для вас, даже если результат не будет точным (или с делителем переменной времени выполнения), вам понадобятся такие параметры, как gcc -O3 -ffast-math. В частности, -freciprocal-math (включенная с помощью -funsafe-math-optimizations включенная -ffast-math) позволяет компилятору заменить x/y x * (1/y) когда это полезно. Другие компиляторы имеют аналогичные варианты, и ICC может включить некоторую "небезопасную" оптимизацию по умолчанию (я думаю, что да, но я забыл).

-ffast-math часто важна, чтобы разрешить авто-векторию циклов FP, особенно сокращений (например, суммирование массива в одну скалярную сумму), потому что математика FP не ассоциативна. Почему GCC не оптимизирует a * a * a * a * a * a to (a * a * a) * (a * a * a)?

Также обратите внимание, что компиляторы C++ могут сбрасывать + и * в FMA в некоторых случаях (при компиляции для целевой, поддерживающей его, например -march=haswell), но они не могут сделать это с помощью /.

У подразделения есть более низкая латентность, чем умножение или добавление (или FMA) в 2-4 раза на современных процессорах x86 и более низкая пропускная способность в 6 - 40 ^единиц (для жесткой циклы, выполняющей только деление, а не только умножение).

Модуль divide/sqrt не полностью конвейерный, по причинам, указанным в ответе @NathanWhitehead. Наихудшие коэффициенты относятся к векторам 256b, потому что (в отличие от других исполнительных блоков) единица разделения обычно не является полной, поэтому широкие векторы должны выполняться в двух половинах. arith.divider_active конвейерное исполнительное устройство настолько необычно, что процессоры Intel имеют arith.divider_active производительности arith.divider_active который поможет вам найти код, который является узким местом на пропускной способности делителя вместо обычных узких мест в arith.divider_active или arith.divider_active выполнения. (Или чаще, узкие места памяти или длинные системы ожидания, ограничивающие параллелизм на уровне инструкций, приводящие к сокращению пропускной способности команд менее чем за 4 часа).

Однако разделение FP и sqrt на процессорах Intel и AMD (кроме KNL) реализовано как единый uop, поэтому он не обязательно оказывает значительное влияние на окружающий код. Лучшим случаем для деления является то, что исполнение вне порядка может скрыть задержку, и когда есть много размножений и добавлений (или другой работы), которые могут произойти параллельно с разделом.

(Целочисленное подразделение микрокодировано как несколько процессоров на Intel, поэтому оно всегда оказывает большее влияние на окружающий код, который умножается на целое число. Там меньше спроса на высокопроизводительное целочисленное деление, поэтому аппаратная поддержка не такая фантастическая. Связанные: микрокодированные инструкции, такие как idiv может вызвать чувствительные к выравниванию интерфейсные узкие места.)

Так, например, это будет очень плохо:

for ()
    a[i] = b[i] / scale;  // division throughput bottleneck

// Instead, use this:
float inv = 1.0 / scale;
for ()
    a[i] = b[i] * inv;  // multiply (or store) throughput bottleneck

Все, что вы делаете в цикле, это load/divide/store, и они независимы, поэтому важна пропускная способность, а не латентность.

Сокращение, подобное accumulator/= b[i] было бы узким местом для деления или умножения латентности, а не пропускной способности. Но с несколькими аккумуляторами, которые вы делите или размножаетесь в конце, вы можете скрыть задержку и все еще насытить пропускную способность. Обратите внимание, что sum += a[i]/b[i] узкие места при add латентности или пропускной способности div, но не в задержке div потому что деление не находится на критическом пути (цепочка зависимостей, связанная с циклом).

Но в чем-то подобном (аппроксимируя такую функцию, как log(x) с отношением двух полиномов), деление может быть довольно дешевым:

for () {
    // (not shown: extracting the exponent / mantissa)
    float p = polynomial(b[i], 1.23, -4.56, ...);  // FMA chain for a polynomial
    float q = polynomial(b[i], 3.21, -6.54, ...);
    a[i] = p/q;
}

Для log() в диапазоне мантиссы отношение двух полиномов порядка N имеет гораздо меньшую ошибку, чем один многочлен с 2N-коэффициентами, а параллельная оценка 2 дает вам некоторый параллелизм на уровне инструкций внутри одного тела цикла, а не одна массовая длинная цепочка отрезков, что делает вещи намного проще для исполнения вне порядка.

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

Мы не являемся узким местом по пропускной способности деления, если наши полиномы достаточно велики, и у нас есть только один разрыв для каждых 10 инструкций FMA или около того. (И в реальном случае log() используется куча работы по извлечению экспоненты/мантиссы и повторному объединению вещей, поэтому между делениями еще больше работы.)

Когда вам нужно делить, обычно лучше всего разделить вместо rcpps

x86 имеет ориентировочно-обратную инструкцию ( rcpps), которая дает вам только 12 бит точности. (AVX512F имеет 14 бит, а AVX512ER имеет 28 бит).

Вы можете использовать это для выполнения x/y = x * approx_recip(y) без использования фактической инструкции деления. (rcpps itsef довольно быстро, обычно немного медленнее, чем умножение. Он использует поиск таблицы из внутренней таблицы в ЦП. Аппарат делителя может использовать ту же таблицу для начальной точки.)

Для большинства целей x * rcpps(y) слишком неточна, и требуется итерация Newton-Raphson для двойной точности. Но это стоит вам 2 умножения и 2 FMA, и имеет латентность примерно так же высоко, как фактическая инструкция деления. Если все, что вы делаете, это деление, то это может быть победа в пропускной способности. (Но вы должны избегать такой циклы в первую очередь, если можете, возможно, делая разделение как часть другого цикла, который выполняет другую работу.)

Но если вы используете разделение как часть более сложной функции, то rcpps себя + дополнительный MUL + FMA обычно делает это быстрее, чтобы просто разделить с divps инструкции, за исключением процессоров с очень низкой divps пропускной способности.

(Например, Knight Landing, см. Ниже KNL поддерживает AVX512ER, поэтому для float векторах VRCP28PS результат уже достаточно точным, чтобы просто умножить без итерации Ньютона-Рафсона. float мантисса размер составляет всего 24 бита.)

Конкретные номера из таблиц Agner Fog:

В отличие от любой другой операции ALU, латентность/пропускная способность подразделения зависят от данных от некоторых ЦП. Опять же, это потому, что он настолько медленный и не полностью конвейерный. Внеплановое планирование проще при фиксированных задержках, поскольку оно позволяет избежать конфликтов с обращением (когда один и тот же порт выполнения пытается произвести 2 результата в одном и том же цикле, например, от выполнения инструкции по 3 циклам, а затем двух операций с одним циклом),

Как правило, наиболее быстрыми случаями являются то, что делитель является "круглым" числом, например, 2.0 или 0.5 (т.е. В представлении float base2 имеется много конечных нулей в мантиссе).

задержка с float (циклы) /пропускная способность (циклы на инструкцию, выполняемые только с обратной стороны с независимыми входами):

                   scalar & 128b vector        256b AVX vector
                   divss      |  mulss
                   divps xmm  |  mulps           vdivps ymm | vmulps ymm

Nehalem          7-14 /  7-14 | 5 / 1           (No AVX)
Sandybridge     10-14 / 10-14 | 5 / 1        21-29 / 20-28 (3 uops) | 5 / 1
Haswell         10-13 / 7     | 5 / 0.5       18-21 /   14 (3 uops) | 5 / 0.5
Skylake            11 / 3     | 4 / 0.5          11 /    5 (1 uop)  | 4 / 0.5

Piledriver       9-24 / 5-10  | 5-6 / 0.5      9-24 / 9-20 (2 uops) | 5-6 / 1 (2 uops)
Ryzen              10 / 3     | 3 / 0.5         10  /    6 (2 uops) | 3 / 1 (2 uops)

 Low-power CPUs:
Jaguar(scalar)     14 / 14    | 2 / 1
Jaguar             19 / 19    | 2 / 1            38 /   38 (2 uops) | 2 / 2 (2 uops)

Silvermont(scalar)    19 / 17    | 4 / 1
Silvermont      39 / 39 (6 uops) | 5 / 2            (No AVX)

KNL(scalar)     27 / 17 (3 uops) | 6 / 0.5
KNL             32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

double латентность (циклы) /пропускная способность (циклы на инструкцию):

                   scalar & 128b vector        256b AVX vector
                   divsd      |  mulsd
                   divpd xmm  |  mulpd           vdivpd ymm | vmulpd ymm

Nehalem         7-22 /  7-22 | 5 / 1        (No AVX)
Sandybridge    10-22 / 10-22 | 5 / 1        21-45 / 20-44 (3 uops) | 5 / 1
Haswell        10-20 /  8-14 | 5 / 0.5      19-35 / 16-28 (3 uops) | 5 / 0.5
Skylake        13-14 /     4 | 4 / 0.5      13-14 /     8 (1 uop)  | 4 / 0.5

Piledriver      9-27 /  5-10 | 5-6 / 1       9-27 / 9-18 (2 uops)  | 5-6 / 1 (2 uops)
Ryzen           8-13 /  4-5  | 4 / 0.5       8-13 /  8-9 (2 uops)  | 4 / 1 (2 uops)

  Low power CPUs:
Jaguar            19 /   19  | 4 / 2            38 /  38 (2 uops)  | 4 / 2 (2 uops)

Silvermont(scalar) 34 / 32    | 5 / 2
Silvermont         69 / 69 (6 uops) | 5 / 2           (No AVX)

KNL(scalar)      42 / 42 (3 uops) | 6 / 0.5   (Yes, Agner really lists scalar as slower than packed, but fewer uops)
KNL              32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

Ивибридж и Бродвелл тоже разные, но я хотел держать стол маленьким. (Core2 (до Nehalem) имеет лучшую производительность делителя, но его максимальные тактовые частоты были ниже.)

Atom, Silvermont и даже Knight Landing (Xeon Phi на базе Silvermont) имеют исключительно низкую производительность деления, и даже вектор 128b медленнее скалярного. AMD с низким энергопотреблением Jaguar CPU (используется в некоторых консолях) аналогичен. Высокопроизводительный делитель занимает много места. Xeon Phi имеет низкую мощность в ядре, и упаковка большого количества ядер на матрице придает ей более жесткие ограничения на площадь, которые Skylake-AVX512. Кажется, что AVX512ER rcp28ps/pd - это то, что вы "предполагаете" использовать в KNL.

(См. Этот результат InstLatx64 для Skylake-AVX512, а также Skylake-X. Числа для vdivps zmm: 18c/10c, поэтому половина пропускной способности ymm.)

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

Сноска 1: как я составил эти отношения div и mul:

Разделение FP по сравнению с несколькими коэффициентами производительности еще хуже, чем у маломощных процессоров, таких как Silvermont и Jaguar, и даже в Xeon Phi (KNL, где вы должны использовать AVX512ER).

Фактические коэффициенты деления/умножения для скалярных (без векторизации) double: 8 на Ryzen и Skylake с их усиленными разделителями, но 16-28 на Haswell (зависящие от данных и более вероятные к концу 28 циклов, если ваши делители не являются круглые числа). Эти современные процессоры имеют очень мощные разделители, но их пропускная способность с удвоенной частотой в два раза сбрасывает его. (Тем более, когда ваш код может автоматически векторизовать с помощью векторов AVI 256b). Также обратите внимание, что при правильных параметрах компилятора эти многократные пропускные способности также применяются к FMA.

Номера из http://agner.org/optimize/ таблиц инструкций для Intel Haswell/Skylake и AMD Ryzen для сканера SSE (не включая x87 fmul/fdiv) и для 256-битных AVX SIMD-векторов float или double. См. Также вики x86.

Ответ 6

Newton rhapson решает целочисленное деление по сложности O (M (n)) с помощью аппроксимации линейной алгебры. Быстрее, чем сложность O (n * n).

В коде Метод содержит 10 миллионов 9adds 2bitwiseshifts.

Это объясняет, почему деление примерно в 12 раз больше циклов процессора как умножение.

Ответ 7

Ответ зависит от платформы, для которой вы программируете.

Например, выполнение большого количества умножений на массиве на x86 должно быть намного быстрее, чем выполнение разделения, потому что компилятор должен создать код ассемблера, который использует инструкции SIMD. Поскольку в инструкциях SIMD нет разделения, тогда вы увидите большие улучшения, используя умножение, затем разделение.