Есть ли какое-либо (не микрооптимизация) усиление производительности при кодировании
Один из моих профессоров рассказал мне несколько лет назад, что деления с плавающей запятой были медленнее, чем умножения с плавающей запятой, не уточняя, почему.
Ответ 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.
