61–70 of 86 posts
Earlier quoted context omitted.
There remain many frequently-encountered cases when carry-save addition is worse than addition using add-with-carry. Neither of the 2 multi-word addition algorithms can replace the other, both have their use cases, so ADC/SBB instructions are included in any decent ISA, because the cost of adding them is negligible. A dedicated flag register is not necessary, some ISAs store the carry/borrow flags in general-purpose…
>> because the software workaround for detecting integer overflow, which is mandatory for any program that claims to be written in a safe way, lowers the attainable performance much more than the workarounds for not having carry That's absurd. A better way is to ensure that your algorithms don't overflow. Detecting an overflow just means your code has to STOP which is usually not safe. It'd be insane to have conditio…
While it'd be nice to have a formal proof that every single `a+b`, `a-b`, `a*b` in every codebase doesn't overflow, I'm sure you understand that that is rather impractical. (and really, it'd be nice! I've thought about having some compile-time-bounded-size integers where each addition increases the size, but multiplication is much less suitable for that, and it also means you can't have a loop adding to an accumulator. It's a rather non-trivial problem really - you might think that it'd be fine to have a loop over a list of objects and sum their sizes, but that can relatively easily overflow if the list references the same massive object many times, so can't even really abstract that)
Someone working entirely on x86_64 very nicely demonstrates that RISC-V is not wrong to omit the carry flag.
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…
If you can substitute a cmov without control flow then it's probably safer, e.g. c1 |= c0 & seq(s1,-1) or so, so long as you can make sure the compiler won't turn it into a branch.
It does add a data dependency though ...
The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
> 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…
The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
But - you still have to split the input numbers into sets of 5 registers in the first place, right? So doesn't that need to be parallelizable somehow as well in order for this to be a net win?
The main takeaway: doing more operations may be faster if they are largely independent, and thus can execute in parallel. Doing fewer operations may be slower if they are forced to execute serially due to data dependency. This idea has wider applicability than operations on long integers.
What I didn't get about this: the technique shown seems to be about making sure that the ripple carry only happens once instead of N-1 times while adding N values. The carry operation is more complex, but this allows the actual addition to be parallelized. But - you still have to split the input numbers into sets of 5 registers in the first place, right? So doesn't that need to be parallelizable somehow as well in or…
With AVX512 (and to a lesser extent with AVX2) one can implement 256 bit addition pretty efficiently with the additional benefit of fitting more numbers in registers. It looks more or less like this: __m256i s = _mm256_add_epi64(a, b); const __m256i all_ones = _mm256_set1_epi64x(~0); int g = _mm256_cmpgt_epu64_mask(a, s); int p = _mm256_cmpeq_epu64_mask(s, all_ones); int carries = ((g The throughput even seems to be…
https://stackoverflow.com/questions/56852812/simd-instructio...
With AVX512 (and to a lesser extent with AVX2) one can implement 256 bit addition pretty efficiently with the additional benefit of fitting more numbers in registers. It looks more or less like this: __m256i s = _mm256_add_epi64(a, b); const __m256i all_ones = _mm256_set1_epi64x(~0); int g = _mm256_cmpgt_epu64_mask(a, s); int p = _mm256_cmpeq_epu64_mask(s, all_ones); int carries = ((g The throughput even seems to be…
Note that, especially on certain Intel architectures, using AVX512 instructions _at all_ can result in the whole processor downclocking, and thus ending up resulting in inconsistent / slower overall performance. https://stackoverflow.com/questions/56852812/simd-instructio...
This isn't correct. AVX512 provides both a bunch of extra instructions, zmm (512 bit) registers, and an extra 16 (for a total of 32) vector registers. The donwnclocking only happens if you use 512 bit registers (not just avx512 instructions). The difference here matters a bunch since there are a bunch of really useful instructions (e.g. 64 bit integer multiply) that are added by avx512 that are pure upside.
Also none of this is an issue on Zen4 or Zen5 since they use much more sensible downlclocking where it will only downclock if you've used enough instructions in a row for it to start spiking power/temp.
Earlier quoted context omitted.
Note that, especially on certain Intel architectures, using AVX512 instructions _at all_ can result in the whole processor downclocking, and thus ending up resulting in inconsistent / slower overall performance. https://stackoverflow.com/questions/56852812/simd-instructio...
> using AVX512 instructions _at all_ This isn't correct. AVX512 provides both a bunch of extra instructions, zmm (512 bit) registers, and an extra 16 (for a total of 32) vector registers. The donwnclocking only happens if you use 512 bit registers (not just avx512 instructions). The difference here matters a bunch since there are a bunch of really useful instructions (e.g. 64 bit integer multiply) that are added by a…
General idea was just to highlight some of the dangers of vector registers. I believe the same is true of ymm (256) to a lesser extent.