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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будьте очень осторожны с разделением и избегайте его, когда это возможно. Например, 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 , за исключением процессоров с очень низкой пропускной способностью.

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

---

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

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

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

задержка с 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’s Landing (Xeon Phi на основе Silvermont) имеют исключительно низкую производительность деления , и даже вектор 128b медленнее скалярного. Маломощный процессор AMD Jaguar (используемый в некоторых консолях) аналогичен. Высокопроизводительный делитель занимает много места. 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 . См. Также вики-tags x86 .

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

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

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

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

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