3 ms·
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 i
by nine_k 1y ago
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.
- repelsteeltje 1y agoYes. Another approach would be to use regular 64 bit chunks and speculatively execute each add with and without carry in parallel. Then select the correct variant based on carry result of less significant addition. With double the amount of additions this allows for log(bits) propagation time (versus linear)
- dgoldstein0 1y agoThere's not just "result with carry" and "result without carry" but rather one variant of that per word of the input ... Which likely isn't that bad to code up.
- brucehoult 1y agoOr see https://news.ycombinator.com/item?id=44133169 https://news.ycombinator.com/item?id=44133169
- volemo 1y agoWouldn’t that produce 2^n possible results to choose from, where n is the number of chunks? That seems like a lot of additional (he-he) instructions executed.
- repelsteeltje 1y agoNope. Just 2n: each chunk pair is added once without carry, and once won't carry=1. For as long as radix=2, you either have a carry or you don't.
- mananaysiempre 1y agoFor a single addition, the radix is irrelevant, the carry is always zero or one: (r-1) + (r-1) = 2r - 2 < 2r.
- account42 1y agoBut for a single addition you will also not save any time because you still need to do the select in series. The whole point of the radix 2^51 trick is that you can defer the normalization over several additions, but in order to do that your carry needs to be more than a single bit.
- rollcat 1y agoThis rule scales up all the way to multi-node supercomputers / cloud. The overhead is negligible when you can employ 10.000 cores.
- hinkley 1y agoAmdahl says no.
- noduerme 1y agoAbstractly, when any parallel system scales up large enough without cross checking or waiting between "threads", the cost of de-duplicating and merging the output will probably outweigh the advantage of producing new results in tandem. I think. That's just a hypothesis, but feels correct. With stuff like a-life distributed over lots of servers all converging on evolutionary answers to a problem, it's the collation and analysis layer that's most expensive and slow. Sharing more frequently / allowing more reliance on central historical truth slows each one down but avoids duplication and redundancy. I guess where that point is depends on what problem you're trying to solve.
- credit_guy 1y agoActually the overhead crushes you when you employ 10000 cores. If the overhead of a process is 10% and the parallel part is 90%, then 2 cores will result in a run time of 55% = 10% + 90%/2 of the original time. And 10 cores will get you to 19%. And 100 cores to 10.9%. If you then buy 9900 more cores to bring it to a total of 10000, you just reduced the runtime from 10.9% to 10.009%. In other words, you increased your bill by a factor of 100 to reduce your run time by almost nothing.
- volemo 1y agoYou two are talking about different kinds of overhead though.
- CamperBob2 1y agoYep. Company called NVidia has been looking into that general idea. They seem to be getting some promising results so far, in a couple of different areas.
- zahlman 1y agoWhat 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 order for this to be a net win?
- adgjlsfhk1 1y agoThat is paralelizable. Each of the 5 registers has no depence on the value of the others.
- zahlman 1y agoBut when you split from 4 registers to 5, the bits for a given destination register may come from two different source registers.
- brucehoult 1y agoThat only means you need a couple of instructions to do each one [1]. The five output registers are each dependent on (at most) a pair of the four input registers, but not on each other. [1] a left shift, a right shift, and an OR. Or just one 2->1 funnel shift instruction if your ISA has that e.g. arm64. And then ANDing with a 51 bit mask. and out0, in0, 0x7FFFFFFFFFFFF extr out1, in1, in0, #51 extr out2, in2, in1, #38 extr out3, in3, in2, #25 lsr out4, in3, #12 and out1, out1, 0x7FFFFFFFFFFFF and out2, out2, 0x7FFFFFFFFFFFF and out3, out3, 0x7FFFFFFFFFFFF