臺灣博碩士論文加值系統

乘法相關運算元件(乘法器、乘法累加器、內積計算器、加法器)不管是對於中央處理器或各種在設計上以乘法運算為主之應用導向數位處理系統(數位信號處理器)的效能表現都佔有舉足輕重的地位，而其主要原因在於乘法相關運算元件對於整體電路設計的延遲時間、耗電量及佔用面積大小影響最為顯著，因此本研究將自行開發乘加法相關運算之自動合成軟體。
此合成器可依使用者要求後，經過兩個階段：第一階段為電路合成階段(Pre-Layout Synthesis)，第二階段為佈局合成階段(Layout Generation)，自動產生一般平行乘法器及乘法累加器之Verilog Gate-Level Codes、驗證所需的Test Fixture File及實體佈局檔(CIF file)，然後使用者可直接拿Verilog Code當作Soft IP或實體佈局檔當作Hard IP嵌入SoC中使用。
而本研究將研究重點放在自動合成器的第一階段(Pre-Layout Synthesis)之開發。針對乘法相關運算元件的壓縮樹部份、最終加法器部份以及 Low Power Module，本研究各別提出了新的方案可使得延遲時間、面積及耗電量大小各方面得到最佳化的結果。另外本研究在壓縮單元上也以全客戶開關電路設計了各種不同類型高速省面積之壓縮單元，並可與標準元件庫中的基本元件混用。而且當製程變更時，使用者只需更新自動合成器所需的 Technology File 即可立即產生最新的乘法器或乘法累加器。

In this thesis, we develop an automatic hardware synthesizer for multiplier-based arithmetic functions such as parallel multipliers/multiplier-accumulator/inner-product calculator. The synthesizer is divided into two major phases. In the first phase called pre-layout netlist generation, the synthesizer generates the gate-level verilog codes and the corresponding test fixture file for pre-layout simulation. The second phase, called layout-generation, is to produce the CIF file of final physical layout based on the gate-level netlist generated in the first phase. The thesis focuses on the first phase. The irregular connection of the Wallace tree in the parallel multiplier is optimized in order to reduce the overall delay and power. In addition to the conventional 3:2 couter that is usually included in standard cell library, our synthesizer can select other different compression elements that are full-custom designed using pass-transistor logic. We also propose several methods to partition the final addition part of the parallel multiplier into several regions in order to further reduce the critical path delay and the area cost. Thus, our multiplier generator combines the advantages of three basic design approaches: high-level synthesis, cell-based design and full-custom design along with area and power optimization.

Chapter 1. 導論1
1.1 論文架構1
1.2 研究動機1
Chapter 2. 相關研究3
2.1 反覆式乘法器（Iterative Structure Multiplier）3
2.2 陣列式乘法器（Array Structure Multiplier）4
2.3 樹狀結構乘法器（Tree Structure Multiplier）5
2.3.1 部份乘積（Partial Product Generation）6
2.3.2 壓縮樹（Compression Tree）8
2.3.2.1 壓縮元件種類8
2.3.2.2 壓縮樹種類9
2.3.2.3 連線方法12
2.3.3 最終加法器（Final Addition）13
Chapter 3. 架構設計及方法應用15
3.1 設計簡介15
3.2 部份乘積（Partial Product Generation）17
3.2.1 Modified Signed Extension Algorithm17
3.2.2 乘法相關元件之部份乘積架構20
3.3 壓縮樹（Compression Tree）23
3.3.1 壓縮元件之實作方法23
3.3.2 壓縮樹之架構28
3.3.3 連線方法29
3.3.4 Low-Power Module33
3.3.4.1 Low-Power Module for switch activity reduction34
3.3.4.2 Low-Power Module for driving strength selection of the compressor36
3.4 最終加法器（Final Addition）37
3.4.1 加法器之實作37
3.4.2 Partition Algorithm40
3.4.2.1 傳統分割法（Traditional Partition Method）40
3.4.2.2 傾斜分割法（Sloping Partition Method）41
3.4.2.3 單向分割法（One-way Partition Method）42
3.4.2.4 對稱分割法（Symmetric Partition Method）45
3.4.2.5 雙向分割法（Bidirectional Partition Method）46
3.4.2.6 最佳分割法（Optimized Partition Method）49
3.5 管線化之實作56
Chapter 4. 成果討論59
4.1 壓縮元件之實作59
4.1.1 實作成果59
4.1.2 效能表現61
4.2 加法器65
4.3 乘法器（Multiplier）67
4.4 乘法累加器（Multiplier Accumulator）72
4.5 內積計算器（Inner Product Calculator）73
4.6 管線化元件75
4.7 低功率模組之驗證76
4.8 佈局合成80
Chapter 5. 應用實例與未來展望81
5.1 應用實例81
5.2 未來展望83
5.3 結論86
參考文獻87

[1]Kidambi, S.-S.; El-Guibaly, F. and Antoniou, A., “Area-Efficient Multipliers for Digital Signal Processing Applications,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol. 43, No. 2, pp. 90-95, Feb. 1996.
[2]Kwang, H.-L. and Chong, S.-R., “A Hardware Reduced Multiplier for Low Power Design”, ASICs, 2000. AP-ASIC 2000. Proceedings of the Second IEEE Asia Pacific Conference on, 2000. Page(s): 331 -334
[3]Jou, J.-M., Kuang, S.-R. and Chen, R.-D., “Design of Low-Error Fixed-Width Multipliers for DSP Applications,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol.46, No.6, pp. 836-842, June 1999.
[4]Van, L.-D. , Wang, S.-S. and Feng, W.-S., “Design of the Lower Error Fixed-Width Multiplier and Its Application,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol.47, No.10, pp. 1112-1118, Oct. 2000.
[5]Booth, A.-D., “A Signed Binary Multiplication Technique,” Quartery J. Mechanical Application in Math., vol. 4, part 2, pp. 236-240, 1951.
[6]MacSorley , O.-L., “High Speed Arithmetic in Binary Computers”, Proc. IRE vol. 49, Jan. 1961.
[7]Oklobdzija, V.-G.; Villeger, D., “Improving Multiplier Design by Using Improved Column Compression Tree and Optimized Final Adder in CMOS Technology”, Very Large Scale Integration (VLSI) Systems, IEEE Transactions on , vol. 3, Issue: 2 , pp. 292 -301, June 1995.
[8]Weinberger, A., “4:2 Carry-Save Adder Module,” IBM Technical Disclosure Bull., vol. 23, Jan. 1981.
[9]Song , P. and DE Michelli , G., “Circuit and Architecture Trade-Offs for High Speed Multiplication,” IEEE J. Solid State Circuits, vol. 26, no. 4, Apr. 1991.
[10]Wallace, C.-S., “A Suggestion for a Fast Multiplier,” IEEE Trans. Computers, vol. 13, no.2, pp.14-17, Feb. 1964.
[11]Dadda, L., “Some Schemes for Parallel Multiplier,” Alta Frequenza, vol.34, pp.349-356, Mar. 1965.
[12]Stelling, P.-F.; Martel, C.-U.; Oklobdzija, V.-G.; Ravi, R., “Optimal Circuits for Parallel Multipliers,” Computers, IEEE Transactions on , vol. 47 Issue: 3 , pp.273-285, March 1998.
[13]Oklobdzija, V.-G.; Villeger, D. and Liu, S.-S., “A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach,” Computers, IEEE Transactions on , vol:45 Issue: 3 ,pp.294-306 March 1996.
[14]Hsiao, S.-F.; Jiang, M.-R., “Efficient Synthesiser for Generation of Fast Parallel Multipliers, ” Computers and Digital Techniques, IEE Proceedings- , vol:147 Issue: 1 , pp.49 -52, Jan. 2000.
[15]Hsiao, S.-F, Juang, T.-B., Jan, J. H. and Tasi, M.-Y., “A Multiplier-Based Arithmetic Function Generator for Digital Signal Processing Applications”, Proc. 12thVLSI/CAD Symp., Paper No. B2-7. , Aug. 2001
[16]BRENT, RICHARD P. and KUNG, H.-T., “A Regular Layout for Parallel Adders”, IEEE Transactions on, vol:c-31, no. 3, March 1982.
[17]OPENCORES project Floating Point Unit, http://www.opencores.org/projects/fpu/, Sept. 2000.