[attachment=14719]
A Timing-Driven Synthesis Approach of a FastFour-Stage Hybrid Adder in Sum-of-Products
What is a Sum-of-Product (SOP)
An arithmetic Sum-of-Product block (SOP) consists of an arbitrary number of product terms and sum terms.
General form of SOP:
Examples of SOP Blocks
Multiplier {assign z = a * b}
found in Microprocessors
Multiply-Accumulator {assign z = (a * b) + c}
found in Cryptographic Applications
Squarer {assign z = a * a}
found in DSP processors
Addition Tree {assign z = a + b + c + d}
found in ALU, Wireless applications
Generalized SOP {assign z = (a * b) + (c * d)}
found in FIR filters, IIR filters
Synthesis of Sum-of-Products
Synthesis of Sum-of-Product blocks is done in 3 steps (in the order of data-flow)
Creation of Partial Products
Reduction of Partial Products into 2 operands
Computation of Final Sum by adding the 2 operands
Motivation and Problem Statement
SOP blocks are widely used and computationally-intensive
Final adder in SOP consumes about 30% to 40% delay of the SOP block. This paper focuses on the synthesis of an efficient final adder for a SOP expression
Stand-alone adder architectures do not work well in SOP
Stand-alone Adder Architectures
Special Arrival-time Property
The 2 operands of the final adder in a SOP exhibit a peculiar arrival time pattern
As a result, traditional monolithic adders do not work well in SOP
Optimized for equal arrival times
Hence, hybrid adders are required, which exploit this arrival-time pattern
Hence it is critical to synthesize an efficient hybrid adder which is designed specifically for SOP blocks
Proposed 4-Stage Hybrid Adder
Notations
We use the following notations:
The bit-width of SubAdder1 (Ripple) is w1 bits
The bit-width of SubAdder2 (Kogge-Stone) is w2 bits
The bit-width of SubAdder3 (Carry-Select, Brent-Kung) is w3 bits
The bit-width of SubAdder4 (Carry-Select, Brent-Kung) is w4 bits
w1 + w2 + w3 + w4 = n (total width of the hybrid adder)
T(ai) = Time when input signal ai is available
T(Si) = Time when output signal Si (Sumi) is available
T(Ci) = Time when output signal Ci (Carryi) is available
SubAdder1 (Ripple-Carry)
Most area-efficient architecture
Very slow
Timing-efficient if input arrival time is skewed. We use it for a few bits near LSB (which arrive earliest)
Parallel-Prefix Adders (KS, BK)
In a Parallel-Prefix adder, Carry for each bit is computed by an efficient tree-structure (using the Generate and Propagate concept).
For each bit i of the adder, Generate (Gi) indicates whether a carry is generated from that bit
Gi = ai bi
For each bit i of the adder, Propagate (Pi) indicates whether a carry is propagated through that bit
Pi = ai bi
The Generate and Propagate concept is extendable to blocks comprising multiple bits, as we discuss next
Parallel-Prefix Adders (KS, BK)
If two blocks (comprising one or more bits) have the GP value-pairs as (Gleft, Pleft) and (Gright, Pright), then the combined block has the GP values as follows:
Gleft, right = Gleft (Pleft Gright)
Pleft, right = Pleft Pright
The above computation is performed
by a carry-operator or ”o”-operator
Once we obtain carry for each bit,
it is trivial to compute the sum
output of each bit (XOR and NAND)
SubAdder2 (Kogge-Stone)
Brent-Kung (BK)
SubAdder3 & SubAdder4 (Carry-Select)
Large area overhead
Used as a special case, since Cin arrives late
Speed depends on the architecture of two adders
But these adders need not be KS (rather, we use BK)
The arrival times of the inputs of SubAdder3 and SubAdder4 are earlier than those for SubAdder2
Determination of width of SubAdder1
Width of the Ripple adder (SubAdder1)
At every bit (i), compute T(Ci+1) and check if
T(Ci+1) ≤ T(ai+1)
T(Ci+1) ≤ T(bi+1)
If check passes, i = i+1
Else continue checking until 3 consecutive bits fail the check (Hill Climbing)
Return the value i as the Ripple Adder width
Determination of width of SubAdder2
Width of Kogge-Stone Adder (SubAdder2)
The latest arriving signals are part of this adder
Hence keep this adder wide, while ensuring that this does not result in a very narrow Carry-Select adder for SubAdder3 and SubAdder4
We determine the widths with the following equation:
w2 = n – w1 if (n-w1) ≤ 8
w2 = 2p, where p = log2 (n-w1) if (n-w1) > 8
Example: If n=32 and w1=7 then w2=16
Delay of the Hybrid Adder
Determination of widths of SubAdder3 and SubAdder4
Width of the two Carry-Select adders
Initial width configuration
w3 = (n-w1-w2)/2
w4 = (n-w1-w2-w3)
With this initial configuration, estimate delay of the overall hybrid adder (based on the previous slide)
Use an iterative approach to explore in the appropriate direction (similar to Binary Search) and converge on the smallest delay configuration
Experimental Setup
Results
Summary
Hybrid adder consists of 4 SubAdders
SubAdder1 has Ripple-Carry architecture
SubAdder2 has Kogge-Stone architecture
SubAdder3 and SubAdder4 have Carry-Select (based on Brent-Kung) architecture
Widths of all SubAdders are computed based on a timing-driven analysis
On an average, 14.31% faster (with 6.62% area penalty)