eyepatchparrot / 759-bignum Goto Github PK

The essence of subtraction is simply addition with a negation and a carry in.

However, manipulating the correct size of the output may not be trivial and ensuring that carries are handled correctly may also prove to be a challenge.

11/10

11/10

11/24

I think the three way split needs regression testing,

11/24

Many potential optimizations available to GPUs not available to hardware due to no area overheads and warp scheduling improving performance. (Being able to eliminate a group of 32 threads could improve performance.)

http://www.cl.cam.ac.uk/research/srg/han/ACS-P35/8-bit-KoggeStone-Adder.pdf
p_i = A_i xor B_i
g_i = A_i and B_i
P_i:j = P_i:k+1 and P_k:j
G_i:j = G_i:k+1 or (P_i:k+1 and G_k:j)

S_i = p_i xor C_i-1

1. Implement with 1 bit / thread exactly as prescribed.
2. Consider vectorizing with 32 bits / thread. At 2048 threads / MP * 60 MPs * 32 additions / thread ~ 4 million additions to saturate = 15MB operands.
3. Compare against using addition + cmp ops at various stages to see if acceleration is possible. Only try if addition is still slow.

Rather than doing an addition followed by carry, calculate all carry information and do carry adds, followed by an addition operation without carries.

What collisions are possible with byte-level carries?

Because we don't have block-wise carries at the addition stage, can't finalize any results. It might be worth it to spend memory to speculate on outcome given a block carry and given no block carry. I'm not sure that's any better than actually

11/10