臺灣博碩士論文加值系統

在這篇論文中, 我們提出了兩個在高效能布斯加密法瓦利氏樹乘法器(Booth-Encoded Wallace-Tree Multiplier)中進位選擇加法器(carry-select-adder)分配演算法, 一為branch-and-bound方法, 一為heuristic方法; 由於資料進入進位選擇加法器時間的不同, 我們將進位選擇加法器分為若干個加法器區塊, 以對乘法器的效能作最佳化. 我們使用我們所做的乘法器產生器產生了15個乘法器, 從實驗數據中可得知, 在不到1%的面積增加下, 可以有約9.2%的效能進步.

In this thesis, we present two carry-select adder partitioning algorithms for high-performance Booth-encoded Wallace-tree multipliers. By taking various data arrival times into account, we propose a branch-and-bound algorithm and a heuristic algorithm to partition an n-bit carry-select adder into a number of adder blocks such that the overall delay of the design is minimized. The experimental results show that our proposed algorithm can achieve on an average 9.1% delay reduction with less than 1% of area overhead on 15 multipliers ranges from 16X16-bit to 64X64-bit.

Contents
Abstract
Contents
List of Figures
List of Tables
Chapter 1 : Introduction
Chapter 2 : Related Work
Chapter 3 : Overview of the Booth-Encoded Wallace Tree Multiplier
3.1 Multiplier Architecture
3.2 Partial Product Generator
3.2.1 A Modified Radix-4 Booth’s Algorithm
3.2.2 Sign-Pre-Calculation
3.3 The Partial-Product-Reduction Tree Structure
3.4 Carry-Select Adder
Chapter 4 : Problem Description
4.1 Delay Effect on Carry-Select Adder Partitioning
4.2 Problem Definition
Chapter 5 : The Carry-Select Adder Partitioning Algorithm
5.1 Branch-and-Bound Method
5.2 Heuristic Algorithm
Chapter 6 : Implementation and Experimental Results
6.1 Experiments on Branch-and-Bound Algorithm v.s. Heuristic Algorithm
6.2 Experiments on Our Proposed Heuristic Algorithm v.s. the CSA Partitioning Method Proposed by [6]
6.3 Experiments on the Multipliers Generated by Our Multiplier Generator
Chapter 7 : Conclusions and Future Work
References

[1] Junhyung Um, Taewhan Kim, C. L. Liu, “Optimal Allocation of Carry-Save-Adders in Arithmetic Optimization”, ICCAD, pp.410~413 1999.
[2] Junhyung Um, Taewhan Kim, C. L. Liu, “A Fine-Grained Arithmetic Optimization Technique for High-Performance/Low-Power Data Path Synthesis”, DAC, P92-P97, 2000.
[3] Oklobdzija, V.G.; Villeger, D.; Liu, S.S., “A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach” IEEE Transactions on Computers, Vol. 45 3, March 1996 , P294-P306.
[4] Martel, C., Oklobdzija, V., Ravi, R., Stelling, P.F., ”Design strategies for optimal multiplier circuits”, Proceedings of the 12th Symposium on Computer Arithmetic, 1996, P42-P49.
[5] Meier, P.C.H.; Rutenbar, R.A.; Carley, L.R., “Exploring multiplier architecture and layout for low power”, Proceedings of the IEEE on Custom Integrated Circuits Conference, pp.513-516, 1996.
[6] Jalil Fadavi-Ardekani, Senior Member, IEEE, ”M*N Booth Encoded Multiplier Generator Using Optimized Wallace Trees” IEEE Transaction on VLSI System, Vol. 12, June 1993, P120-P125.
[7] Stelling, P.F., Oklobdzija, V., “Design strategies for the final adder in a parallel multiplier” Conference Record of the 29th Asilomar Conference on Signals, Systems and Computers, Vol. 1, 1996, P591-P595.
[8] Stelling, P.F., Oklobdzija, V.G., “Implementing multiply-accumulate operation in multiplication time”, 13th IEEE Symposium on Computer Arithmetic, 1997, P99-P106.
[9] Stelling, P.F., Martel, C.U., Oklobdzija, V.G., Ravi, R., “Optimal circuits for parallel multipliers”, IEEE Transactions on Computers, Vol. 47 3, March 1998, P273-P285.
[10] Wen-Chang Yeh; Chein-Wei Jen , “High-speed Booth encoded parallel multiplier design” IEEE Transactions on Computers, Vol. 49 7, P692 -P701, July 2000.
[11] Kolagotla, R.K., Srinivas, H.R., Burns, G.F., “VLSI implementation of a 200-MHz 16/spl times/16 left-to-right carry-free multiplier in 0.35 /spl mu/m CMOS technology for next-generation DSPs”, Proceedings of the IEEE Custom Integrated Circuits Conference, 1997, P469-P472 vol. 1, No. 2, June 1993.
[12] C. S. Wallace “A suggestion for a Fast Multiplier”, IEEE Transaction on Computers, Vol. EC-13, P14-P17, 1964.
[13] A.D. Booth, “A Signed Binary Multiplication Technique”, Quart. J. Math., vol. IV, pp. 2, 1951.
[14] O.L MacSorley, “High-Speed Arithmetic in Binary Computers”, IRE Proc., vol. 49, pp.67-91, Jan. 1961.
[15] Smith, Michael J. S., “Application-Specific Integrated Circuits”, Addision-Wesley, Chapter 2.
[16] Synopsys Design Compiler Reference Manual v1999.10”, Synopsys, 1999.
[17] IC layout Command Reference Manual, Avanti 1999.4