臺灣博碩士論文加值系統

本篇論文分析3D圖學與虛擬實境的運算需求。依照這些運算需求，我們亦針對多媒體硬體處理器的計算能力進行分析，發現現存媒體器在支援3D圖學及虛擬實境應用仍有不足現象。為了符合3D多媒體的運算需求，我們乃進一步提出一個具有高度集積特性的媒體處理器架構。這個媒體處理器乃基於NSC98微處理器架構修正而來。所以它擁有一個RISC core及多個特殊功能單元。其中用來支援3D運算的主力在於多媒體運算單元及CORDIC運算單元。前者和Intel MMX相容，但另外新增五個指令以提高3D運算效能。CORDIC單元用來執行需要長時間運算的指令，如三角函數的計算等。
在CORDIC單元的電路設計上，我們亦提出若干新技巧，使其效能及成本皆可達到完善。首先我們修正double rotation CORDIC演算法，使其能夠在360度全角度範圍計算三角函數。其次為了增進電路效能與降低電路成本，我們使用了封包方式的輸出與輸入方式。另外為了降低數字表示法轉換的時間，我們使用線上(on-line)方式轉換數字表示法。
所有電路設計都以Verilog語言寫成，並且使用COMPASS 0.35μm元件庫和Synopsys設計輔助工具來合成電路，到目前為止，我們已完成了邏輯電路的合成與時序的模擬，並將送國科會CIC製作。

In this thesis, the computation requirements of 3D graphics and virtual reality are analyzed. According to the computation requirements, some existing architectures of multimedia hardware, for example, the Microsoft Talisman and NSC98 microprocessor, are compared. Obviously, their capability can not sufficiently support 3D graphics computations. To satisfy the computation requirements of 3D multimedia applications, we propose an architecture of highly integrated media processor which is extended from the micro-architecture of NSC98. This architecture consists of a RISC core and some special functional units. In this architecture, most multimedia operations are performed on a Multimedia Functional Unit (MFU), which is Intel MMX compatible. But, to speed up the performance of multimedia computation, we develop another five new instructions to be included into the Intel MMX compatible instruction set. Besides, a CORDIC unit responsible for executing the instructions with long latency is also developed. In this thesis, we focus on the circuit design of CORIDC unit that calculates the triangular functions.
In the design of CORDIC unit, we propose three novel ideas to obtain an excellent solution. First, we modify the double rotation CORDIC algorithm to work on 360-degree full rotation range. It is important for supporting image-based VR computations in a high-performance manner. Second, to enhance performance and reduce circuit cost, the scheme of packed-formatted I/O is adopted. Third, an on-line number translation scheme is applied to reduce number translation time.
In this thesis, the CORDIC unit is modeled by Verilog language, and the COMPASS 0.35μm cell library and Synopsys EDA tool are adopted to synthesize the CORDIC circuit. Until now, we have accomplished logic circuit thesis and timing simulation takes of the CORDIC unit. Then, it will be delivered to Chip Implementation Center at National Science Council for IC prototyping.

LIST OF TABLES
LIST OF FIGURES
CHAPTER 1 INTRODUCTION
1.1 BACKGROUND AND MOTIVATION
1.2 THESIS ORGANIZATION
CHAPTER 2 ARCHITECTURE OF HIGHLY INTEGRATED MEDIA PROCESSOR
2.1 COMPUTATIONAL REQUIREMENTS OF 3D GRAPHICS
2.1.1 Database Traversal
2.1.2 Front-end (Geometric Processing)
2.1.3 Rasterization
2.2 COMPUTATIONAL REQUIREMENTS OF IMAGE-BASED VR
2.3 ANALYSIS OF MEDIA PROCESSORS
2.3.1 Microsoft Talisman Architecture
2.3.2 NSC98 Microprocessor
2.4 THE PROPOSED ARCHITECTURE FOR HIGHLY INTEGRATED MEDIA PROCESSOR
2.4.1 CORDIC Unit
2.4.2 MFU
2.4.3 Enhanced Instruction Set
CHAPTER 3 CORDIC BASED ALGORITHMS
3.1 CORDIC (COORDINATE ROTATION DIGITAL COMPUTER) ALGORITHM
3.2 REDUNDANT CORDIC ALGORITHM
3.3 ON-LINE CORDIC ALGORITHM
3.4 CORRECTING ROTATION CORDIC ALGORITHM
3.5 DOUBLE ROTATION CORDIC ALGORITHM
3.6 OTHER CORDIC ALGORITHMS
CHAPTER 4 ARCHITECTURE DESIGN OF CORDIC CIRCUIT
4.1 MODIFIED DOUBLE ROTATION CORDIC ALGORITHM FOR FULL ROTATION RANGE
4.1.1 Adopting tan-1(2-0) as the starting rotation angle
4.1.2 Moving the starting point to be at 180 degree
4.2 I/O INTERFACE OF THE CORDIC UNIT
4.2.1 Packet-formatted I/O
4.3 ON-LINE NUMBER TRANSLATION
4.4 DETAILED ARCHITECTURE OF THE COMPONENTS IN CORDIC UNIT
4.4.1 Architecture of Preprocessing Sub-unit
4.4.2 Architecture of Residual Angle Computation Sub-unit
4.4.3 Architecture of X & Y Components Computation Sub-unit
4.4.4 Architecture of Post-processing Sub-unit
4.3.5 Controller Sub-unit
CHAPTER 5 MODELING AND IMPLEMENTATION OF CORDIC CIRCUIT
5.1 DESIGN METHODOLOGY
5.2 DESIGN SKILLS
5.2.1 Redundant Number System
5.2.2 Decision the Pair (Pi, Qi)
5.2.3 Z Component Normalization
5.2.4 Redundant Number Adder
5.2.5 Shifter
5.2.6 X and Y Components Normalization
5.2.7 Number Translation
5.3 SYNTHESIS AND SIMULATION RESULTS
CHAPTER 6 CONCLUSION AND FUTURE WORKS
6.1 CONCLUSION
6.2 FUTURE WORKS
REFERENCES
APPENDIX A RTL CODE OF CORDIC UNIT
APPENDIX B SYNTHESIS RESULTS
APPENDIX C SIMULATION RESULTS

[1] Intel MMX and Streaming SIMD Extension Manual, http://www.intel.com
[2] AMD 3Dnow! TM Technology Manual.
[3] Foley, van Dam, Feiner, and Hughes, J.F., Comupter Graphics: Principles and Practice, Addison-Wesley, Reading, Mass., 1990.
[4] E. Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, Ph.D. Thesis, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City, UT, Dec. 1974.
[5] L. McMillan, and G. Bishop, “Plenoptic Modeling: An Image-based Rendering System”, SIGGRAPH, pp.39-46, 1995.
[6] S. M. Seitz and C. R. Dyer, “View Morphing”, SIGGRAPH, pp. 21-30, 1996.
[7] H. Huang, S. Nain, and Y. Hung, “Disparity-Based View Morphing (Disparity Morphing) - A New Technology for Image-Based Virtual Reality and Rendering Systems”, ACM Symposium on Virtual Reality Software and Technology, 1998.
[8] S. E. Chen, L. Williams, and Apple Computer Inc., “View Interpolation for Image Synthesis”, SIGGRAPH, pp.279-288, 1993.
[9] S. J. Gortler, R.Grzeszczuk, R. Szeliski, and M. F. Cohen, “The Lumugraph”, SIGGRAGH, pp., 1996.
[10] M. Levoy, and P. Hanrahan, “Light Field Rendering”, SIGGRAPH, pp.31-42, 1996.
[11] S. E. Chen and Apple Computer Inc., “QuickTime VR — An Image-based Approach to Virtual Environment Navigation”, SIGGRAPH, pp.29-38, 1995.
[12] J. Torborg, J. T. Kajiya, and Microsoft Corporation, “Talisman: Commodity Realtime 3D Graphics for the PC”, SIGGRAPH, pp.353-363, 1996.
[13] C. L. Wu, “Design and Implementation of an Advanced Microprocessor”, supported by National Science Council, Taipei, R.O.C., Project no. NSC85-2622-E-009-0102.
[14] J. Lengyel, J. Snyder, “Rendering with Coherent Layers”, SIGGRAPH, pp.233- 242, 1997.
[15] J. E. Volder, “The CORDIC Trigonometric Computing Technique”, IRE Trans. Electronic Computers, Vol. EC-8, No.3, pp.330-334, Sept. 1959. Computer Arithmetic Edition by Earle E., Swartzlander, JR., pp.226-230.
[16] Y. J. Huang, Design and Implementation of Multimedia Functional Unit in an Advanced Microprocessor, Master Thesis, Institute of Information Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C., June 1997.
[17] S. Y. Lin, Circuit Design of Multimedia Functional Unit Based on SIMD Technique, Master Thesis, Institute of Information Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C., June 1997.
[18] P. T. P. Tang, “Table-Lookup Algorithms for Elementary Functions and Their Error Analysis”, 10th IEEE Symposium on Computer Arithmetic, pp.232-236, 1991.
[19] S. Walther, “A Unified Algorithm for Elementary Functions”, AFIPS Conf. Proc., Vol. 38, pp.379-385, 1971. Computer Arithmetic Edition by Earle E., Swartzlander, JR., pp.272-276.
[20] S. Chen, C. Li, and Y. Hou, “Compatible CORDIC and CCM Algorithms for Small Area Realization”, IEEE Signal Processing Society, pp.572-579, Sept. 1995.
[21] J. D. Bruguera, E. Antelo, and E. L. Zapata, “Design of a Pipelined Radix 4 CORDIC Processor”, Parallel Computing, pp.729-744, Vol.19, July 1993.
[22] Ercegovac and T. Lang, “Redundant and On-line CORDIC：Application to Matrix Triangularization and SVD”, IEEE Trans. Computer, pp.725-740, June 1990.
[23] H. X. Lin and H. J. Sips, “On-line CORDIC Algorithms”, IEEE trans. Computers, pp.1038-1052, Aug. 1990.
[24] N. Takagi, T. Asada, and S. Yajima, “Redundant CORDIC Methods with a Constant Scale Factor for Sine and Cosine Computation”, IEEE Trans. Computers, pp.989-995, Aug. 1991.
[25] B. Parhami, “Carry-free Addition of Recorded Binary Signed-Digit Numbers”, IEEE Trans. Computers, pp.1470-1476, Nov. 1988.
[26] Rambus 64/72-Mbit RDRAM Datasheet, http://www.rambus.com
[27] Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic”, IRE Trans. Electronic Computers, pp.389-400, Sept. 1961.
[28] -, “On a flexible implementation of digital computer arithmetic”, in Inform, Processing ’62. Amsterdam: North-Holland, pp.664-670, 1963.
[29] -, “Binary-compatible signed-digit arithmetic”, in AFIPS Conf. Proc., 1964 Fall Joint Comput. Conf., pp.663-672, 1964.
[30] S.-J. Yih, M. Cheng, and W.-S. Feng, “Multilevel barrel shifter for CORDIC design”, Electronics Letters 20th, pp.13-14, Vol.32, June 1996.
[31] M. Ercegovac and T. Lang, “On-the-Fly Conversion of Redundant into Conventional Representations”, IEEE Trans. Computers, pp.895-897, July 1987.
[32] Verilog Family Reference Manual Version 1.6, Cadence Cooprtation, 1991.