臺灣博碩士論文加值系統

在硬體電路設計中，以往以手繪電路圖描述設計的方式已不能滿足效率和成本的考量與需求。目前，以高階語言的電路方式來做描述、合成與模擬是一種新的趨勢。在高階硬體描述語言的成型與建立標準後，我們希望將一些計算上的問題在經由有效的數學方式所描述出來後，能將之合成為硬體描述語言的程式，進而幫助在硬體電路上的設計，達到較佳的設計效果。在這篇論文中，我們提出了一個轉換合成的系統，能將張量乘積公式轉換合成VHDL硬體描述語言的程式。張量乘積公式在過去已被大量使用來作為描述塊狀遞迴演算法。張量乘積套用在運算上的型態可以把它對應到程式語言的結構表現。在這裡，我們以VHDL語言當作我們主要的描述語言，用它合成的結果來幫助電路的設計。因為VHDL擁有與低階方式同樣用來描述硬體元件的特性，所以VHDL更是適合於超大型積體電路 (VLSI) 的電路設計。在我們的系統中，我們將每個張量乘積的公式以LISP-like的方式描述出來，並將之轉換成VHDL程式碼，包含了位元階層物件的處理與運算，在整個過程中，我們是以平行的前置問題當做例子來作合成的說明。

In the early years, engineers designed logical circuits with hand drawing which is very inefficient and costly. Now, circuit design using high-level hardware description languages is a new trend. High-level hardware description languages can be used to describe, synthesize, and simulate hardware circuits. With the standard of hardware description language developed up in recent years, we will use mathematical formulas to describe computational problems, then to synthesize hardware description language programs from mathematical formulas. The synthesizing results may be efficiently used in hardware circuit design, and optimizing circuits. In this thesis, we present a system to translate tensor product formulas to VHSIC Hardware Description Language (VHDL) programs. Tensor product formulas are used to represent block recursive algorithms. Operations of tensor product formulas can be mapped to programming language constructs. We use VHDL as our target programming language for program synthesis. VHDL contains high-level programming language constructs as well as low-level constructs for describing hardware components. Hence, VHDL is suitable for VLSI circuit design. In our system, a tensor product formula is written in a LISP-like form and translated into VHDL code containing bit-level objects and operations. We use the parallel prefix problem as an example to illustrate program synthesis.

Contents
1 Introduction ...............................................................4
2 An Overview of The Tensor Product.......................................... 6
2.1 Tensor Product Definition ................................................6
2.2 Stride Permutation .......................................................7
2.3 Other Properties .........................................................8
3 Tensor Product Formulas for Parallel Prefix Algorithms.....................10
3.1 Parallel Form ...........................................................11
3.2 Vector Form .............................................................13
3.3 Stride Permutation ......................................................16
4 An Overview of VHDL .......................................................17
4.1 VHDL structure ..........................................................17
4.2 Data Types ..............................................................20
4.3 VHDL Statement ..........................................................21
4.3.1 Assignment Statement ..................................................21
4.3.2 Sequential Statement ..................................................22
4.3.3 Concurrent Statement ..................................................24
5 System Implementation .....................................................25
5.1 Formulas Expression .....................................................26
5.1.1 Parallel Form Formula .................................................26
5.1.2 Vector Form Formula ...................................................27
5.1.3 Stride Permutation ....................................................27
5.1.4 Combination Formula ...................................................28
5.2 Parallel Form Formula to VHDL ...........................................29
5.3 Vector form formula to VHDL .............................................35
5.4 Stride permutation formula to VHDL ......................................38
5.5 Combination Formula to VHDL .............................................41
6 Conclusions and future work.............................................44

[1] G.E. Blelloch. Prefix sums and their applications.Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, November 1990.[2] J.W. Brewer. Kronecker products and matrix calculus in system theory. IEEE Transaction on Circuits and Systems, 25:772--781, 1978.[3] D.L. Dai, S.K.S. Gupta, S.D. Kaushik, J.H. Lu, R.V. Singh, C.H. Huang, P. Extent: A portable programming environment for designing and implementing high-performance block-recursive algorithms. In Proceedings of Supercomputing ''94, pages 49--58, Los Alamitos, USA, 1994. IEEE Comput. Soc. Press.[4] M.-H. Fan, C.-H. Huang, Y.-C. Chung, J.-S. Liu, and J.-Z. Lee. A programming methodology for designing parallel prefix algorithms.In Proceedings of the 2001 International Conference on Parallel Processing, pages 463--470, Los Alamitos, USA, 2001. IEEE Comput. Soc. Press.[5] A.Graham. Kronecker Products and Matrix Calculus: With Applications. Ellis Horwood Limited, 1981.[6] F.A. Graybill. Matrices, with Applications in Statistics. Wadsworth International Group, 1983.[7] S.K.S. Gupta, C.-H. Huang, P.Sadayappan, and R.W. Johnson. A framework for generating distributed-memory parallel programs for block recursive algorithms. J. Parallel and Distributed Computing, 34:137--153, 1996.[8] C.-H. Huang, J.R. Johnson, and R.W. Johnson. A tensor product formulation of Strassen''s matrix multiplication algorithm. Appl. Math Letters}, 3(3):104--108, 1990.[9] R.D.M. Hunter and T.T. Johnson.Introduction to VHDL. CHAPMAN-HALL, Inc, 1996.[10] J.R. Johnson, R.W. Johnson, D.Rodriguez, and R.Tolimieri. A methodology for designing, modifying and implementing Fourier transform algorithms on various architectures. Circuits Systems Signal Process, 9(4):450--500, 1990.[11] S.Mazor and P.Langstraat. A Guide to VHDL. Kluwer Academic Publishers, 1992.[12] G.X. Ritter and P.D. Gader. Image algebra techniques and parallel image processing.J. Parallel and Distributed Computing, 4:7--44, 1987.