Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The radix 2^51 trick (2017)

chosenplaintext.ca

Post reply on HN
Print view View original

51–60 of 86 posts

Re: The radix 2^51 trick (2017)

#51

Post by phkahler »

nickcw wrote: post #29
alwahi wrote: post #26

how to do this for large multiplications instead?

You can do large multiplications with a convolution and do the carry afterwards. A convolution can be done with FFT, pointwise multiply, inverse FFT which is O(n log n) rather that O(n^2) for traditional multiplication. The bits in each limb can be quite small though as there are lots of carries and it depends on how many digits you have and how accurate your floating point is. Some kind of FFT is how all large multi…

GIMPS is also interesting since it doesn't need to do 2 operand multiplication. It only needs squaring.

Re: The radix 2^51 trick (2017)

#52

Post by rollcat »

Denvercoder9 wrote: post #41
rollcat wrote: post #27

Earlier quoted context omitted.

An unexpected optimisation can introduce a side channel (most commonly timing). This one would be safe, but "how do you tell a compiler which ones [not] to use" is a whole topic by itself.

The C++ standard doesn't forbid introducing side channels, so the answer to the question is yes.

With all the UB, I wonder how did we manage to write any secure or safety-critical code at all.

Re: The radix 2^51 trick (2017)

#53

Post by john-h-k »

phkahler wrote: post #50
john-h-k wrote: post #4

Earlier quoted context omitted.

uops.info has latency for both (Alder Lake) at 1 cycle but throughput (lower is better) * for add is 0.20 (ie 5 per cycle) * for adc is 0.50 (ie 2 per cycle) so it does seem correct. This seems to be a consequence of `add` being available on ports 0, 1, 5, 6, & B, whereas `adc` is only available on ports 0 & 6 So yes as an individual instruction it’s no worse, but even non-dependent instructions will be worse for OoO…

Intel is also supposed to introduce the new APX instructions which include a bunch of instructions that duplicate existing ones but don't set any flags. The only plausible reason to add these is for performance reasons.

This isn't just due to the actual dependencies of flag instructions at hardware level (although likely be a factor), it also majorly affects code layout. On Arm64 for example, you can make a comparison, do other operations, and then consume the result of that comparison afterwards, which is excellent for the pipeline and OoO engine. However, because most instructions on x86_64 write flags, you can't do this, and so you are forced to cram `jcc`/`setcc` instructions right after the comparison, which is less friendly to compilers and the OoO engine

Re: The radix 2^51 trick (2017)

#54

Post by Thorrez »

phkahler wrote: post #46
addaon wrote: post #2

> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. Why not give th…

>> Why not give the top limb 64 bits and the other four limbs 48 bits each, then? I think one goal is to use 5 64 bit registers to do 256 bit math. That means using 256/5 = 51.2 bits of each word. That's probably some kind of ideal if you want 256bit math, but not optimal if you're writing a generic big-int library. In the old days you'd want to use exactly one byte for the carry(s) because we didn't have barrel shif…

>That means using 256/5 = 51.2 bits of each word.

Why must each word have the same amount? Why not 64 bits on the top word, and 48 bits on the other 4 words?

Re: The radix 2^51 trick (2017)

#55

Post by brucehoult »

phkahler wrote: post #47
brucehoult wrote: post #12

Earlier quoted context omitted.

Also, there is another way to do this while keeping 64 bit limbs. All variables uint64_t. s0 += a0; s1 += a1; s2 += a2; s3 += a3; c0 = s0 The key insight here is that unless the sum at a particular limb position is all 1s the carry out from that position DOES NOT DEPEND on the carry in to that limb position, but only on whether the original add in that position produces a carry. If the sum is all 1s the the carry out…

I think you want to write: if (s1 == -1) c1 = c0; if (s2 == -1) c2 = c1; These can become conditional moves on x86. I've often thought RISC-V should have implemented an IF instruction instead of compare and branch. IF would cause the next instruction to be executed conditionally while not needing a flag register at the ISA level. They could have required only branch and jump to be conditional, but it turns out condit…

The problem is that, as far as I know, a conditional move is going to introduce a data dependency from c0 to c1 to c2 that is the exact thing we are trying to get rid of. The cmov is a constant time instruction, not a speculated instruction like a conditional branch.

The entire point of what I did is that the two conditional branches will be predicted not taken, so the CPU will 99.9999999999999999946% of the time not even see the `c1 = c0` and `c2 = c1` instructions that introduce the sequential dependencies.

Re: The radix 2^51 trick (2017)

#56

Post by brucehoult »

NooneAtAll3 wrote: post #21
brucehoult wrote: post #6

Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.

ha, I'm not the only one to think "so what's all the risc5 gmp fuss was about, if carry flag is slow anyway?"

Right.

Even at that time in 2021 I argued that serialising through a carry flag is limiting on wide machines, but there was very little RISC-V hardware available at the time and also GMP was not yet ported to RISC-V.

That has changed a bit now, and almost two months ago I tried the GMP project's own gmpbench on a few RISC-V boards.

I found that when comparing similar µarch at similar clock speed, in dual-issue in-order SiFive's U74 is very comparable to Arm's A53, and in small 3-wide OoO SiFive's P550 is significantly better than Arm's A72.

And that's not even using the kind of technique discussed in this post, but the full multi-instruction carry flag emulation criticised by Granlund.

https://www.reddit.com/r/RISCV/comments/1jsnbdr/gnu_mp_bignu...

It's going to be very interesting when the 8-wide OoO RISC-V cores come out, probably starting with Tenstorrent's Ascalon core which they expect to tape out in Q3 and they have said they want to get into as many hands as possible to accelerate RISC-V development, including in laptops, not only in servers or the like.

Re: The radix 2^51 trick (2017)

#57

Post by LegionMammal978 »

Thorrez wrote: post #54
phkahler wrote: post #46

Earlier quoted context omitted.

>> Why not give the top limb 64 bits and the other four limbs 48 bits each, then? I think one goal is to use 5 64 bit registers to do 256 bit math. That means using 256/5 = 51.2 bits of each word. That's probably some kind of ideal if you want 256bit math, but not optimal if you're writing a generic big-int library. In the old days you'd want to use exactly one byte for the carry(s) because we didn't have barrel shif…

>That means using 256/5 = 51.2 bits of each word. Why must each word have the same amount? Why not 64 bits on the top word, and 48 bits on the other 4 words?

Evenly distributing the number of bits per word lets you chain more additions/subtractions before having to normalize.

Re: The radix 2^51 trick (2017)

#58

Post by john-h-k »

john-h-k wrote: post #4
russdill wrote: post #3

I'm seriously doubtful that adc is inherently slower than add on a modern CPU other then the data hazard introduced by the carry bit. I realize the point of the article is the data hazard so this is a really minor nit.

uops.info has latency for both (Alder Lake) at 1 cycle but throughput (lower is better) * for add is 0.20 (ie 5 per cycle) * for adc is 0.50 (ie 2 per cycle) so it does seem correct. This seems to be a consequence of `add` being available on ports 0, 1, 5, 6, & B, whereas `adc` is only available on ports 0 & 6 So yes as an individual instruction it’s no worse, but even non-dependent instructions will be worse for OoO…

note: since learnt that B port is just port 11 in all the intel docs, uops.info just hexifies them to keep ports single-char

Re: The radix 2^51 trick (2017)

#59

Post by xigoi »

LegionMammal978 wrote: post #57
Thorrez wrote: post #54

Earlier quoted context omitted.

>That means using 256/5 = 51.2 bits of each word. Why must each word have the same amount? Why not 64 bits on the top word, and 48 bits on the other 4 words?

Evenly distributing the number of bits per word lets you chain more additions/subtractions before having to normalize.

Sure, but the point is that for the most significant limb, there is no point in having redundant bits because whatever you put in them will be discarded after normalization.

Re: The radix 2^51 trick (2017)

#60

Post by LegionMammal978 »

xigoi wrote: post #59
LegionMammal978 wrote: post #57

Earlier quoted context omitted.

Evenly distributing the number of bits per word lets you chain more additions/subtractions before having to normalize.

Sure, but the point is that for the most significant limb, there is no point in having redundant bits because whatever you put in them will be discarded after normalization.

Ah, in that case, you're right, it would make sense to use all 64 bits for the top limb. Still, making them all equal-sized can have benefits if you use SIMD or similar techniques to operate on them uniformly. One project of mine has been trying to work with large integers in CUDA by distributing their limbs across a warp.
Post reply on HN