Будьте очень осторожны с делением и избегайте его, когда это возможно. Например, выведите 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. (для узкого цикла, делающего только деление вместо только умножение).
Единица деления / sqrt не полностью конвейеризована, по причинам, объясненным в @ NathanWhitehead's answer . Наихудшие отношения для векторов 256b, потому что (в отличие от других исполнительных блоков) делительная единица обычно не является полной шириной, поэтому широкие векторы должны быть выполнены в две половины. Не полностью конвейеризованный исполнительный модуль настолько необычен, что процессоры Intel имеют аппаратный счетчик производительности arith.divider_active, чтобы помочь вам найти код, который ограничивает пропускную способность делителя вместо обычных узких мест внешнего порта или порта выполнения. (Или чаще узкие места в памяти или длинные цепочки задержек, ограничивающие параллелизм на уровне команд, приводят к тому, что пропускная способность команд составляет менее ~ 4 за такт).
Однако деление FP и sqrt на процессорах Intel и AMD (кроме KNL) реализовано как один моп, поэтому оно не обязательно оказывает большое влияние на пропускную способность окружающего кода . Наилучший случай для деления - когда выполнение не по порядку может скрыть задержку, и когда есть много умножений и сложений (или другой работы), которые могут происходить параллельно с делением.
(Целочисленное деление микрокодируется в Intel как несколько мопов, поэтому оно всегда оказывает большее влияние на окружающий код, который умножается на целое число. Спрос на высокопроизводительное целочисленное деление меньше, поэтому аппаратная поддержка не так уж и привлекательна. 1057 * микрокодированные инструкции, такие как 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 дает некоторый параллелизм на уровне команд в одном цикле body вместо одной огромной длинной цепочки депов, что значительно облегчает выполнение задач вне очереди.
В этом случае мы не ограничиваемся задержкой деления, потому что выполнение не по порядку может поддерживать несколько итераций цикла над массивами в полете.
Мы не ограничиваем разделение пропускная способность , пока наши полиномы достаточно велики, чтобы у нас было только одно деление на каждые 10 инструкций FMA или около того. (И в реальном log() сценарии использования будет куча работы, извлекающей экспоненту / мантиссу и снова объединяющей вещи, так что между делениями еще больше работы.)
Когда вам нужно делить, обычно лучше просто делить вместо rcpps
x86 имеет приблизительную обратную инструкцию (rcpps), которая дает вам только 12 бит точности. (AVX512F имеет 14 бит, а AVX512ER имеет 28 бит.)
Вы можете использовать это для выполнения x / y = x * approx_recip(y) без использования действительной инструкции деления. (rcpps itsef довольно быстрый; обычно немного медленнее, чем умножение. Он использует поиск по таблице из внутренней таблицы ЦП. Аппаратура делителя может использовать ту же таблицу для начальной точки.)
Для большинства целей x * rcpps(y) слишком неточно, и требуется итерация Ньютона-Рафсона для удвоения точности. Но это стоит вам 2 умножения и 2 FMA , и имеет задержку, примерно равную реальной инструкции деления. Если all , который вы делаете, является делением, то это может быть выигрыш в пропускной способности. (Но вы должны, во-первых, избегать такого рода циклов, если можете, возможно, делая деление как часть другого цикла, выполняющего другую работу.)
Но если вы используете деление как часть более сложной функции, сама rcpps + дополнительная муль + FMA обычно ускоряет деление с помощью инструкции divps, за исключением процессоров с очень низким divps пропускная способность.
(Например, Посадка Рыцаря, см. Ниже. KNL поддерживает AVX512ER , поэтому для float векторов результат VRCP28PS уже достаточно точен, чтобы просто умножаться без итерации Ньютона-Рафсона. float Размер мантиссы составляет всего 24 бита.)
Конкретные числа из таблиц Агнера Фога:
В отличие от любой другой операции ALU, задержка деления / пропускная способность зависит от данных некоторых процессоров. Опять же, это потому, что это так медленно и не полностью конвейерно. Внеочередное планирование легче с фиксированными задержками, потому что оно предотвращает конфликты обратной записи (когда один и тот же порт выполнения пытается выдать 2 результата в одном цикле, например, от выполнения команды 3 цикла и затем двух операций 1 цикла) .
Как правило, самые быстрые случаи, когда делитель представляет собой "круглое" число, такое как 2.0 или 0.5 (то есть представление base2 float имеет множество конечных нулей в мантиссе).
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).
Actualделить / умножать коэффициенты пропускной способности для скалярных (не векторизованных) double: 8 на Ryzen и Skylake с их увеличенными делителями, но 16-28 на Haswell (зависит от данных и более вероятно к концу цикла 28)если ваши делители не круглые числа).Эти современные процессоры имеют очень мощные делители, но их удвоенная пропускная способность по двум тактам просто поражает.(Тем более, когда ваш код может автоматически векторизоваться с векторами AVX 256b).Также обратите внимание, что при правильных параметрах компилятора эти мультипликативные пропускные способности также применяются к FMA.
Числа из http://agner.org/optimize/ таблиц инструкций для Intel Haswell / Skylake и AMD Ryzen для SSE-скаляра (не включая x87 fmul / fdiv) и для векторов AVX SIMD 256b float или double.См. Также тег x86 вики.