Hello. I need to add two unsigned numbers modulo 2**32-1. Now it's done in very inefficient way: at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that. Does anybody know a better way to do that?
modulo 2**32-1 arith
Started by ●December 15, 2015
Reply by ●December 15, 20152015-12-15
Ilya Kalistru wrote:> Hello. > I need to add two unsigned numbers modulo 2**32-1. > Now it's done in very inefficient way: at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that. > Does anybody know a better way to do that?Sounds like you want an "end around carry." That means that the carry out of a 32-bit full adder wraps back to its carry in. In that way a 32-bit full adder would do what you want in one cycle. -- Gabor
Reply by ●December 15, 20152015-12-15
GaborSzakacs wrote:> Ilya Kalistru wrote: >> Hello. >> I need to add two unsigned numbers modulo 2**32-1. >> Now it's done in very inefficient way: at first clock cycle there is >> simple addition of two 32-bit unsigned numbers with 33-bit result and >> on second cycle if the result >= 2**32-1, we add 1 and take only 32 >> bits of that. >> Does anybody know a better way to do that? > > Sounds like you want an "end around carry." That means that the > carry out of a 32-bit full adder wraps back to its carry in. In > that way a 32-bit full adder would do what you want in one cycle. >Hmmm... On second thought, that would not handle the case where the inputs add up to exactly 2**32-1, since there would be no carry out, but you would want to add one to end up with zero. -- Gabor
Reply by ●December 15, 20152015-12-15
On 12/15/2015 5:32 AM, Ilya Kalistru wrote:> Hello. I need to add two unsigned numbers modulo 2**32-1. Now it's > done in very inefficient way: at first clock cycle there is simple > addition of two 32-bit unsigned numbers with 33-bit result and on > second cycle if the result >= 2**32-1, we add 1 and take only 32 bits > of that. Does anybody know a better way to do that?Not sure how efficient your implementation would be this way. You can achieve the same result by adding one to the sum and adding the high bit of this result to the original sum to get your answer. This should give a simpler result because of the comparison your approach uses requires a full adder rather than the incrementer of this approach. signal sum, temp, mod_result : unsigned (32 downto 0); signal answer : unsigned (31 downto 0); sum <= RESIZE(a, 33) + RESIZE(b, 33); temp <= sum + 1; mod_result <= sum + temp(32); answer <= mod_result(31 downto 0); Doing the addition with an end around carry will not cover the case of the sum being 2^n - 1. No guarantees of the code above. I'm a bit rusty these days. -- Rick
Reply by ●December 15, 20152015-12-15
On Tuesday, December 15, 2015 at 5:32:14 AM UTC-5, Ilya Kalistru wrote:> Hello. > I need to add two unsigned numbers modulo 2**32-1. > Now it's done in very inefficient way: at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that. > Does anybody know a better way to do that?Maybe you should revisit the need for 'modulo 2**32-1' instead of 'modulo 2**32'. Synthesis results of your method and Rickman's method indicate that the modulo portion is consuming significantly more logic than the addition itself. Given the code posted below, here are the synthesis results using Quartus to target a Cyclone IV GX: Method# Logic Elements Notes ======= ============== ===== 0 32 Sum <= A+B, no 'module 2**32-1' as a baseline 1 32 Sum <= A+B+1, as another reference point 2 76 Ilya's method 3 98 Rickman's method Kevin Jennings ===== START OF CODE ===== library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; entity Custom_Adder is generic(METHOD: integer range 0 to 3); port( A: in unsigned(31 downto 0); B: in unsigned(31 downto 0); C: out unsigned(31 downto 0) ); end Custom_Adder; architecture RTL of Custom_Adder is signal Sum: unsigned(32 downto 0); signal Sum_P1: unsigned(32 downto 0); constant MAX: unsigned(32 downto 0) := '0' & x"FFFF_FFFF"; begin Sum <= resize(A, Sum'length) + resize(B, Sum'length); Sum_P1 <= Sum + 1; -- KJ note: Performing all calculations on one clock cycle in order to determine logic cells. GEN_METHOD0: if (METHOD = 0) generate C <= Sum(C'range); end generate GEN_METHOD0; GEN_METHOD1: if (METHOD = 1) generate C <= Sum_P1(C'range); end generate GEN_METHOD1; GEN_METHOD2: if (METHOD = 2) generate -- Ilya's method: -- at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result -- and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that C <= Sum_P1(C'range) when (Sum >= MAX) else Sum(C'range); end generate GEN_METHOD2; GEN_METHOD3: if (METHOD = 3) generate signal Mod_Res: unsigned(32 downto 0); begin -- sum <= RESIZE(a, 33) + RESIZE(b, 33); -- temp <= sum + 1; -- mod_result <= sum + temp(32); -- answer <= mod_result(31 downto 0); -- The computation of 'mod_result' above Mod_Res <= Sum + unsigned'(Sum_P1(32 downto 32)); C <= Sum_P1(C'range) when (Sum_P1(32) = '1') else Sum(C'range); end generate GEN_METHOD3; end RTL; ===== END OF CODE =====
Reply by ●December 15, 20152015-12-15
On Tuesday, December 15, 2015 at 3:38:57 PM UTC-5, KJ wrote: OOPS, correction to the Method3 code: Original: C <= Sum_P1(C'range) when (Sum_P1(32) = '1') else C <= Mod_Res(C'range); Corrected: C <= Mod_Res(C'range); Number of logic elements used is 97 rather than 98. Kevin
Reply by ●December 15, 20152015-12-15
KJ wrote:> On Tuesday, December 15, 2015 at 5:32:14 AM UTC-5, Ilya Kalistru wrote: >> Hello. >> I need to add two unsigned numbers modulo 2**32-1. >> Now it's done in very inefficient way: at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that. >> Does anybody know a better way to do that? > > Maybe you should revisit the need for 'modulo 2**32-1' instead of 'modulo 2**32'. Synthesis results of your method and Rickman's method indicate that the modulo portion is consuming significantly more logic than the addition itself. Given the code posted below, here are the synthesis results using Quartus to target a Cyclone IV GX: > > Method# Logic Elements Notes > ======= ============== ===== > 0 32 Sum <= A+B, no 'module 2**32-1' as a baseline > 1 32 Sum <= A+B+1, as another reference point > 2 76 Ilya's method > 3 98 Rickman's method > > Kevin Jennings > > ===== START OF CODE ===== > library ieee; > use ieee.std_logic_1164.all; > use ieee.numeric_std.all; > > entity Custom_Adder is generic(METHOD: integer range 0 to 3); > port( > A: in unsigned(31 downto 0); > B: in unsigned(31 downto 0); > C: out unsigned(31 downto 0) > ); > end Custom_Adder; > > architecture RTL of Custom_Adder is > signal Sum: unsigned(32 downto 0); > signal Sum_P1: unsigned(32 downto 0); > constant MAX: unsigned(32 downto 0) := '0' & x"FFFF_FFFF"; > begin > Sum <= resize(A, Sum'length) + resize(B, Sum'length); > Sum_P1 <= Sum + 1; > > -- KJ note: Performing all calculations on one clock cycle in order to determine logic cells. > > GEN_METHOD0: if (METHOD = 0) generate > C <= Sum(C'range); > end generate GEN_METHOD0; > > GEN_METHOD1: if (METHOD = 1) generate > C <= Sum_P1(C'range); > end generate GEN_METHOD1; > > GEN_METHOD2: if (METHOD = 2) generate > -- Ilya's method: > -- at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result > -- and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that > C <= Sum_P1(C'range) when (Sum >= MAX) else Sum(C'range); > end generate GEN_METHOD2; > > GEN_METHOD3: if (METHOD = 3) generate > signal Mod_Res: unsigned(32 downto 0); > begin > -- sum <= RESIZE(a, 33) + RESIZE(b, 33); > -- temp <= sum + 1; > -- mod_result <= sum + temp(32); > -- answer <= mod_result(31 downto 0); > -- The computation of 'mod_result' above > Mod_Res <= Sum + unsigned'(Sum_P1(32 downto 32)); > C <= Sum_P1(C'range) when (Sum_P1(32) = '1') else Sum(C'range); > end generate GEN_METHOD3; > end RTL; > ===== END OF CODE =====I'm guessing the requirement for modulo 2**32-1 is driven by the algorithm, possibly some checksummy sort of thing. I know Fletcher uses 2**N-1 modulo pretty heavily. If your concern is speed rather than size, you could probably do it by running two parallel adders, Y0 = A+B and Y1 = A+B+1. If the Y1 add carries out then Y = Y1 else Y = Y0. Alternatively, the way you do it in an optimized Fletcher is in blocks. Add a whole bunch of samples together with sufficient extra bits on the high end to count the overflows, then periodicially stop taking in new data and add the overflows back into the LSBs. You could easily get that "periodically" down to once out of every 1024 samples. -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
Reply by ●December 15, 20152015-12-15
On 12/15/2015 4:31 PM, Rob Gaddi wrote:> KJ wrote: > >> On Tuesday, December 15, 2015 at 5:32:14 AM UTC-5, Ilya Kalistru wrote: >>> Hello. >>> I need to add two unsigned numbers modulo 2**32-1. >>> Now it's done in very inefficient way: at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that. >>> Does anybody know a better way to do that? >> >> Maybe you should revisit the need for 'modulo 2**32-1' instead of 'modulo 2**32'. Synthesis results of your method and Rickman's method indicate that the modulo portion is consuming significantly more logic than the addition itself. Given the code posted below, here are the synthesis results using Quartus to target a Cyclone IV GX: >> >> Method# Logic Elements Notes >> ======= ============== ===== >> 0 32 Sum <= A+B, no 'module 2**32-1' as a baseline >> 1 32 Sum <= A+B+1, as another reference point >> 2 76 Ilya's method >> 3 98 Rickman's method >> >> Kevin JenningsI'm not clear on how "Ilya's method" uses only 76 LEs. I assume an LE is a 4 input LUT and/or a register. I count at least 131. Producing Sum uses 33, producing Sum_P1 uses another 33, evaluating (Sum >= MAX) uses 33 then there are 32 used in the mux to select the result. How can that reduce to 76 LEs?>> ===== START OF CODE ===== >> library ieee; >> use ieee.std_logic_1164.all; >> use ieee.numeric_std.all; >> >> entity Custom_Adder is generic(METHOD: integer range 0 to 3); >> port( >> A: in unsigned(31 downto 0); >> B: in unsigned(31 downto 0); >> C: out unsigned(31 downto 0) >> ); >> end Custom_Adder; >> >> architecture RTL of Custom_Adder is >> signal Sum: unsigned(32 downto 0); >> signal Sum_P1: unsigned(32 downto 0); >> constant MAX: unsigned(32 downto 0) := '0' & x"FFFF_FFFF"; >> begin >> Sum <= resize(A, Sum'length) + resize(B, Sum'length); >> Sum_P1 <= Sum + 1; >> >> -- KJ note: Performing all calculations on one clock cycle in order to determine logic cells. >> >> GEN_METHOD0: if (METHOD = 0) generate >> C <= Sum(C'range); >> end generate GEN_METHOD0; >> >> GEN_METHOD1: if (METHOD = 1) generate >> C <= Sum_P1(C'range); >> end generate GEN_METHOD1; >> >> GEN_METHOD2: if (METHOD = 2) generate >> -- Ilya's method: >> -- at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result >> -- and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that >> C <= Sum_P1(C'range) when (Sum >= MAX) else Sum(C'range); >> end generate GEN_METHOD2; >> >> GEN_METHOD3: if (METHOD = 3) generate >> signal Mod_Res: unsigned(32 downto 0); >> begin >> -- sum <= RESIZE(a, 33) + RESIZE(b, 33); >> -- temp <= sum + 1; >> -- mod_result <= sum + temp(32); >> -- answer <= mod_result(31 downto 0); >> -- The computation of 'mod_result' above >> Mod_Res <= Sum + unsigned'(Sum_P1(32 downto 32)); >> C <= Sum_P1(C'range) when (Sum_P1(32) = '1') else Sum(C'range); >> end generate GEN_METHOD3; >> end RTL; >> ===== END OF CODE ===== > > I'm guessing the requirement for modulo 2**32-1 is driven by the > algorithm, possibly some checksummy sort of thing. I know Fletcher uses > 2**N-1 modulo pretty heavily. > > If your concern is speed rather than size, you could probably do it by > running two parallel adders, Y0 = A+B and Y1 = A+B+1. If the Y1 > add carries out then Y = Y1 else Y = Y0.That would reduce to the same complexity as my method as implemented above. My approach can be optimized by producing temp (Y1) from the two inputs. Then in parallel adding bit 32 into the sum of the two inputs that produces Y. Take Y modulo 2^n as the final step using 66 LEs. Like this... signal Y: unsigned(31 downto 0); signal Y, Y1, A, B: unsigned(32 downto 0); Y1 <= A + B + 1; Y <= resize(A + B + resize(Y1(32 downto 32),33), 32); If the tool is of any use it will add the upper bit of Y1 as a carry in to the sum of A + B utilizing a total of 65 LEs. -- Rick
Reply by ●December 16, 20152015-12-16
On Tuesday, December 15, 2015 at 7:16:42 PM UTC-5, rickman wrote:> > I'm not clear on how "Ilya's method" uses only 76 LEs. I assume an LE is > a 4 input LUT and/or a register.The target device family was stated.> I count at least 131. Producing Sum > uses 33, producing Sum_P1 uses another 33, evaluating (Sum >= MAX) uses > 33 then there are 32 used in the mux to select the result. How can that > reduce to 76 LEs? >It reduces because synthesis does not work how you how you have described it above.> That would reduce to the same complexity as my method as implemented > above. My approach can be optimized by producing temp (Y1) from the two > inputs. Then in parallel adding bit 32 into the sum of the two inputs > that produces Y. Take Y modulo 2^n as the final step using 66 LEs. Like > this... > > signal Y: unsigned(31 downto 0); > signal Y, Y1, A, B: unsigned(32 downto 0); > Y1 <= A + B + 1; > Y <= resize(A + B + resize(Y1(32 downto 32),33), 32); > > If the tool is of any use it will add the upper bit of Y1 as a carry in > to the sum of A + B utilizing a total of 65 LEs. >Your updated algorithm is actually the same as your first. There are also a few problems with your code that indicate that you did not bother to compile your design to produce actual results so your conclusions are simply speculating (and they are incorrect). - You've declared 'Y' twice, once to be a 32 bit vector, the other 33 bits. Minor thing, easily fixed - The calculation of Y1 is not correct and will result in Y1(32) always being 0 which then affects the computation of Y in the next line. This error functionally changes the output to simply be the 32 bit sum of the inputs mod 2^32, not mod 2^32-1 as requested. - The code you posted with the fix to remove the declaration of Y as a 33 bit number results in 32 logic cell usage not 66 as you speculated. However this number is not really meaningful because it is not computing what the OP wanted due to the second error. When that second error is corrected as shown in the code posted below, it result in the same 97 logic cells as your originally posted method. Bottom line is that what you have outlined for your method takes more logic simply because there is an additional adder required for your method that is not needed with Ilya's method. You and Rob are also not correct in thinking that computing Sum+1 as A+B+1 will save anything. In the updated code I've posted at the end, I've added another generic control called SP1_METHOD which is used to control how 'Sum + 1' gets computed. Sum + 1 can now be computed as: Sum_P1 <= Sum + 1; (as it was in the original code) or Sum_P1 <= A+B+1; Quartus sees through the smoke and produces the exact same logic independent of SP1_METHOD. However, Quartus can be made to overshoot: if you compute Sum + 1 as 'A+1+B' rather than 'A+B+1', then the resource usage shoots up from 76 to 108 using Ilya's method. This is the result posted for Method=6, SP1_Method=1. Obviously, Quartus is able to spot the common 'A+B' expression and not recompute it. The reason why changing the order of the two adds makes a difference is because the VHDL language specifies that the expression be evaluated from left to right and 'A+B+1' is not the same as 'A+1+B' in that context. The LRM does not allow for a 'commutative property of addition'. To take advantage of that mathematical property, the code must be explicitly written in a way that takes advantage of it. Back to the OP's problem. Barring a discovery of some other mathematical relationship that can be taken advantage of (which is what is really needed), what Ilya originally described is optimal. In fact, spreading the computation over two clock cycles as he described is the best approach. Whereas computing the output all within a single clock cycle takes 76 logic cells, spreading the computation into two clocks only takes 65 (see new Method=5). The tradeoff is the additional clock cycle of latency. Whether or not that is important in Ilya's application is for him to decide. Results for all of the variations are: Logic Elements Method# SP1=0 SP1=1 Notes 0 32 32 C <= A+B, no modulo '2**32-1' as a baseline 1 32 32 C <= A+B+1, as another reference point 2 76 76 Ilya's method although implemented all in one clock cycle 3 97 97 Rickman's method #1 4 97 97 Rickman's method #2 5 65 65 Ilya's method as stated, two clock cycles 6 76 108 Same as method 2, but when SP1_METHOD=1 it will computes Sum + 1 as A+1+B rather than A+B+1 Kevin Jennings ==== START OF CODE ==== library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; entity Custom_Adder is generic( SP1_METHOD: integer range 0 to 1; -- Controls how 'Sum + 1' is calculated METHOD: integer range 0 to 6); port( Clock: in std_ulogic; A: in unsigned(31 downto 0); B: in unsigned(31 downto 0); C: out unsigned(31 downto 0) ); end Custom_Adder; -- Results: -- Logic Elements -- Method# SP1=0 SP1=1 Notes -- 0 32 32 C <= A+B, no modulo '2**32-1' as a baseline -- 1 32 32 C <= A+B+1, as another reference point -- 2 76 76 Ilya's method although implemented all in one clock cycle -- 3 97 97 Rickman's method #1 -- 4 97 97 Rickman's method #2 -- 5 65 65 Ilya's method as stated, two clock cycles -- 6 76 108 Same as method 2, but when SP1_METHOD=1 it will computes Sum + 1 as A+1+B rather than A+B+1 architecture RTL of Custom_Adder is signal Sum: unsigned(32 downto 0); signal Sum_P1: unsigned(32 downto 0); constant MAX: unsigned(32 downto 0) := '0' & x"FFFF_FFFF"; begin Sum <= resize(A, Sum'length) + resize(B, Sum'length); Sum_P1 <= Sum + 1 when (SP1_METHOD = 0) else resize(A, Sum'length) + resize(B, Sum'length) + 1; -- KJ note: If you change Sum_P1 to compute A+1+B rather than A+B+1 then the number of logic cells -- increases by 27 (i.e. almost one for each bit of the adder -- KJ note: Performing all calculations on one clock cycle in order to determine logic cells. GEN_METHOD0: if (METHOD = 0) generate C <= Sum(C'range); end generate GEN_METHOD0; GEN_METHOD1: if (METHOD = 1) generate C <= Sum_P1(C'range); end generate GEN_METHOD1; GEN_METHOD2: if (METHOD = 2) generate -- Ilya's method, implemented all in one clock cycle: -- at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result -- and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that C <= Sum_P1(C'range) when (Sum >= MAX) else Sum(C'range); end generate GEN_METHOD2; GEN_METHOD3: if (METHOD = 3) generate signal Mod_Res: unsigned(32 downto 0); begin -- Rickman's first method -- sum <= RESIZE(a, 33) + RESIZE(b, 33); -- temp <= sum + 1; -- mod_result <= sum + temp(32); -- answer <= mod_result(31 downto 0); Mod_Res <= Sum + unsigned'(Sum_P1(32 downto 32)); C <= Mod_Res(C'range); end generate GEN_METHOD3; GEN_METHOD4: if (METHOD = 4) generate -- Rickman's second method -- signal Y: unsigned(31 downto 0); -- signal Y, Y1, A, B: unsigned(32 downto 0); <-- KJ note: Redclares 'Y' -- Y1 <= A + B + 1; <-- KJ note: Error: must have 33 elements not 32 -- Y <= resize(A + B + resize(Y1(32 downto 32),33), 32); signal Y: unsigned(31 downto 0); signal Y1: unsigned(32 downto 0); begin Y1 <= resize(A, 33) + resize(B, 33) + 1; Y <= resize(A + B + resize(Y1(32 downto 32),33), 32); C <= Y; end generate GEN_METHOD4; GEN_METHOD5: if (METHOD = 5) generate -- Ilya's method: -- at first clock cycle there is simple addition of two 32-bit unsigned numbers with 33-bit result -- and on second cycle if the result >= 2**32-1, we add 1 and take only 32 bits of that signal Sum_Dlyd: unsigned(Sum'range); signal Sum_Dlyd_P1: unsigned(Sum'range); begin Sum_Dlyd <= Sum when rising_edge(Clock); Sum_Dlyd_P1 <= Sum_Dlyd + 1; C <= Sum_Dlyd_P1(C'range) when (Sum_Dlyd(32) = '1') else Sum_Dlyd(C'range); end generate GEN_METHOD5; GEN_METHOD6: if (METHOD = 6) generate -- Same as method 2 (Ilya's method, implemented all in one clock cycle) except -- the ordering of operands for the computation of 'Sum + 1' is modified. signal Sum_P1: unsigned(Sum'range); begin Sum_P1 <= Sum + 1 when (SP1_METHOD = 0) else resize(A, Sum'length) + 1 + resize(B, Sum'length); C <= Sum_P1(C'range) when (Sum >= MAX) else Sum(C'range); end generate GEN_METHOD6; end RTL; ==== END OF CODE ====
Reply by ●December 16, 20152015-12-16
On Tuesday, December 15, 2015 at 4:33:51 PM UTC-5, Rob Gaddi wrote:> I'm guessing the requirement for modulo 2**32-1 is driven by the > algorithm, possibly some checksummy sort of thing. I know Fletcher uses > 2**N-1 modulo pretty heavily. >=20Could be right, at least there is some possible context now to the question= . Thanks.> If your concern is speed rather than size, you could probably do it by > running two parallel adders, Y0 =3D A+B and Y1 =3D A+B+1. If the Y1 > add carries out then Y =3D Y1 else Y =3D Y0. >=20See my earlier post today. Quartus will implement 'Y1=3DA+B+1' exactly the= same as 'Y1=3DY+1'.> Alternatively, the way you do it in an optimized Fletcher is in blocks.==20> Add a whole bunch of samples together with sufficient extra bits on the > high end to count the overflows, then periodicially stop taking in new > data and add the overflows back into the LSBs. You could easily get > that "periodically" down to once out of every 1024 samples. >=20Interesting idea, but I don't think it saves anything over Ilya's method. = Ilya's method as originally specified (i.e. spread out over two clock cycle= s) takes essentially 2 logic cells per bit (but it takes ~2.4 per bit for s= ingle clock cycle). When it comes time to periodically update the overflow= s that you mentioned, you will end up with another adder and consume anothe= r 32 logic cells (one per bit). Kevin Jennings
