45
Chapter 5
Arithmetic at the RT Level
Arithmetic components define the timing and power performance of datapath designs as they are usually forming the critical path and are responsible for a major part of the total power consumption. Several algorithms have been proposed and implemented covering a large range of requirements in terms of area, timing and power. It is important to note, that the most efficient is not always the preferred one, as it may result in a design overkill and increased cost.
In RTL HDL code, arithmetic components are usually inferred by arithmetic operators such (×,+,−) which are implementation independent. Operators are then interpreted to arith-metic primitives by the HDL compiler. The synthesis engine then, based on the constraints set, performs module selection for the arithmetic primitives from a vendor specific propri-etary IP1 component library2. Finally, the technology independent implementations are mapped to the specific technology library3 used.
The purpose of this chapter is to shed light in the steps described above and the handles available to the RTL designer to interfere in this process.
46 Chapter 5. Arithmetic at the RT Level Adder Type Area (gates) Delay (ns) Power (W)
Ripple carry 144 54.27 1.17
Const. width carry skip 156 28.38 1.09
Var. width carry skip 170 21.84 1.26
Carry lookahead 200 17.13 1.71
Carry Select 284 19.56 2.16
Conditional Sum 368 20.05 3.04
Table 5.1: Area, timing and switching performance of 32-bit adders
The input length of 32 bits has been selected as a representative one for most applications.
The authors, have concluded that absolute results from different methods to estimate per-formance may vary, yet they are qualitatively correct. The technology used was an obsolete for today 2um MOSIS4. All adders have been simulated for the same frequency of 10MHz which is 2 times smaller than the frequency of the slowest adder.
The carry-lookahead adder stands out as the fastest adder with an average area and power performance and it is hence a good compromise for high-speed applications. Though at its pure form, the high fanin and fanout requirements make it prohibitive for large adders.
Alternative variations, such as the ripple carry lookahead and the super-block ripple carry lookahead adders, are suitable for average and large widths [43]. The ripple carry adder has the worst performance of all adders and the only reason to be preferred over a carry skip adder is its highly regular structure. For average speed constraints, the variable block width carry skip adder is a fairly good choice. Finally, the carry select and conditional sum adders have a good performance over all widths at high cost, though with high power consumption.
Multi-Operand Addition (>2)
To avoid chaining of adders to calculate the sum of multiple operands, two methods are proposed:
• Adder arrays
• Adder trees
Adder arrays are constructed as a linear arrangement of either carry-propagate (CPA) or carry-save adders (CSA). In the latter case, a carry propagate adder is used to merge the carry and sum vectors. The fastest implementation is achieved by an array of CSAs followed by a fast CPA. The performance of an array of CSAs with an RCA or a fast final CPA is given by formulas 5.1 and 5.2, respectively, where m is the number of operands andn the width.
T =O(m+n) (5.1)
T =O(m+log(n)) (5.2)
Array adders have a more regular structure and lower interconnection, but lower performance when compared to adder trees. The performance of a tree adder is given by equation 5.3.
T =O(log(m) +log(n)) (5.3)
Adder trees are constructed by a tree arrangement of compressors (see figure 5.1left) followed again by a carry propagate adder. In this way carry propagation is only performed once and postponed until after the tree. Effectively, arithmetic is performed in carry-save format
4Metal Oxide Semiconductor Implementation System
5.1 A Review of Arithmetic Components 47
and the final carry-propagate can be perceived as a conversion layer between the carry-save and the standard 2’s complement number representation.
An adder tree made of full-adders is commonly known as a wallace tree. A full-adder is effectively a (3,2) compressor that encodes three input bits to two. A (4,2) compressor and an optimized version of it are illustrated in figure 5.1. A (4,2) compressor achieves a higher compression rate and timing performance for the same area. For this reason it should be preferred for the construction of high fanin trees or the design of larger compressors (e.g.
(8,2)).
compressor (m,k)
a0 … am-1
s0 … sk-1
FA
FA
a0 a1 a2 a3
cin cout
cin
c s
0 1
0 1 cout
c s
a0 a1 a2 a3
Figure 5.1: Implementation of a (4,2) compressor [61]
5.1.2 Multiplication
A multiplier is in practice a multi-operand adder with the partial products as input operands, which are created on the fly by the partial product generator, as depicted in figure 5.2. Thus, an array multiplier consists of a partial product generator and an adder array. Replacing the adder array with a wallace adder tree, a wallace multiplier is created. The Booth encoding can be used to reduce the number of partial products leading to smaller delay, reduced area in the wallace tree and potentially lower power dissipation due to the reduced adder tree.
PARTIAL PRODUCT GENERATION MULTI-OPERAND ADDER CARRY PROPAGATE ADDER
Figure 5.2: Architecture of a parallel multiplier
Similar to the array adders, array multipliers suffer from long delays and are only preferred for low to average performance applications. For average to high performance the wallace multiplier is commonly the best choice, while for ultra-high speed applications the booth
48 Chapter 5. Arithmetic at the RT Level
recoded wallace multiplier is the default choice. Pipelining can then extend the operation speed further with increased latency.
Callaway and Swartzlander in [12] have estimated and simulated the delay and power dissi-pation of three commonly used multipliers:
• modified array multiplier
• Wallace tree multiplier
• Booth recoded wallace tree multiplier
Their results are given for a 2um CMOS technology. The delay is calculated as the number of full-adder cells on the critical path, hence it is technology independent and valid for smaller technologies. The power results are given in milliwatts, so they can only be used for qualitative comparisons. The delay and average power characterization for 8-, 16- and 32-bit multipliers are presented in tables 5.2 and 5.3, respectively.
Mult. Type 8bit 16bit 32bit
Modified array 7 15 31
Wallace 4 9 17
Radix-4 Booth 3 4 6
Table 5.2: Multiplier full-adder delays Mult. Type 8bit 16bit 32bit Modified array 14 47 275
Wallace 13 31 128
Radix-4 Booth 25 44 163
Table 5.3: Multiplier average power consumption (in mW)
Power figures are computed on the basis of the maximum frequency of the slowest multiplier.
An important observation is that for low to average performance requirements, an area optimized design is not necessarily a low power one. Although the wallace multiplier would be a design overkill when timing can be met by the modified array, it attains less power consumption. However, average power consumption is not a representative metric as it does not take into account the real operation conditions. The power-delay product should be used instead [12]; the results are quoted in table 5.4.
Mult. Type 8bit 16bit 32bit Modified array 0.70 4.70 42.6
Wallace 0.65 3.12 19.2 Radix-4 Booth 1.26 4.37 24.5
Table 5.4: Multiplier power-delay product (ns×mW))
The lower the power-delay product, the faster and more efficient the implementation. Based on that, the wallace multiplier represents the best choice when timing is not violated. Oth-erwise, the booth recoded version yields an acceptable performance.
As discussed in the multi-operand addition section, the wallace tree has an irregular layout and longer interconnects than the array adder. This may invalidate the above claims in future technologies, where wiring becomes the limiting factor. This argument is also supported by the foreseen increase importance of leakage power [27], which calls for minimum transistor implementations and may render area-performance trade-offs unacceptable. Pipelining may then be necessary, which is more straight forward in the modified array implementation.