Reconfigurable Computing -

Adders

Oliver Sinnen
Electrical and Computer Engineering
The University of Auckland
Adders
VHDL and hardware synthesising tools
 Modern synthesising tools can create adders
automatically for a “+” in VHDL code

=> So why should we be concern with adders, we are

engineers?
Why should we be concern with adders?
Because:
 Excellent example on how structure influences
performance
 Similar challenges encountered in other areas of reconfigurable
computing
 In general – in practice it also depends on the used hardware
 Often appear on the critical path
 Adder performance can be crucial for system performance
 Basic building block in most designs
 Arithmetic adders (including subtractors)
 Other arithmetic operators
 eg multipliers, dividers
 Counters (including program counters in processors)
 Incrementors, decrementors, etc
Adder structures
 Because of their importance, researchers are still
searching for better ways to add!
 Adder structures proposed already
 Ripple carry
 Carry select
 Carry skip
 Carry look-ahead
 Hybrid
 Manchester
 … and several dozen more variants
 Adder structures discussed here
 Ripple carry
 already discussed – only fast with special 'fast-carry logic'
 Carry select
 Carry look-ahead
 Hybrid adders
 Serial adder
 Subtractor

Start with
 Review of basic blocks
 Critical path
 • : and

Review: Half and Full Adder + : or

 Half Adder (HA):

 Input: operand bits a, b a s
 Output: sum bit s and carry-out cout HA
b cout

s=a xor b=a b  a b

c out =a⋅b=ab
 • : and

Review: Half and Full Adder + : or

 Half Adder (HA):

 Input: operand bits a, b a s
 Output: sum bit s and carry-out cout HA
b cout

s=a xor b=a b  a b

c out =a⋅b=ab
 Full Adder (FA):
 Input: operand bits a, b and carry-in cin
 Output: sum bit s and carry-out cout
a s
s=a xor b xor c in =abc in  a b c in  a b cin a b cin b FA
cout
cin
c out =abac in bc in
Critical path
 Latency input -> output
 Worst case signal propagation path

Example: ripple carry adder, n bits

an-1 bn-1 an-2 bn-2 a1 b1 a0 b0

FA FA FA FA
cout cin cout cin cout cin cout cin

sn-1 sn-2 s1 s0
carry
out
Critical path
 Latency input -> output
 Worst case signal propagation path

Example: ripple carry adder, n bits

an-1 bn-1 an-2 bn-2 a1 b1 a0 b0

FA FA FA FA
cout cin cout cin cout cin cout cin

sn-1 sn-2 s1 s0
carry
out
Critical path
 Example: ripple carry adder, n bits

an-1 bn-1 an-2 bn-2 a1 b1 a0 b0

FA FA FA FA
cout cin cout cin cout cin cout cin

sn-1 sn-2 s1 s0
carry
out

T ripple-add =T FA a , b  c out n−2T FA c in  c out T FA c in  s

 Latency is linear in number of bits

 => O(n)
 Fast-carry logic improves T FA c in  c out 
Carry-select adder
 Improving complexity!

Carry-select adder
 Idea: use redundant adder blocks
 Replicate adder blocks
 One for cin = 0
 One for cin = 1
 Use simple multiplexer to choose result based on real
cin from preceding block
Carry-select adder

n-1 n/2
0
n/2-bit adder n/2-1 0
cin
n/2-bit adder 1 n/2-bit adder

n/2+1 n/2+1
n/2

1 0 cn/2
Mux

cout, high n/2 bits low n/2 bits

Carry-select adder
 All n/2-bit adders work in parallel

n-1 n/2
0
n/2-bit adder n/2-1 0
cin
n/2-bit adder 1 n/2-bit adder

n/2+1 n/2+1
n/2

1 0 cn/2
Mux

cout, high n/2 bits low n/2 bits

T CSA =T add n/ 2T Mux ≈T add n/ 2

Carry-select adder
 CSA concept can be generalised to any number of bits
and stages

Straightforward approach:
 Chain several stages

For example:
 using 4 bit adders
 stages: k = n/4
T CSA =T 4bit-add n/ k k −1T Mux

 => complexity still linear

Carry-select adder
For logarithmic time complexity:
 Use levels – here 2 levels
n-1 3n/4 3n/4-1 n/2 n/2-1 n/4
0 0 0 n/4-1 0
n/4-bit adder n/4-bit adder n/4-bit adder cin
n/4-bit adder
n/4-bit adder 1 n/4-bit adder 1 n/4-bit adder 1

n/4+1 n/4+1 n/4 n/4 n/4+1 n/4+1

1 Mux 0 1 Mux 0 cn/4

n/4

n/4
1 0
Mux cn/2
n/2+1

cout, high n/2 bits middle n/4 bits low n/4 bits
Carry-select adder

T CSA, 2levels =T add n/ 42 T Mux

n-1 3n/4 3n/4-1 n/2 n/2-1 n/4

0 0 0 n/4-1 0
n/4-bit adder n/4-bit adder n/4-bit adder cin
n/4-bit adder
n/4-bit adder 1 n/4-bit adder 1 n/4-bit adder 1

n/4+1 n/4+1 n/4 n/4 n/4+1 n/4+1

1 Mux 0 1 Mux 0 cn/4

n/4

n/4
1 0
Mux cn/2
n/2+1

cout, high n/2 bits middle n/4 bits low n/4 bits
Carry propagation
 General performance problem of adders is the carry
propagation
 In each stage of an adder a carry is either
 generated
 propagated
 annihilated (absorbed)

Equations:
g i =a i bi generate ai si
bi FA
p i =a i xor b i propagate ci+1
ci
a i =a i b i =ai b i annihilate
Carry propagation
Carry equation g i =a i b i
c out =abac in bc in p i =a i xor b i
c i1=ai bi ai c i bi c i
Carry recurrence using gi and pi
c i1=g i  pi c i

=> Carry enters stage i+1 if

it is generated in stage i
or
it enters stage i and it is propagated by that stage
 General formulation of carry propagation, independent
of number system
Unrolling the carry recurrence
Unrolling
c i1 =g i  p i c i
=g i  p i  g i−1 p i−1 c i−1 =g i  p i g i−1 pi pi−1 c i−1
=
For n=4

c1 =g 0  p 0 c 0
c2 =g 1 p1 g 0  p1 p 0 c 0
c3 =g 2 p 2 g 1 p 2 p1 g 0  p 2 p1 p0 c 0
c4 =g 3 p 3 g 2 p 3 p 2 g 1 p3 p 2 p1 g 0  p 3 p 2 p1 p 0 c 0

 Carry lookahead!
Carry-lookahead adder
c1 =g 0 p 0 c 0
c2 =g 1 p1 g 0  p1 p0 c 0
c3 =g 2 p 2 g 1 p 2 p1 g 0 p 2 p1 p0 c 0
c4 =g 3  p 3 g 2  p 3 p 2 g 1 p3 p 2 p1 g 0 p 3 p 2 p1 p0 c 0

 Can be calculated using two level AND-OR logic

circuit!
 For n=4: 4 p, 4 g and 1 c inputs
 Impractical for large n's
 Fan-in of gates is n+1
=> For large n => tree networks – high latency
Solution:
 Multilevel lookahead
Multilevel carry-lookahead
 Define block generate and propagate
 4-bit block
p[0,3]= p 3 p 2 p1 p 0
g [0,3]= g 3 p 3 g 2 p 3 p 2 g 1 p 3 p 2 p1 g 0

 Using this, c5 can be written as

c5 = g 4 p 4 c 4
= g 4  p 4  g 3 p 3 g 2  p 3 p 2 g 1 p 3 p 2 p 1 g 0  p 3 p 2 p1 p 0 c 0 
= g 4 p 4  g [0,3] p[0,3] c 0 
Note, same form as equation for c1
c 1= g 0  p 0 c 0 c 0 ⇒ g [0,3] p[0,3] c 0
=> same logic circuit can be used
Multilevel carry-lookahead
 Lookahead carry generator
c3 c2 c1
g3 p3 g2 p2 g1 p1 g0 p0

4-bit lookahead carry generator c0

g[0,3] p[0,3]
Multilevel carry-lookahead
 16-bit carry lookahead adder

4-bit adder & lookahead carry generator

c12 c8 c4
g[12,15] g[8,11] g[4,7] g[0,3]
p[12,15] p[8,11] p[4,7] p[0,3]

4-bit lookahead carry generator c0

g[0,15] p[0,15]
 Multilevel carry-lookahead
 16-bit carry lookahead
adder 4-bit adder & lookahead carry generator

Latency through adder:

c12 c8 c4
 Producing g and p for individual
bit positions (1 gate level) g[12,15] g[8,11] g[4,7] g[0,3]
 Producing g and p for 4-bit p[12,15] p[8,11] p[4,7] p[0,3]
blocks (2 gl)
4-bit lookahead carry generator c0
 Predicting c , c , c for the
4 8 12
blocks (2 gl)
c0
 Predicting internal carries within g[0,15] p[0,15]
each 4-bit block (2 gl)
 Computing the sum bits (2 gl)
Total:
9 gate levels (for comparison: 16-bit RCA 32 gate levels)
 Multilevel carry-lookahead
n-bit carry lookahead adder
 Each level adds 4 gate levels 16-bit carry lookahead adder

4-bit adder & lookahead carry generator

c12 c8 c4
g[12,15] g[8,11] g[4,7] g[0,3]
p[12,15] p[8,11] p[4,7] p[0,3]
16 16
4-bit lookahead carry generator c0
.....
g[0,15] p[0,15]

4-bit lookahead carry generator

T lookahead-add,4bit-block =4 log 4 n1 gate level

Optimal adder
 Performance of adders depends on complexity AND
technology

Adder choice criteria:

 Adder size – number of bits n
 Implementation technology
 FPGA, ASIC, CMOS, ...
 Performance requirements
 Necessary speed
 Design constraints
 Available gates
 Layout constraints (eg column/row)
 Costs
 Fast Adders
 Challenge: What style of adder is fastest / most compact for any
FPGA technology?
 Answer is not simple
 For small adders (n < ?),
fast carry logic will certainly make a simple ripple carry
adder fastest
 It will also use the minimum resources - but will need to be laid
out as a column or row
 For larger adders ( ? < n < ? ),
carry select styles are likely to be best -
 They use ripple carry blocks efficiently
 For very large adders ( n > ? ),
a carry look ahead adder may be faster?
 But it will use considerably more resources!
 Adder design parameters
 Block size
 Number of levels

For example CS/CLA:

 Block size determined by technology used
 It will need to match logic block capability
 It will need to balance internal LUT propagation delay with link delay
+ effectiveness of additional capabilities,
eg Altera cascade chains

 Usually experiments are needed to determine optimal

proportions (block size, levels ...) for adders
 Hybrid adders
 Combining two or more design methods
 Small ripple carry adders (few bits) are often building
blocks of larger adders
 Especially when fast carry logic exists on target platform,
which makes these adders fast
 Carry-select adders are hybrid adders
 Redundant top-level adders can be of any type, eg ripple carry
 Combinations of carry-lookahead and carry-select are quite
common
 In both ways
 Can reduce design complexity
 Can avoid additional levels
 eg instead of 3 only 2 levels carry-lookahead
 Active research on new combinations
Serial adder
 Sometimes adder performance is not an issue, but
space is
 For example for highly parallel problems
 Many small adders!

Solution:
sum
 Bit serial adder a

register
2-bit
 Space efficient b FA cout
cin
 Slow!
 1 bit of result per cycle
clock
 Serial adder
sum
a

register
In VHDL

2-bit

b FA cout
cin
ENTITY serial_add IS
PORT( a, b, clk : IN std_logic;
sum, cout : OUT std_logic );
END ENTITY serial_add; clock

ARCHITECTURE df OF serial_add IS
SIGNAL cint : std_logic; Synthesizer will insert latch
BEGIN on internal signals
PROCESS( clk ) It will recognise
BEGIN IF clk’EVENT ... pattern
IF clk’EVENT AND clk = ‘1’ THEN
sum <= a XOR b XOR cint;
cint <= (a AND b) OR (b AND cint) OR (a AND cint );
END IF;
END PROCESS;
cout <= cint;
END ARCHITECTURE df;
Subtraction
 Subtractions are common also
 Observe
 c=a-b
is equivalent to
 c = a + (-b)
=> Adder can be used for subtractions if we can negate
the 2nd operand

 Signed number representation

 Complement representation
 2's complement
2's complement
unsigned 2's
In complement system binary integer complement
 -x is represented by unsigned value 0000 0 0
0001 1 1
M-x, where M is complementation 0010 2 2
constant 0011 3 3
 Example: M=16 0100 4 4
0101 5 5
 -7 => 9 0110 6 6
0111 7 7
1000 8 -8
2's complement: 1001 9 -7
 n-bit number 1010 10 -6
1011 11 -5
 M=2n 1100 12 -4
 Range of representable numbers 1101 13 -3
1110 14 -2
 from -2n-1 to 2n-1-1
1111 15 -1
 Most Significant Bit (MSB)/leftmost
bit represents sign (1: negative, 0:
positive)
Computing 2's complement
 Negation in 2’s complement arithmetic
 Rule:
 Complement each bit
 Add 1 Binary Decimal
0001 1
eg Complement 1110
Add 1 1111 -1

0110 6
Complement 1001
Add 1 1010 -6

Inverse:
1010 -6
Complement 0101
Add 1 0110 6
Due to asymmetric range: from
1000 -8
Complement 0111 -2n-1 to 2n-1-1
Add 1 1000 overflow Overflow detection necessary

Note: Adding 1 can often be avoided using the c in of an adder

Adder / Subtractor
 Using an adder
 Complement each bit using an inverter
 Use the carry in to add 1!
a
b
0 1

add/
subtract

cin
FA FA FA

carry