COMP 103

Lecture 14

Adder Design Continued

Reading:
Chapter 11, 577- 586
(skip dynamic implementations)

[All lecture notes are adapted from Mary Jane Irwin, Penn State, which were adapted from Rabaey’s Digital Integrated
Circuits, ©2002, J. Rabaey et al.]

COMP103- L13 Adder Design, Part 2.1

Carry-Skip (Carry-Bypass) Adder

A3 B3 A2 B2 A1 B1 A0 B0

Co,3
FA FA FA FA Ci,0

Co,3
S3 S2 S1 S0

BP = P0 P1 P2 P3 “Block Propagate”

If (P0 & P1 & P2 & P3 = 1) then Co,3 = Ci,0 otherwise

the block itself kills or generates the carry internally

COMP103- L13 Adder Design, Part 2.2

 Carry-Skip Chain Implementation

block carry-out
carry-out
BP
block carry-in

P3 P2 P1 P0

!Cout Cin
G3 G2 G1 G0

BP

COMP103- L13 Adder Design, Part 2.3

4-bit Block Carry-Skip Adder

bits 12 to 15 bits 8 to 11 bits 4 to 7 bits 0 to 3

Setup Setup Setup Setup

Carry Carry Carry Carry

Propagation Propagation Propagation Propagation
Ci,0

Sum Sum Sum Sum

Worst-case delay → carry from bit 0 to bit 15 = carry generated

in bit 0, ripples through bits 1, 2, and 3, skips the middle two
groups (B is the group size in bits), ripples in the last group from
bit 12 to bit 15

Tadd = tsetup + B tcarry + ((N/B) -1) tskip +B tcarry + tsum

COMP103- L13 Adder Design, Part 2.4

 Optimal Block Size and Time
‰ Assuming one stage of ripple (tcarry) has the same delay
as one skip logic stage (tskip) and both are 1
TCSkA = 1 + B + (N/B-1) + B + 1
tsetup ripple in skips ripple in tsum
block 0 last block

= 2B + N/B + 1
‰ So the optimal block size, B, is
dTCSkA/dB = 0 ⇒ √(N/2) = Bopt
‰ And the optimal time is
Optimal TCSkA = 2(√(2N)) + 1
Example: N =32, B=? , T=?
COMP103- L13 Adder Design, Part 2.5

Carry-Skip Adder Extensions

‰ Variable block sizes
z A carry that is generated in, or absorbed by, one of the inner
blocks travels a shorter distance through the skip blocks, so can
have bigger blocks for the inner carries without increasing the
overall delay
Cout Cin

‰ Multiple levels of skip logic

Cout Cin

skip level 1
AND of the
skip level 2 first level skip
signals (BP’s)
COMP103- L13 Adder Design, Part 2.6
 Carry-Skip Adder Comparisons

70

60

50

40 RCA
CSkA
30 B=6 VSkA
B=5
20 B=4
B=2 B=3
10

0
8 bits 16 bits 32 bits 48 bits 64 bits

COMP103- L13 Adder Design, Part 2.7

Carry Select Adder

A’s B’s

4-b Setup
‰ Precompute the carry P’s G’s
out of each block for
both carry_in = 0 and “0” carry propagation 0
carry_in = 1 (can be
done for all blocks in
“1” carry propagation 1
parallel) and then select
the correct one
Cout multiplexer Cin
C’s
Sum generation

COMP103- L13 Adder Design, Part 2.8

S’s
 Carry Select Adder: Critical Path
bits 12 to 15 bits 8 to 1 bits 4 to 7 bits 0 to 3
A’s B’s A’s B’s A’s B’s A’s B’s

Setup Setup Setup Setup

P’s G’s P’s G’s P’s G’s P’s G’s

“0” carry “0” carry “0” carry “0” carry 0

“1” carry “1” carry “1” carry “1” carry 1

mux mux mux mux

Cout Cin
C’s C’s C’s C’s

Sum gen Sum gen Sum gen Sum gen

S’s S’s S’s S’s

COMP103- L13 Adder Design, Part 2.9

Square Root Carry Select Adder

bits 14 to 19 bits 9 to 13 bits 5 to 8 bits 2 to 4 bits 0 to 1
A’s B’s A’s B’s A’s B’s A’s B’s A’s B’s

Setup Setup Setup Setup Setup

P’s G’s P’s G’s P’s G’s P’s G’s P’sG’s

“0” carry “0” carry “0” carry “0” carry “0” carry 0

“1” carry “1” carry “1” carry “1” carry “1” carry 1

Cout mux mux mux mux mux

C
C’s C’s C’s C’s C’s in

Sum gen Sum gen Sum gen Sum gen Sum gen

S’s S’s S’s S’s

S’s

COMP103- L13 Adder Design, Part 2.10

 Parallel Prefix Adders (PPAs)
‰ Define carry operator € on (G,P) signal pairs
(G’’,P’’) (G’,P’)

€
where
G = G’’ ∨ P’’G’
(G,P)
P = P’’P’

z € is associative, i.e.,
[(g’’’,p’’’) € (g’’,p’’)] € (g’,p’) = (g’’’,p’’’) € [(g’’,p’’) € (g’,p’)]

€ €

€ €

COMP103- L13 Adder Design, Part 2.11

PPA General Structure

‰ Given P and G terms for each bit position, computing all
the carries is equal to finding all the prefixes in parallel
(G0,P0) € (G1,P1) € (G2,P2) € … € (GN-2,PN-2) € (GN-1,PN-1)
‰ Since € is associative, we can group them in any order
z but note that it is not commutative (can’t swap the order!)

Pi, Gi logic (1 unit delay) ‰ Measures to consider

z number of € cells
z tree cell depth (time)
Ci parallel prefix logic tree z tree cell area
(1 unit delay per level)
z cell fan-in and fan-out
z max wiring length
z wiring congestion
Si logic (1 unit delay) z delay path variation (glitching,
power implications)
COMP103- L13 Adder Design, Part 2.12
 Brent-Kung PPA

G15 G14 G13 G12 G11 G10 G9 G8 G7 G6 G5 G4 G3 G2 G1 G0

p15 p14 p13 P12 p11 P10 p9 P8 P7 P6 P5 P4 P3 p2 P1 P0 C
in

€ € € € € € € € €
Parallel Prefix Computation

€ € € €

€ €

€ €

€ € €

€ € € € € € €

C16 C15 C14 C13 C12 C11 C10 C9 C8 C7 C6 C5 C4 C3 C2 C1

COMP103- L13 Adder Design, Part 2.13

Kogge-Stone PPF Adder

G15 G14 G13 G12 G11 G10 G9 G8 G7 G6 G5 G4 G3 G2 G1 G0
P15 P14 P13 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1 P0 C
in

€ € € € € € € € € € € € € € € €
Parallel Prefix Computation

€ € € € € € € € € € € € € €
T = log2N

€ € € € € € € € € € € €

€ € € € € € € €

C16 C15 C14 C13 C12 C11 C10 C9 C8 C7 C6 C5 C4 C3 C2 C1

Tadd = tsetup + log2N t€ + tsum

COMP103- L13 Adder Design, Part 2.14
 More Adder Comparisons

70

60

50
RCA
40
CSkA
30 VSkA
KS PPA
20

10

0
8 bits 16 bits 32 bits 48 bits 64 bits

COMP103- L13 Adder Design, Part 2.15

Binary Adder Landscape

synchronous word parallel adders

ripple carry adders (RCA) carry prop min adders

T = O(N), A = O(N)

signed-digit fast carry prop residue adders

adders adders
T = O(1), A = O(N)

Manchester carry parallel conditional carry

carry chain select prefix sum skip
T = O(√N),
T = O(N) T = O(log N) A = O(N)
A = O(N) A = O(N log N)
COMP103- L13 Adder Design, Part 2.16
 Project: Teams of 2-3 people
‰ Circuit design: design and implement the switch level circuit and
follow up with SPICE simulation. Possible circuits: adders,
multipliers, VLIW instruction decoder, a DSP datapath, conversion
from rectangular to polar coordinates, pipelining issues between
synchronous and asynchronous domains, low-power comparators,
on-chip level converters
‰ Memories: a register file design, content-addressable memories
‰ Interconnect issues:
z Look into logical effort and see how it applies to interconnect. Deriving
equations and checking the results against SPICE simulation
z Bus encoding to minimize coupling
z Near speed of light signaling (inductance effects)

‰ Logical effort related software effort: write a C/C++/Java program

that evaluates the delay of a circuit based on logical effort, or that
would allow you to size the gates.

COMP103- L13 Adder Design, Part 2.17

More project ideas

IP-Blocks:
- Encryption chip for the Advanced Encryption Standard (Rijndael algorithm) with self-test upon
power-up
- Public key encryption using Montgomery or Galois Field multiplier
- IP Packet Forwarding Engine (with possibly with Encryption / Decryption)
- USB (Universal Serial Bus) Function Controller for a Microcontroller (e.g. ARM, MIPS, etc.)
- PCI Controller for a Microcontroller
- Ethernet Controller for packet transmission/reception and encapsulation / de capsulation
- Viterbi decoder
- Game processors with rendering acceleration
- Floating point add / subtract / multiplier co-processor
- MPEG compression / decompression
- DSP core with multiple MAC units and VLIW instructions
- JPEG encoder / decoder

- High speed arithmetic coprocessor using advanced logic family such as SR-Domino or CPL logic
for the data path design

COMP103- L13 Adder Design, Part 2.18