臺灣博碩士論文加值系統

在數位訊號處理的過程中，經常會使用到特定函數的處理單元，例如：求倒數、取對數等…運算。在傳統上，我們使用以查表法為主的函數運算單元來實做出這些特定功能的硬體。然而，隨著精確的提高，表格面積呈現指數方式的成長且表格面積占硬體總面積的比率也大幅的提高。在本論文中，我們提出了兩種方法來有效降低以查表為主之函數運算單元的表格面積：非等份表格切割以及牛頓法結合等份表格切割法。實驗數據顯示，在大多數的情況中，我們可以獲得超過50%的表格面積縮減比率。

In many digital signal processing applications, we often need some special function units which can compute complicated arithmetic functions such as reciprocal and logarithm. Conventionally, table-based arithmetic design strategy uses lookup tables to implement these kinds of function units. However, the table size will increase exponentially with respect to the required precision. In this thesis, we propose two methods to reduce the table size: bottom-up non-uniform segmentation and the approach which merges uniform piecewise interpolation and Newton-Raphson method. Experimental results show that we obtain significant table sizes reduction in most cases.

Chinese Abstract ……………………………………………………………………...i
Abstract ……………………………………………………………………………....ii
List of Figures ................................................................................................................v
List of Tables................................................................................................................vii
Chapter 1 Introduction................................................................................................1
1.1 Motivation..................................................................................................1
1.2 Thesis Organization ...................................................................................2
Chapter 2 Backgrounds and Relevant Research.........................................................3
2.1 Table-based Arithmetic Categories ............................................................3
2.2 Table-addition Methods .............................................................................5
2.2.1 Bipartite Methods...........................................................................6
2.2.2 Multipartite Methods .....................................................................9
2.3 Table-polynomial Methods ......................................................................12
2.3.1 Uniform Piecewise Methods........................................................13
2.3.2 Non-uniform Piecewise Methods ................................................19
2.4 Summary ..................................................................................................27
Chapter 3 Bit Width Optimization in Operators.......................................................29
3.1 Truncated Multipliers...............................................................................29
3.2 Squarers....................................................................................................32
Chapter 4 Bottom-up Non-uniform Segmentation Approach...................................36
4.1 Overview..................................................................................................36
4.2 Architecture Design .................................................................................40
4.3 Error Analysis and Bit-Optimization .............................................................44
4.3.1 Degree-1 Interpolation ........................................................................45
4.3.2 Degree-2 Interpolation ........................................................................48
Chapter 5 Newton-Raphson with Piecewise Polynomial Interpolation ...................51
5.1 Approach Overview.................................................................................51
5.2 Architecture Design .................................................................................53
5.3 Bit-Optimization ......................................................................................55
Chapter 6 Experiential Results and Comparison......................................................57
6.1 Algorithm Comparison in Non-uniform Segmentation ...........................57
6.2 Estimation of Area and Delay..................................................................60
6.2.1 Estimation Model Design ............................................................61
6.2.2 Estimation Results Comparison...................................................64
6.3 Real Synthesis Results .............................................................................73
6.4 Newton-Raphson Approach Results ........................................................82
7 Conclusions and Future Works ............................................................................83
7.3 Conclusions..............................................................................................83
7.4 Future Works............................................................................................84
Reference .....................................................................................................................85

[1] J.M. Muller, “A Few Results on Table-Based Methods,” Reliable Computing, Vol. 5, No. 3, pp. 279-288, Aug. 1999.
[2] M.J. Schulte and J.E. Stine, “Symmetric Bipartite Tables for Accurate Function Approximation,” Proc. 13th Symp. Computer Arithmetic, pp. 175-183, 1997.
[3] J.E. Stine and M.J. Schulte, “The Symmetric Table Addition Method for Accurate Function Approximation,” J. VLSI Signal Processing Systems for Signal Image and Video Technology, vol. 21, pp. 167-177, 1999.
[4] M.J. Stine and J.E. Stine, “Approximating Elementary Functions with Symmetric Bipartite Tables,” IEEE Transactions on Computers, vol. 48, no. 8, pp. 842-847, Aug. 1999.
[5] F-d Dinechin and A. Tisserand, “Some Improvements on Multipartite Table Methods,” Proc. 15th IEEE Symp. Computer Arithmetic, pp. 128-135, 2001.
[6] F-d Dinechin and A. Tisserand, “Multipartite Table Method,” IEEE Transactions on Computers, vol. 54, no. 3, pp. 319-330, Mar. 2005.
[7] T.B. Jung, S.F. Hsiao, and M.J. Tsai, “Para-CORDIC: Parallel CORDIC rotation algorithm,” IEEE Transactions on Circuits and System-I, vol. 51, no. 8, pp. 1515-1524, Aug. 2004.
[8] E. Antelo and J. Villalba, “Low Latency Pipelined Circular CORDIC,” Proc. 17th IEEE Symp. Computer Arithmetic, pp. 280-287, 2005.
[9] E. Antelo, J. Villalba, and E.L. Zapata, “Low-Latency Pipelined 2D and 3D CORDIC Processors,” IEEE Transactions on Computers, vol. 57, no. 3, pp.404-417, Mar. 2008.
[10] M.J. Schulte and E.E. Swartzlander, “Hardware Designs for Exactly Rounded Elementary Functions,” IEEE Transactions on Computers, vol. 43, no. 8, Aug. 1994.
[11] J. Cao, B. Wei, and J. Cheng, “High-Performance Architectures for Elementary Function Generation,” Proc. 15th IEEE Symp. Computer Arithmetic, pp. 136-144, 2001.
[12] J.A. Pineiro, J.D. Bruguera, and J.M. Muller, “Faithful Powering Computation Using Table Look-Up and Fused Accumulation Tree,” Proc. IEEE 15th Symp. Computer Arithmetic, pp. 40-47, 2001.
[13] J.M. Muller, “Partially rounded Small-Order Approximations for Accurate, Hardware-Oriented, Table-Based Methods,” Proc. IEEE 16th Symp. Computer Arithmetic, pp. 1-8, 2003.
[14] E.G. Walters-III and M.J. Schulte, “Efficient Function Approximation Using Truncated Multipliers and Squarers,” Proc. IEEE 17th Symp. Computer Arithmetic, 2005.
[15] J.A. Pineiro, J.M. Muller, and J.D. Bruguera, “High-Speed Function Approximation Using a Minimax Quadratic Interpolator,” IEEE Transactions on Computers, vol. 54, no. 3, pp. 304-318, Mar. 2005.
[16] D-U Lee, W. Luk, J. Villasenor, and P.Y.K. Cheung, “Hierarchical Segmentation Schemes for Function Evaluation,” Proc. IEEE Conf. Field-Programmable Technology, pp. 92-99, Dec. 2003.
[17] D-U Lee, W. Luk, J. Villasenor, and P.Y.K. Cheung, “Non-uniform Segmentation for Hardware Function Evaluation,” Proc. 11th Int’l Conf. Field Proframmable Logic and Applications, pp. 796-807, Sept. 2003.
[18] T. Sasao, S. Nagayama, and J.T. Butler, “Numerical Function Generators Using LUT Cascades,” IEEE Transactions on Computers, vol. 56, no. 6, June 2007.
[19] D-U Lee, R.C.C Cheung, W. Luk, and J.D. Villasenor, “Hardware Implementation Trad-Offs of Polynomial Approximations and Interpolations,” IEEE Transactions on Computers, vol. 57, no. 5, May 2008.
[20] D-U Lee, A.A. Gaffar, O. Mencer, and W. Luk, “Adaptive Range Reduction for Hardware Function Evaluation,” Proc. IEEE Int’l Conf. Field-Programmable Technology, pp.169-176, 2004.
[21] D-U Lee, A.A. Gaffar, O. Mencer, and W. Luk, “Optimizing Hardware Function Evaluation,” IEEE Transactions on Computers, vol. 54, no. 12, Dec. 2005.
[22] Behroox Parhami, Computer Arithmetic (Algorithms and Hardware Designs), Oxford University Press, 2000
[23] L-D. Van and C.C. Yang, “Generalized Low-Error Area-Efficient Fixed-Width Multipliers,” IEEE Transactions on Circuits and System-I, vol. 52m no. 8, Aug. 2005.
[24] K.C. Bickerstaff, M.J. Schulte, and E.E. Swartzlander,Jr., “Reduced Area Multipliers,” Proceedings 1993 Application Specific Array Processors, pp. 478-489, 1993.