(18.204.227.34) 您好!臺灣時間:2021/05/19 08:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:陳坤志
研究生(外文):Kun-Chih Chen
論文名稱:縮減以查表為主之算數處理器中表格面積的實作與分析
論文名稱(外文):Design and Analysis of Table-based Arithmetic Units with Memory Reduction
指導教授:蕭勝夫
指導教授(外文):Shen-Fu Hsiao
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:99
中文關鍵詞:函數近似方法非等份切割法計算機算數多項式逼近法牛頓法
外文關鍵詞:Newton-RaphsonComputer arithmeticpolynomial approximationNon-uniform segmentationFunction approximation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:351
  • 評分評分:
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:0
在數位訊號處理的過程中,經常會使用到特定函數的處理單元,例如:求倒數、取對數等…運算。在傳統上,我們使用以查表法為主的函數運算單元來實做出這些特定功能的硬體。然而,隨著精確的提高,表格面積呈現指數方式的成長且表格面積占硬體總面積的比率也大幅的提高。在本論文中,我們提出了兩種方法來有效降低以查表為主之函數運算單元的表格面積:非等份表格切割以及牛頓法結合等份表格切割法。實驗數據顯示,在大多數的情況中,我們可以獲得超過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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top