Transcript Block Size Optimization in Carry-Skip Adder

Block Size Optimization in
Carry-Skip Adder
By Lee Hathcock
Carry-Skip Adders
• Carry-Skip a quick and dirty method to
increase speed over ripple-carry
• Small hardware / power cost
• Comparatively large speed increase
• My approach
• Use a program written in C++ to generate
optimal block sizes
O & B’s Method
• First generate number of stages based on
skip delay value
• Computed by the function n <= m + ½ (mT) +
¼ (m^2 T) + 1/8 (1-(-1)^m)T
• n is the number of bits that can be covered
• m is the number of stages
• Goal is to find the lowest m that will generate
enough bits to cover the required bits
O & B’s Method (cont.)
• After m has been found, generate each y(i)
• Use formula:
• min{1+iT, 1+(m+1-i)T}, where i ranges from 1 to
the number of stages
• This generates a block distribution that covers the
required number of bits
O & B’s Method (cont.)
• The previous formula actually generates too
many bits
• Need to reduce, implement bit chopping
algorithm
•
•
•
•
Start at middle value, decrement size
Move to bit to left, decrement.
Move two positions to the right, decrement
Continue until out of range or necessary bits have
been chopped
Timing Analysis
• Have to run though sets of timing triplets to
optimize
• Format (i, j, k)
• j is the internal delay though the block
• i is the skip delay plus the previous stage’s worst i, j
• k is the internal propagation delay of the current
stage plus the previous stage’s worst i, j
Timing Analysis (cont.)
• If the j value is greater than the i value for a
given stage, can optimize
• Match bits by subtracting from the size of
current stage
• Reallocate bit later, where j is much less than i
• Tends to lower total delay in some cases
Basic Skip Circuit (from notes)
Power / Delay Analysis
• Two cases of 4-bit carry-skip
• Used Cadence with ami06 process, existing
MSU libraries for ami06 (voltage = 3.3v)
• First with breakdown of 2,2
• Average power of 127.851 uW
• Fastest time = 1.13x10^-9 s
• Slowest time = 4.14x10^-8 s
Power / Delay Analysis (cont.)
• Second case with 1, 2, 1
• Average power of 88.2793 uW
• Fastest time = 7.19x10^-10 s
• Slowest time = 4.14x10^-10 s
• To be expected, propagated all the way through
• Less skip logic, with case this small, makes it faster
Considerations / Limitations
• Wanted to implement Turrini’s multilevel
skip algorithm
• Very optimal up to 128 bits and 5-6 skip levels
• Lack of different skip values for larger skips
• Skews results a bit, not really realistic
• Partly due to limitations of chosen algorithm
Limitations
• Skip delay has to be an integer value
• Intended to make non-integer values possible,
not done due to choice of algorithm
• Approximation can be done, still will near-optimal
results
Conclusions
• Carry-skip a very effective way to cheaply
speed up adder design
• Optimization of block size can be very
difficult
• Program works fairly well in most cases
• A fully functional version of this program could
be very useful for quick carry-skip optimization
• Only a few changes and fixes will be necessary to
address the issues listed previously