We demonstrate faster and energy-efficient column compression multiplication with very small area overheads by using a combination of two techniques: partition of the partial products into two parts for independent parallel column compression and acceleration of the final addition using new hybrid adder structures proposed here. Based on the proposed techniques, 8-b, 16-b, 32-b, and 64-b Wallace (W), Dadda (D), and HPM (H) reduction tree based Baugh-Wooley multipliers are developed and compared with the regular W, D, H based Baugh-Wooley multipliers. The performances of the proposed multipliers are analyzed by evaluating the delay, area, and power, with 65？nm process technologies on interconnect and layout using industry standard design and layout tools. The result analysis shows that the 64-bit proposed multipliers are as much as 29%, 27%, and 21% faster than the regular W, D, H based Baugh-Wooley multipliers, respectively, with a maximum of only 2.4% power overhead. Also, the power-delay products (energy consumption) of the proposed 16-b, 32-b, and 64-b multipliers are significantly lower than those of the regular Baugh-Wooley multiplier. Applicability of the proposed techniques to the Booth-Encoded multipliers is also discussed. 1. Introduction High-speed multiplication is a primary requirement of high-performance digital systems. In recent trends, the column compression multipliers are popular for high-speed computations due to their higher speeds [1, 2]. The first column compression multiplier was introduced by Wallace in 1964 [3]. He reduced the partial product of rows by grouping into sets of three-row set and two-row set using (3,2) counter and (2,2)？？counter, respectively. In 1965, Dadda altered the approach of Wallace by starting with the exact placement of the (3,2) counter and (2,2) counter in the maximum critical path delay of the multiplier [4]. Three-dimensional minimization- (TDM-) based column compression approach was proposed in 1996 to perform fast multiplication [5]. Since the 2000s, a closer reconsideration of Wallace and Dadda multipliers has been done and proved that the Dadda multiplier is slightly faster than the Wallace multiplier and the hardware required for Dadda multiplier is lesser than the Wallace multiplier [6, 7]. The HPM-based column compression was developed in 2006, and it has standard layout structure than Eriksson et al.’s multiplier [8]. The detailed case for HPM-based Baugh-Wooley multiplier against the Booth-Encoded multipliers has been described in [9]. In this work, we implement the proposed techniques with
References
[1]
K. C. Bickerstaff, Optimization of Column Compression Multipliers [Ph.D. thesis], Department of Electrical and Computer Engineering, University of Texas at Austin, Austin, Tex, USA, 2007.
[2]
B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, New York, NY, USA, 2nd edition, 2010.
[3]
C. S. Wallace, “A suggestion for a fast multiplier,” IEEE Transactions on Electronic Computers, vol. EC-13, pp. 14–17, 1964.
[4]
L. Dadda, “Some schemes for parallel multipliers,” Alta Frequenza, vol. 34, pp. 349–356, 1965.
[5]
V. G. Oklobdzija, D. Villeger, and S. S. Liu, “A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach,” IEEE Transactions on Computers, vol. 45, no. 3, pp. 294–306, 1996.
[6]
K. C. Bickerstaff, E. E. Swartzlander, and M. J. Schulte, “Analysis of column compression multipliers,” in Proceedings of the 15th IEEE Symposium on Computer Arithmetic, pp. 33–39, June 2001.
[7]
W. J. Townsend, E. E. Swartzlander, and J. A. Abraham, “A comparison of Dadda and Wallace multiplier delays,” in Advanced Signal Processing Algorithms, Architectures, and Implementations XIII, vol. 5205 of Proceedings of the SPIE, pp. 552–560, August 2003.
[8]
H. Eriksson, P. Larsson-Edefors, M. Sheeran, M. Sj？lander, D. Johansson, and M. Sch？lin, “Multiplier reduction tree with logarithmic logic depth and regular connectivity,” in Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 4–8, May 2006.
[9]
M. Sj？lander and P. Larsson-Edefors, “The case for HPM based Baugh-Wooley multipliers,” Tech. Rep. 08-8, Chalmers University of Technology, Goteborg, Sweden, 2008.
[10]
C. R. Baugh and B. A. Wooley, “A two’s complement parallel array multiplication algorithm,” IEEE Transactions on Computers, vol. 22, pp. 1045–1047, 1973.
[11]
M. Sj？lander and P. Larsson-Edefors, “High-speed and low-power multipliers using the Baugh-Wooley algorithm and HPM reduction tree,” in Proceedings of the 15th IEEE International Conference on Electronics, Circuits and Systems (ICECS '08), pp. 33–36, September 2008.
[12]
V. G. Oklobdzija and D. Villeger, “Improving multiplier design by using improved column compression tree and optimized final adder in CMOS technology,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 3, no. 2, pp. 292–301, 1995.
[13]
P. F. Stelling and V. G. Oklobdzija, “Design strategies for optimal hybrid final adders in a parallel multiplier,” Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, vol. 14, no. 3, pp. 321–331, 1996.
[14]
B. Ramkumar, H. M. Kittur, and P. M. Kannan, “ASIC implementation of modified faster carry save adder,” European Journal of Scientific Research, vol. 42, no. 1, pp. 53–58, 2010.
[15]
B. Ramkumar and H. M. Kittur, “Low-power and area-efficient carry select adder,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 20, no. 2, pp. 371–375, 2012.
[16]
B. Ramkumar and H. M. Kittur, “Optimal final carry propagate adder design for parallel multipliers,” http://arxiv.org/abs/1110.3584.
[17]
Y. He, C. H. Chang, and J. Gu, “An area efficient 64-bit square root carry-select adder for low power applications,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '05), vol. 4, pp. 4082–4085, May 2005.
[18]
M. Sj？lander and P. Larsson-Edefors, “High-speed and low-power multipliers using the Baugh-Wooley algorithm and HPM reduction tree,” in Proceedings of the 15th IEEE International Conference on Electronics, Circuits and Systems (ICECS '08), pp. 33–36, September 2008.
[19]
S. R. Kuang, J. P. Wang, and C. Y. Guo, “Modified booth multipliers with a regular partial product array,” IEEE Transactions on Circuits and Systems II, vol. 56, no. 5, pp. 404–408, 2009.
