부동 소수점 나누기 대 부동 소수점 곱하기

부동 소수점 나누기 대 부동 소수점 곱하기

---

코딩으로 인한 성능 향상 (비 마이크로 최적화)이 있습니까?

float f1 = 200f / 2

비교하여

float f2 = 200f * 0.5

제 교수는 몇 년 전 저에게 이유를 설명하지 않고 부동 소수점 분할이 부동 소수점 곱셈보다 느리다고 말했습니다.

이 진술이 최신 PC 아키텍처에 적용됩니까?

업데이트 1

의견과 관련하여 다음 경우도 고려하십시오.

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 인용 업데이트 :

하드웨어에서 곱셈보다 분할을 훨씬 더 복잡하게 만드는 알고리즘 / 아키텍처 요구 사항이 무엇인지 알고 싶습니다.

---

예, 많은 CPU가 1 또는 2 클럭 사이클로 곱셈을 수행 할 수 있지만 나누기는 항상 더 오래 걸립니다 (FP 나누기가 때때로 정수 나누기보다 빠름).

이 답변 을 보면 나눗셈이 24주기를 초과 할 수 있음을 알 수 있습니다.

나누기가 곱셈보다 더 오래 걸리는 이유는 무엇입니까? 초등학교로 돌아간 것을 기억한다면 곱셈은 본질적으로 많은 동시 덧셈으로 수행 될 수 있다는 것을 기억할 것입니다. 나누기는 동시에 수행 할 수없는 반복적 인 빼기가 필요하므로 시간이 더 걸립니다. 실제로 일부 FP 장치는 상호 근사를 수행하고이를 곱하여 분할 속도를 높입니다. 정확하지는 않지만 다소 빠릅니다.

---

나눗셈은 본질적으로 곱셈보다 훨씬 느린 연산입니다.

그리고 이것은 사실 컴파일러 가 부동 소수점 부정확성으로 인해 많은 경우 최적화 할 수없는 (그리고 여러분이 원하지 않을 수도있는) 것일 수 있습니다. 이 두 진술 :

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

아르 하지 의미 동일 - 0.1정확히로 표현할 수없는 double끝날 약간 다른 값을 사용하므로, - 서로 다른 결과를 생성 할 경우,이 분할에 대한 승산 치환!

---

분할에 매우주의하고 가능하면 피하십시오. 예를 들어, float inverse = 1.0f / divisor;루프 밖으로 들어 올려 루프 inverse내부에서 곱 합니다. (반올림 오차 inverse가 허용되는 경우)

일반적으로 또는 1.0/x로 정확하게 표시 할 수 없습니다 . 때 정확한 것입니다 이것은 컴파일러의 최적화를 할 수 있습니다 (2)의 힘 에 결과의 변화없이가.floatdoublexx / 2.0fx * 0.5f

결과가 정확하지 않을 때 (또는 런타임 변수 제수를 사용하는 경우)에도 컴파일러가이 최적화를 수행하도록하려면 gcc -O3 -ffast-math. 특히, -freciprocal-math(으로 활성화 -funsafe-math-optimizations하여 사용할 -ffast-math컴파일러 교체 할 수 있습니다) x / y과 x * (1/y)그 유용합니다. 다른 컴파일러에도 비슷한 옵션이 있으며 ICC는 기본적으로 "안전하지 않은"최적화를 활성화 할 수 있습니다 (그렇다고 생각하지만 잊어 버렸습니다).

-ffast-mathFP 수학은 연관성이 아니기 때문에 FP 루프의 자동 벡터화, 특히 감소 (예 : 배열을 하나의 스칼라 합계로 합산)를 허용하는 데 종종 중요합니다. GCC가 a * a * a * a * a * a를 (a * a * a) * (a * a * a)로 최적화하지 않는 이유는 무엇입니까?

또한 노트는 C ++ 컴파일러는 접을 수 +와 *(지원이, 같이하는 대상에 대해 컴파일 할 때 어떤 경우에 FMA에 -march=haswell, 그러나 함께 할 수 없어) /.

---

부문 곱셈 또는 추가 (또는보다 더 지연이 FMA 6 ~ 40의 요인에 의해 현대의 x86 CPU에서 4-2의 배), 악화 처리량 ¹ (일을 꽉 루프 만 이 아닌 부문 에만 셈).

나누기 / sqrt 단위는 @NathanWhitehead의 답변에 설명 된 이유 때문에 완전히 파이프 라인되지 않습니다 . 최악의 비율은 256b 벡터에 대한 것입니다. (다른 실행 단위와 달리) 분할 단위는 일반적으로 전체 너비가 아니기 때문에 넓은 벡터는 두 개의 절반으로 이루어져야합니다. 완전 파이프 라인되지 않은 실행 단위는 매우 드문 경우이므로 Intel CPU에는 arith.divider_active일반적인 프런트 엔드 또는 실행 포트 병목 현상 대신 분할기 처리량에 병목 현상이있는 코드를 찾는 데 도움 이되는 하드웨어 성능 카운터가 있습니다. (또는 더 자주, 명령어 수준 병렬 처리를 제한하는 메모리 병목 현상이나 긴 대기 시간 체인으로 인해 명령어 처리량이 클럭 당 ~ 4 미만이됩니다.)

그러나 Intel 및 AMD CPU (KNL 제외)의 FP 분할 및 sqrt는 단일 uop으로 구현되므로 주변 코드에 큰 처리량 영향을주지는 않습니다 . 나누기에 가장 좋은 경우는 비 순차적 실행이 지연 시간을 숨길 수 있고 나누기와 동시에 발생할 수있는 곱셈과 더하기 (또는 기타 작업)가 많은 경우입니다.

(정수 분할은 Intel에서 다중 uop으로 마이크로 코딩되므로 정수가 곱하는 주변 코드에 항상 더 많은 영향을줍니다. 고성능 정수 분할에 대한 수요가 적기 때문에 하드웨어 지원이 화려하지 않습니다. 관련 : can 과 같은 마이크로 코딩 된 명령어 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]에 병목 현상 이 발생 하지만 부서가 중요 경로 (루프 전달 종속성 체인)에 없기 때문에 지연 시간이 아닙니다.adddivdiv

---

그러나 이와 같은 ( 두 다항식의 비율 과 같은 함수를 근사화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)을 평가하는 대규모 길게하면 대신 하나의 단일 루프 본체 내의 일부 명령 수준의 병렬 처리를 제공 가수의 범위 dep 체인을 사용하면 비 순차적 실행이 훨씬 쉬워집니다.

이 경우, 비 순차적 실행은 비행중인 어레이에서 루프의 여러 반복을 유지할 수 있으므로 분할 지연에 병목 현상이 발생하지 않습니다.

다항식이 10 개의 FMA 명령어에 대해 하나의 나누기 만 가질 수있을만큼 충분히 크면 나누기 처리량 에 병목 현상이 발생하지 않습니다 . (실제 log()사용 사례에서는 지수 / 가수를 추출하고 다시 결합하는 작업이 많으므로 나누기 사이에 할 일이 더 많습니다.)

---

나눌 필요가있을 때 일반적으로 나누는 대신 나누는 것이 가장 좋습니다. rcpps

x86에는 rcpps12 비트의 정밀도 만 제공 하는 근사 역수 명령어 ( )가 있습니다. (AVX512F는 14 비트, AVX512ER는 28 비트입니다.)

x / y = x * approx_recip(y)실제 나누기 명령어를 사용 하지 않고도 이를 수행 할 수 있습니다 . ( rcppsitsef는 상당히 빠르며 일반적으로 곱셈보다 약간 느립니다. CPU 내부 테이블에서 테이블 조회를 사용합니다. 분할기 하드웨어는 시작점으로 동일한 테이블을 사용할 수 있습니다.)

대부분의 경우 x * rcpps(y)는 너무 부정확하며 정밀도를 두 배로 늘리기위한 Newton-Raphson 반복이 필요합니다. 그러나 2 개의 곱셈과 2 개의 FMA 가 필요하며 실제 나누기 명령어만큼 지연 시간이 있습니다. 경우 모든 당신이하고있는이 부서입니다, 그것은 처리량 승리 할 수 있습니다. (하지만 가능한 한 다른 작업을 수행하는 다른 루프의 일부로 분할을 수행하여 처음에 이러한 종류의 루프를 피해야합니다.)

그러나 더 복잡한 함수의 일부로 rcpps나누기를 사용하는 divps경우 divps처리량 이 매우 낮은 CPU를 제외하고 는 일반적으로 자체 + 추가 다중 + FMA를 사용하여 명령으로 나누는 것이 더 빠릅니다 .

(예를 들어 Knight 's Landing, 아래 참조. KNL은 AVX512ER를 지원 하므로 float벡터의 VRCP28PS경우 결과는 이미 Newton-Raphson 반복없이 곱할 수있을만큼 정확합니다. float가수 크기는 24 비트에 불과합니다.)

---

Agner Fog의 테이블에있는 특정 숫자 :

Unlike every other ALU operation, division latency/throughput is data-dependent on some CPUs. Again, this is because it's so slow and not fully pipelined. Out-of-order scheduling is easier with fixed latencies, because it avoids write-back conflicts (when the same execution port tries to produce 2 results in the same cycle, e.g. from running a 3 cycle instruction and then two 1-cycle operations).

Generally, the fastest cases are when the divisor is a "round" number like 2.0 or 0.5 (i.e. the base2 float representation has lots of trailing zeros in the mantissa).

float latency (cycles) / throughput (cycles per instruction, running just that back to back with independent inputs):

                   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 latency (cycles) / throughput (cycles per instruction):

                   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)

Ivybridge and Broadwell are different too, but I wanted to keep the table small. (Core2 (before Nehalem) has better divider performance, but its max clock speeds were lower.)

Atom, Silvermont, and even Knight's Landing (Xeon Phi based on Silvermont) have exceptionally low divide performance, and even a 128b vector is slower than scalar. AMD's low-power Jaguar CPU (used in some consoles) is similar. A high-performance divider takes a lot of die area. Xeon Phi has low power per-core, and packing lots of cores on a die gives it tighter die-area constraints that Skylake-AVX512. It seems that AVX512ER rcp28ps / pd is what you're "supposed" to use on KNL.

(See this InstLatx64 result for Skylake-AVX512 aka Skylake-X. Numbers for vdivps zmm: 18c / 10c, so half the throughput of ymm.)

---

Long latency chains become a problem when they're loop-carried, or when they're so long that they stop out-of-order execution from finding parallelism with other independent work.

---

Footnote 1: how I made up those div vs. mul performance ratios:

FP divide vs. multiple performance ratios are even worse than that in low-power CPUs like Silvermont and Jaguar, and even in Xeon Phi (KNL, where you should use AVX512ER).

Actual divide/multiply throughput ratios for scalar (non-vectorized) double: 8 on Ryzen and Skylake with their beefed-up dividers, but 16-28 on Haswell (data-dependent, and more likely towards the 28 cycle end unless your divisors are round numbers). These modern CPUs have very powerful dividers, but their 2-per-clock multiply throughput blows it away. (Even more so when your code can auto-vectorize with 256b AVX vectors). Also note that with the right compiler options, those multiply throughputs also apply to FMA.

Numbers from http://agner.org/optimize/ instruction tables for Intel Haswell/Skylake and AMD Ryzen, for SSE scalar (not including x87 fmul / fdiv) and for 256b AVX SIMD vectors of float or double. See also the x86 tag wiki.

---

Yes. Every FPU I am aware of performs multiplications much faster than divisions.

However, modern PCs are very fast. They also contain pipelining archtectures that can make the difference negligable under many circumstances. To top it off, any decent compiler will perform the division operation you showed at compile time with optimizations turned on. For your updated example, any decent compiler would perform that transformation itself.

So generally you should worry about making your code readable, and let the compiler worry about making it fast. Only if you have a measured speed issue with that line should you worry about perverting your code for the sake of speed. Compilers are well aware of what is faster than what on their CPU's, and are generally much better optimizers than you can ever hope to be.

---

Think about what is required for multiplication of two n bit numbers. With the simplest method, you take one number x and repeatedly shift and conditionally add it to an accumulator (based on a bit in the other number y). After n additions you are done. Your result fits in 2n bits.

For division, you start with x of 2n bits and y of n bits, you want to compute x / y. The simplest method is long division, but in binary. At each stage you do a comparison and a subtraction to get one more bit of the quotient. This takes you n steps.

Some differences: each step of the multiplication only needs to look at 1 bit; each stage of the division needs to look at n bits during the comparison. Each stage of the multiplication is independent of all other stages (doesn't matter the order you add the partial products); for division each step depends on the previous step. This is a big deal in hardware. If things can be done independently then they can happen at the same time within a clock cycle.

---

Newton rhapson solves integer division in O(M(n)) complexity via linear algebra apploximation. Faster than The otherwise O(n*n) complexity.

In code The method contains 10mults 9adds 2bitwiseshifts.

This explains why a division is roughly 12x as many cpu ticks as a multiplication.

---

The answer depends on the platform for which you are programming.

For example, doing lots of multiplication on an array on x86 should be much faster then doing division, because the compiler should create the assembler code which uses SIMD instructions. Since there are no division in the SIMD instructions, then you would see great improvements using multiplication then division.

참고URL : https://stackoverflow.com/questions/4125033/floating-point-division-vs-floating-point-multiplication