Деление с плавающей точкой против умножения с плавающей точкой
Есть ли (немирооптимизация) прирост производительности при кодировании?
float f1 = 200f / 2
по сравнению с
float f2 = 200f * 0.5
Мой профессор несколько лет назад сказал мне, что деления с плавающей запятой происходят медленнее, чем умножения с плавающей запятой, без объяснения причин.
Это утверждение верно для современной архитектуры ПК?
Update1
В отношении комментария, пожалуйста, также рассмотрите этот случай:
float f1;
float f2 = 2
float f3 = 3;
for( i =0 ; i < 1e8; i++)
{
f1 = (i * f2 + i / f3) * 0.5; //or divide by 2.0f, respectively
}
Обновление 2 Цитата из комментариев:
[Я хочу] знать, каковы алгоритмические / архитектурные требования, которые приводят к гораздо более сложному делению в аппаратном обеспечении, чем умножению
7 ответов
Да, многие процессоры могут выполнять умножение за 1 или 2 такта, но деление всегда занимает больше времени (хотя деление FP иногда быстрее, чем целочисленное деление).
Если вы посмотрите на этот ответ, вы увидите, что деление может превышать 24 цикла.
Почему деление занимает намного больше времени, чем умножение? Если вы помните, что еще в начальной школе, вы можете вспомнить, что умножение может быть выполнено с множеством одновременных дополнений. Деление требует итеративного вычитания, которое не может быть выполнено одновременно, поэтому это занимает больше времени. Фактически, некоторые единицы FP ускоряют деление, выполняя взаимное приближение и умножая на это. Это не так точно, но несколько быстрее.
Будьте очень осторожны с делением и избегайте его, когда это возможно. Например, гостиницы 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 до (a*a*a)*(a*a*a)?
Также обратите внимание, что компиляторы C++ могут сворачиваться+а также*в FMA в некоторых случаях (при компиляции для цели, которая его поддерживает, например, -march=haswell), но они не могут сделать это с /,
У деления задержка хуже, чем при умножении или сложении (или FMA) в 2–4 раза на современных процессорах x86, и худшая пропускная способность в 6–40 1 раз(для замкнутого цикла выполняетсятолько деление вместо только умножения).
Единица деления на квадратный метр не полностью конвейеризована, по причинам, объясненным в ответе @NathanWhitehead. Наихудшие отношения для векторов 256b, потому что (в отличие от других исполнительных блоков) делительная единица обычно не является полной шириной, поэтому широкие векторы должны быть сделаны в две половины. Не полностью конвейерный исполнительный модуль настолько необычен, что процессоры Intel имеют arith.divider_active счетчик производительности оборудования, который поможет вам найти код, который является узким местом в пропускной способности делителя вместо обычных узких мест внешнего порта или порта выполнения. (Или чаще, узкие места в памяти или длинные цепочки задержек, ограничивающие параллелизм на уровне команд, приводящий к тому, что пропускная способность команд составляет менее ~4 за такт).
Тем не менее, разделение FP и sqrt на процессорах Intel и AMD (кроме KNL) реализовано как единое целое, поэтому оно не обязательно оказывает большое влияние на пропускную способность окружающего кода. Наилучший случай для деления - это когда выполнение не по порядку может скрыть задержку, и когда есть много умножений и сложений (или другой работы), которые могут происходить параллельно с делением.
(Целочисленное деление микрокодируется в 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
Все, что вы делаете в цикле - это загрузка / деление / хранение, и они независимы, поэтому важна пропускная способность, а не задержка.
Сокращение как 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
х86 имеет примерно-обратную инструкцию (rcpps), который дает только 12 бит точности. (AVX512F имеет 14 бит, а AVX512ER имеет 28 бит.)
Вы можете использовать это, чтобы сделатьx / y = x * approx_recip(y)без использования фактической инструкции деления. (rcppsэто довольно быстро; обычно немного медленнее, чем умножение. Он использует поиск по таблице из внутренней таблицы ЦП. Аппаратные средства делителя могут использовать ту же таблицу в качестве отправной точки.)
Для большинства целейx * rcpps(y)слишком неточно, и требуется итерация Ньютона-Рафсона для удвоения точности. Но это стоит вам 2 умножения и 2 FMA, и имеет задержку, примерно равную реальной инструкции деления. Если все, что вы делаете, это деление, то это может быть выигрыш в пропускной способности. (Но вы должны избегать такого рода циклов в первую очередь, если можете, возможно, делая деление как часть другого цикла, который выполняет другую работу.)
Но если вы используете разделение как часть более сложной функции,rcppsсам по себе + дополнительный мул + FMA обычно делает быстрее делиться с divpsинструкция, кроме процессоров с очень низкимdivpsпропускная способность.
(Например, Knight's Landing, см. Ниже. KNL поддерживает AVX512ER, поэтому дляfloatвекторыVRCP28PSрезультат уже достаточно точен, чтобы просто умножать без итерации Ньютона-Рафсона.floatРазмер мантиссы составляет всего 24 бита.)
Конкретные цифры из таблиц Агнера Фога:
В отличие от любой другой операции ALU, задержка деления / пропускная способность зависит от данных на некоторых процессорах. Опять же, это потому, что это так медленно и не полностью конвейерно. Внеочередное планирование легче с фиксированными задержками, потому что оно предотвращает конфликты обратной записи (когда один и тот же порт выполнения пытается выдать 2 результата в одном цикле, например, от выполнения команды 3 цикла, а затем двух операций 1 цикла),
Как правило, самые быстрые случаи, когда делитель является "круглым" числом, таким как2.0или же0.5(то есть base2floatпредставление имеет много конечных нулей в мантиссе).
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 на Райзене и Скайлэйке с их увеличенными делителями, но 16-28 на Haswell (зависит от данных, и, скорее всего, ближе к концу цикла 28, если ваши делители не являются круглыми числами). Эти современные процессоры имеют очень мощные делители, но их удвоенная пропускная способность по двум тактам просто поражает. (Тем более, когда ваш код может автоматически векторизоваться с векторами AVX 256b). Также обратите внимание, что при правильных параметрах компилятора эти умноженные пропускные способности также применяются к FMA.
Номера из http://agner.org/optimize/ таблиц инструкций для Intel Haswell/Skylake и AMD Ryzen для скаляров SSE (не включая x87 fmul / fdiv) и для 256b векторов AVX SIMD float или же double, Смотрите также x86 tag wiki.
Деление по своей сути намного более медленная операция, чем умножение.
И на самом деле это может быть чем-то, что компилятор не может (и может не захотеть) оптимизировать во многих случаях из-за неточностей с плавающей запятой. Эти два утверждения:
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 битов во время сравнения. Каждый этап умножения не зависит от всех других этапов (не имеет значения, в каком порядке вы добавляете частичные продукты); для деления каждый шаг зависит от предыдущего шага. Это большое дело в оборудовании. Если что-то можно сделать независимо, тогда это может произойти в одно и то же время в течение часового цикла.
Ньютон Рапсон решает целочисленное деление в сложности O(M(n)) с помощью аппроксимации линейной алгебры. Быстрее чем иначе O(n*n) сложность.
В коде метод содержит 10 месяцев, 9 и 2 сдвига.
Это объясняет, почему деление примерно в 12 раз больше тактов процессора, чем умножения.
Ответ зависит от платформы, для которой вы программируете.
Например, выполнение большого умножения в массиве на x86 должно быть намного быстрее, чем деление, потому что компилятор должен создать код ассемблера, который использует инструкции SIMD. Поскольку в инструкциях SIMD нет деления, вы увидите большие улучшения, используя умножение и деление.