臺灣博碩士論文加值系統

在本論文中，我們最主要的研究是針對在3D繪圖中的一些相關硬體設計，做最佳化或創新之設計，以期能增進現今3D繪圖之效能。而所選擇的研究對象，包含下列三個部分：（1）座標轉換器：我們從基本的座標轉換分析開始，根據一些轉換矩陣特徵，發展一個較為簡單的架構，以省去不必要的乘法運算。（2）除法、開根號與乘法器之綜合硬體設計：設計一以2為底的浮點運算單元，並運用over-redundant 的表示方式，將三種運算以一相容硬體加以實踐，並符合IEEE浮點算數標準規格。（3）著色器的硬體設計：針對3D繪圖上之著色方式中品質最佳的Phong Shading 方法設計硬體，以期減少CPU運算上的負擔，並達到3D繪圖速度上的要求。

In this thesis, our goal is to design and optimize new efficient processing cores for 3D graphics. This these is divided into three parts: (I) The datapath design for geometric transformation: First we analysis basic geometric transformation operations used in 3D graphics. Based on the special features of matrix-vector multiplication for geometric transformation, we design a simple architecture that eliminates redundant multiplication. (II) A fused efficient VLSI implementation of radix 2 floating-point arithmetic unit is presented, which is capable of doing division, square root and multiplication. To make the quotient/ root digit's selection function simple, over-redundant radix 2 representation is used. The arithmetic unit complies with IEEE's binary floating-point standard. (III) The datapath design for 3D graphic shading. We introduce some shading methods that are usually used for 3D graphics. A VLSI architecture is designed for Phong shading, which has the best performance for 3D graphics shading. Our targets for this architecture are to decrease the computation of CPU and can arrive the speed's requires for 3D graphics.

Contents
Chinese Abstracti
English Abstractii
Acknowledgementiii
Contentsiv
List of Tablesvii
List of Figuresviii
Chapter 1 Introduction1
1.1 Concept of 3D Computer Graphic1
1.2 Introduction of OpenGL 2
1.3 Design Consideration of 3D Graphic Chip5
1.3.1 Datapath Design for Geometric Transformations7
1.3.2 A shared Unit for Division, Square Root and Multiplication8
1.3.3 Shading Methods in 3D Graphics9
1.4 Organization of the Thesis10
Chapter 2 Geometric Transformation11
2.1 Introduction11
2.2 Object transformations14
2.3.1 Translation14
2.3.2 Rotation15
2.3.3 Scaling16
2.3.4 Shearing17
2.3 Homogeneous coordinate and matrix representation18
2.4 Concatenation of Transformations20
2.5 Projections21
2.5.1 Orthographic projection22
2.5.2 Perspective Projections24
2.6 Manipulating the Matrix Stacks27
2.7 Implementation of Transformations in OpenGL28
Chapter 3 Datapath Design for Geometric Transformations31
3.1 Introduction31
3.2 Floating Point Definition31
3.3 Fused Floating Point Multiply-Add Unit33
3.4 FMA Used in Geometric Transformation34
3.5 Analysis of the Geometric Transformation Matrices and MAC Unit in Graphics
Pipeline35
3.6 The Modified Architecture38
3.6.1 Parallel Exponent Computation38
3.6.1.1 Zeros and Ones Detector39
3.6.1.2 Common Exponent Detector40
3.6.1.3 Finding the Negligible Exponent Sums43
3.6.1.4 Complete Architecture of Parallel Exponent Computation43
3.6.2 Mantissa MAC Input Selector44
3.6.2.1 The Shift Part45
3.6.2.2 The Non-trivial Part46
3.6.3 The Mantissa MAC49
3.6.4 The Final Mantissa Adder and Normalizer51
3.6.4.1 The Leading-zero Anticipator52
3.6.4.2 The Leading-zero Counter54
3.7 Overall Architecture and Performance57
Chapter 4 A Combined Floating Point Radix-2 Arithmetic Algorithm and Architecture61
4.1 Introduction61
4.2 The Unified Division/Square Root/ Multiplication Algorithm63
4.2.1 The Division Algorithm63
4.2.1.1 Range of the Partial Remainder63
4.2.1.2 Quotient Selection Function65
4.2.1.3 The Division Recursion67
4.2.2 The Square Root Algorithm68
4.2.2.1 Range of the Partial Remainder68
4.2.2.2 Selection Function for Square Root69
4.2.2.3 The Square Root Recursion72
4.2.3 The MSD-First Multiplication Algorithm72
4.2.3.1 The Recursive Relationship73
4.2.3.2 Generation of Product Digits74
4.3 The Modified On-the-fly Converter75
4.4 The Hardware Design Implementation78
4.4.1 Radix-2 Redundant Arithmetic78
4.4.2 Carry Free Adder78
4.4.3 Digit Selection Architecture80
4.4.4 The Modified On-the-fly Converter82
4.4.5 PRD Generation84
4.4.6 Product Digit Decoder87
4.5 The Overall Architecture88
Chapter 5 Algorithm and Hardware design for Phong Shading91
5.1 Modeling of Lighting91
5.2 Surface-Shading Methods93
5.2.1 Flat Shading94
5.2.2 Gouraud Shading94
5.3 Phong Shading97
5.3.1 The Conventional Phong Shading97
5.3.2 Fast Phong Shading by Using Taylor's Series Approximation99
5.4 The Proposed Algorithm for Phong Shading102
5.4.1 Using the Proposed Shared Architecture105
5.4.2 Newton-Raphson Method [35]106
5.4.3 CCM Algorithm107
5.4.4 Log Space Computation108
5.5 Datapath Design for Modified Phong Shading110
5.5.1 The Fn(x) and Fd(x) Evaluator111
5.5.2 The Log Stage111
5.5.3 Multiplier 1114
5.5.4 The Anti-log Stage114
5.5.5 Multiplier 2115
5.6 The Total Hardware Implementation115
Chapter 6 Conclusion118
Reference120
Appendix A124
Appendix B128
Autobiography136

Reference
[1] J. D. Foley et al., "Computer Graphics", Addison-Wesley, 1990
[2] Mason Woo, Jackie Neider, and Tom Davis, "OpenGL Programming Guide, The Official Guide to Learning OpenGL, Version 1.1", Addison-Wesley Developers Press, 1997.
[3] OpenGL ARB, "OpenGL Programming Guide" , Addison-Wesley, Jan. 1995.
[4] Edward Angel, "Interactive Computer Graphics: A top-down approach with OpenGL", Addison-Wesley Longman, Inc., 1997.
[5] J. D. Foley et al. "Introduction to Computer Graphics", Addison-Wesley, 1994.
[6] D. Hearn and M. P, Baker, "Computer Graphics", Prentice Hall, 1986.
[7] R. D. Andreev, " Graphics System: Architecture and Realization", North-Holland, 1993.
[8] OpenGL ARB, "OpenGL Reference Manual: The official Reference Document for OpenGL, Release 1", Addison-Wesley, Jan. 1995.
[9] "Graphics SPC1500POB", Data sheet, S-MOS Systems, December 1994.
[10] X. Huang, W. Liu, and B. Wei, "A High-performance CMOS Redundant Binary Multiplication-and-Accumulate (MAC) Unit", IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Application, Vol. 41, No. 1, Jan. 1994, pp. 33-39.
[11] F. Arakawa, O. Nishii, K. Uchiyama, N. Nakagawa. "SH4 RISC Multimedia Microprocessor", IEEE Micro. Vol. 18, Issue. 2, Mar. 1998, pp.26-34.
[12] S. H. Hu, "Audio Equalization and Graphic Preprocessing for Personal VR Environment", Institute of Electronics, National Chiao Tung University, 1998.
[13] J. Neider, T. Davis, M. Woo, "OpenGL Programming Guide", Addison-Wesley, 1993.
[14] K. P. Acken, M. J. Irwin, R. M. Owens, A. K. Garga, "Architectural Optimizations for a Floating Point Multiply-Accumulate Unit in a Graphics Pipeline", IEEE Compu. Soc. Press, 1996, pp.65-71.
[15] H. Suzuki, H. Morinaka, H. Makino, Y. Nakase, K.Mashiko, "Leading-Zero Anticipatory Logic for High-Speed Floating Point Addition", IEEE Journal of Solid-state Circuit, Vol. 31, No. 8, Aug. 1996, pp. 1157-1164.
[16] V. G. Oklobdzija, "An Algorithmic and Novel Design of a Leading Zero Dector Circuit: Comparison with Logic Synthesis", IEEE Trans. On VLSI System, Vol. 2, No.1, Mar. 1994, pp. 124-128.
[17] G. W. Bewick, "Fast Multiplication: Algorithm and Implementation", Dissertation for the Degree of Doctor in Philsophy, February 1994.
[18] S. M. Sait, A. A. Farooqui, and G. F. Bechoff, "A Novel Technique for Fast Multiplication", IEEE, 1995.
[19] M. D. Ercegovac and T. Lang, "Division and Square Root", Norwell, Massachusetts 02061: Kluwer Academic Publishers, 1994.
[20] S. Majerski, "Square-Rooting Algorithms for high-speed digital circuits", IEEE Trans. on Computers, vol. 34, 1985, pp. 724-733.
[21] C. H. Ten, " Compatible Hardware for Arithmetic Unit Design", Institute of Electronics, National Chiao Tung University, 1991.
[22] L. Ciminiera and A. Serra, "Efficient Serial-Parallel Arrays for Multiplication and Addition", Processings of the 7th Symposium on Computer Arithmetic, 1985, pp.28-35.
[23] M. D. Ercegovac and T. Lang, "On-the-fly Conversion of Redundant into Conventional Representations", IEEE Trans. on Computers, Vol. C-36, July 1987, pp.895-897.
[24] H. R. Srinivas and K. K. Parhi, "A Floating Point Radix 2 Shared Division/Square Root Chip", in Proc. of IEEE International Conference on Computer Design: VLSI in Computers and Processors, (Austin, TX), October 1995, pp. 472-478.
[25] A. Vandemeulebroecke, E. Vanzieleghem T. denayer, and P. G. A. Jespers, "A New Carry-free Division Algorithm and its Application to a Single-Chip 1024-b RSA Processor", IEEE Journal of solid state circuits, vol. 25, June 1990, pp. 748-756.
[26] H. R. Srinivas and K. K. Parhi, "High-Speed VLSI Arithmetic Processors Using Hybrid Number System", Joural of VLSI Signal Processing, vol. 4, April 1992, pp. 177-198.
[27] P. Montuschi and L. Ciminiera, "Over-redundant Digit Sets and the Design of Digit-by-Digit Division Unit.", IEEE Trans. on Computers, vol. 43, March 1994, pp. 269-277.
[28] A. Watt, ?D Computer Graphics", 2nd Edition, Addison Weley, 1993.
[29] H. Gouraud, "Continuous Shading of Curved Surfaces", IEEE Trans. On Comp., C-20(6), June. 1971, pp.623-628.
[30] B. T. Phong. " Illumination for computer generated images", Comm. Of the ACM., Vol. 18, No. 6, June 1975, pp. 311-317.
[31] G. Bishop and D. M. Weimar, " Fast Phong Shading", Computer Graphics, Vol. 20 1986, pp. 255-262.
[32] H. C. Sin, J. A. Lee, and L. S. Kim, "VLSI Implementation of Phong Shader in 3D Graphics", Proceedings of the 1998 IEEE International Symposium on Circuits and Systems, 1998. ISCAS '98. Vol. 2, 1998, pp. 417 -420.
[33] C. L. Chen, B. S. Liang, and C. W. Jen, "A Low-cost Raster Engine for Video Game, Multimedia PC and Iteractive TV", IEEE Trans. On Consumer Electronics, Vol. 41, No. 3, August. 1995, pp. 724-730.
[34] D. Hearn and M. P. Baker, "Computer Graphics", Prentice Hall, 1994, pp. 500-504.
[35] N. R. Scott, "Computer Number Systems and Arithmetic", Prentice Hall, Englewood Cliffs, N.J, 1985.
[36] D. Cantor, G. Estrin, and R. Turn, "Logarithm and Exponential Function Evaluation in A Variable Structure Digital Computer", TRE Trans, vol. EC-11. 1962, pp. 155-164.
[37] T. C. Chen, "Automatic Computation of Exponentials, Logarithms, Ratios and Square", IBM Journal Res. And Dev., July 1972, pp. 380-388.
[38] Y. D. Hou, "Unified Design of An Efficient CORDIC/CCM Processor", Institute of Electronics, National Chiao Tung University, 1993.
[39] B. C. Shih, Y. H. Yeh, C. Y. Lee, "A 40M Pixels/s 3D Graphics Shading Processor", VLSI 9th Design/CAD Symposium, 1998, pp. 261-264.
[40] E. Hokenek, R. K. Montoye, P. W. Cook, "Second Generation RISC Floating Point with Multiply-Add Fused", IEEE Journal of Solid-state Circuits, vol. 25, No 5, Oct. 1990.
[41] Edward Angel, "Interactive Computer Graphics: A Top-down Approch with OpenGL", Addison-Wesley Longman, Inc., 1997.
[42] M. R. D. Rodrigues, J. H. P. Zurawski, and J. N. Gosling, "Hardware Evaluation of Mathematical Functions", IEEE, Proc., vol. 128, no. 4, July 1981, pp. 155-164.