在這四、五十年期間，單一處理器的執行速度是穩定增加的，然而，對於任何單一處理器而言，其計算能力仍然受到其執行速度的上限而有所限制。因此，當我們處理需要執行大量計算之複雜的科學問題時，一個可以提高效率的最自然的方法就是使用多處理器。在多處理器中解決平行問題時，處理器間之訊息傳遞是需要的。在這篇論文中，我們利用一個以張量乘積為基礎的代數理論去表示一種有名的編碼方式，也就是格雷碼，在電腦科學的各個不同領域中，格雷碼常常被拿來當作研究的工具，特別是在靜態內部連結網路，例如，環、n 維環面體、超立方體、以及立方體連結。 我們將以張量乘積表示二進位之格雷反射排列延伸至 r 進位，並且發展出以張量乘積表示混合基底之格雷反射排列， 這些都在論文中被一一說明。我們也舉例說明以張量乘積表示廣義之格雷反射排列可以應用到網路嵌入上，在這個應用中，我們可以利用格雷反射排列當作嵌入函數，將一個環或者是二維環面體之內部連結網路嵌入至 n 維環面體之內部連結網路。我們也真正的去計算網路嵌入所定義出來的公式，用以證明格雷反射排列確實可以被當作嵌入函數，將之應用到網路嵌入上。

For the duration of the last few decades, the speed of uniprocessor has steadily increased. However, its computing power is still limited by the upper bound on the speed of any single processor. Consequently, a natural way to enhance performance is to use multiprocessor to deal with many complex scientific problems that need a large quantity of computation. Communications between processors are required to solve a parallel problem on the multiprocessor. In this thesis, we present an algebraic theory based on tensor products for representing a famous encoding method, reflected Gray code, which can be often used in several research areas of computer science, especially in static interconnection network such as rings, n-dimensional tori, hypercubes, and cube-connected cycles. We derive a tensor formulation of the base-r reflected Gray code based on binary case and extend it to mixed-radices Gray code formulation. We also describe the application of reflected Gray permutation, a formal model for specifying and verifying network embeddings using reflected Gray permutation as embedding function. This model can be used to demonstrate that a ring and a two-dimensional torus network can be embedded in an n-dimensional torus interconnection network. We illustrate and justify the correctness of which reflected Gray permutation can be used as embedding function in this model.

Acknowledgements ……………………………………………………………… III
Abstract …………………………………………………………………………… IV
Table of Contents ………………………………………………………………… VI
List of Figures ……………………………………………………………………… VII
Chapter 1. Introduction …………………………………………………………… 1
Chapter 2. Related Work ………………………………………………………… 3
Chapter 3. An Overview of the Tensor Product Notation ………………………… 6
3.1 Some Difinitions of Tensor Product Notation ………………………… 6
3.2 Some Theorems and Properties of Tensor Product Notation…………… 10
Chapter 4. Generalized Reflected Gray Permutation ……………………………… 12
4.1 Binary Gray Code Formulation ……………………………………… 12
4.2 Base-r Gray Code Formulation ……………………………………… 18
4.3 Mixed-Radices Gray Code Formulation ……………………………… 44
Chapter 5. Application of Reflected Gray Permutation …………………………… 64
5.1 Direct Interconnection Networks …………………………………… 64
5.2 Network Embedding ………………………………………………… 75
5.2.1 A Brief Overview of Network Embedding …………………… 75
5.2.2 Network Embedding Using Reflected Gray Permutation ……… 80
Chapter 6. Conclusions …………………………………………………………… 105
Bibliography ……………………………………………………………………… 107

Bibliography
[1] T. Feng. A survey of interconnection networks. IEEE Transaction on Computer Systems, C-30(12):12-27, Dec. 1981.
[2] A. Grahram. Kronecker Products and Matrix Calculus: With Applications. Ellis Horwood Limited, 1981.
[3] J. P. Hayes. Computer Architecture and Organization. McGraw Hill, 1988.
[4] C. T. Ho. and S. L. Johnsson. Embedding meshes in boolean cubes by graph decomposition. Journal of Parallel and Distributed Computing, 8, pp. 328-338, 1990.
[5] C. T. Ho, M. T. Raghunath, and S. L. Johnsson. An efficient algorithm for Gray-to-binary permutation on hypercubes. Journal of Parallel and Distributed Computing, 20, pp. 114-120, 1994.
[6] R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1991.
[7] C.-H. Huang, J. R. Johnson, R. W. Johnson. A tensor product formulation of Strassen's matrix multiplication algorithm. Appl Math Letters, 3(3):67-71, 1990.
[8] C.-H. Huang, J. R. Johnson, R. W. Johnson. Generating parallel programs from tensor product formulas: a case study of Strassen's matrix multiplication algorithm. In International Conference on Parallel Processing, volume III, pp. 104-108, 1992.
[9] J. R. Johnson, R. W. Johoson, 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.
[10] R. W. Johnson, C.-H. Huang, J. R. Johnson. Multilinear algebra and parallel programming. Journal of Supercomputing, 5:189-218, 1991.
[11] S. L. Johnsson. Communication efficient basic linear algebra computations on hypercube architectures. Journal of Parallel and Distributed Computing, 4, 2 pp. 133-172, Apr.1987.
[12] S. L. Johnsson. and C. T. Ho Binary cube emulation of butterfly networks encodeed by Gray code. Journal of Parallel and Distributed Computing, 20 pp. 261-279, 1994.
[13] S. D. Kaushik, S. Sharma, C.-H. Huang, J. R. Johnson, R. W. Johnson, and P. Sadayappan. An algebric theory for modeling direct interconnection networks. Technical Report OSU-CIS-RC-1/92-TR 5, Dept. of Computer and Information Science, The Ohio State University, Jan. 1992. Also in Proc. of Supercomputing'92, pp. 488-497.
[14] S. D. Kaushik, S. Sharma, C.-H. Huang, J. R. Johnson, R. W. Johnson, and P. Sadayappan. An algebric theory for modeling direct interconnection networks. Journal of Information Science and Engineering, 12, 25-49, 1996.
[15] V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing. The Benjamin/Cummings Publishers, Inc. 1994.
[16] B. Kurnar, C.-H. Huang, P. Sadayappan, and R. W. Johnson. A tensor product formulation of Strassen's matrix multiplication algorithm with memory reduction. Scientific Programming, 4(4):275-289, 1995.
[17] S. Lakshmivarahan. and S. K. Dhall. Analysis and Design of Parallel Algorithms. McGraw-Hill, Inc. 1990.
[18] F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays‧Trees‧Hypercubes. Morgan Kaufmann Publishers, Inc. 1992.
[19] C. V. Loan. Computational Frameworks for the Fast Fourier Transform. SIAM, 1992.
[20] J. A. Moore. and M. J. Quinn. Generating an efficient broadcast sequence using reflected Gray codes. IEEE Transaction on Parallel and Distributed Systems, vol. 8, no. 11, pp. 1117-1122, Nov. 1997.
[21] Y. Saad, M. Schultz. Topological properties of hypercubes. IEEE Transaction on Computer Systems, C-37 pp.12-27, 1988.
[22] S. Q. Zheng. and S. Latifi. Optimal simulation of linear multiprocessor architectures on multiply-twisted cube using generalized Gray codes. IEEE Transaction on Parallel and Distributed Systems, vol. 7, no. 6, pp. 612-619, 1996.
[23] A. Y. Zomaya. Parallel and Distributed Computing Handbook. McGraw-Hill, Inc. 1996.