臺灣博碩士論文加值系統

　　本論文詳細研究了一般化彼得森圖形，它與著名的彼得森圖形一樣有內外兩個環，每個環的節點數可以為5或大於6的任意整數，而且與彼得森圖形一樣是分支度三的規則圖形。我們詳細討論了一般化彼得森圖形的性質，並且提出一最短路徑的傳繞演算法以及其VLSI的佈局方法。
本論文的另一個主題是基於一個創新的圖形擴展方法提出一個命名為Y 的新圖形，以二分相連圖形為基圖並且將每個節點以環擴充為主節點，與被廣泛應用的超立方體(hypercube)相較，Y 的節點數可以多25%，並且直徑較小。若與一般化彼得森圖形比較，新圖形Y 與一般化彼得森圖形都是規則圖形(regular) ，但是新圖形的節點數、分支度和圖形直徑等性質有較大的彈性。事實上，一般化彼得森圖形是 Y圖形的一個特例。我們也為Y圖形發展出一個最短路徑的傳繞演算法。

　　This thesis presents a detailed study of several properties of the generalized Petersen graph, which are considered important to the parallel architectures. Similar to the well-known Petersen graph, the generalized Petersen graph contains two cycles; all the nodes within one cycle are each linked to their counterparts in the other cycle. Each cycle can hold either exactly five nodes or any number of nodes larger than six, according to our study. Besides the detailed analyses of several important properties of the generalized Petersen graph, we also propose a shortest-path routing algorithm and a general method for its VLSI layout.
The second major contribution of this thesis is the proposition of a new graph, denoted as Y, developed in conjunction with a novel approach to graph expansion. This expansion method recursively utilizes the structure of a bipartite graph and substitutes each node with a cyclic supernode. When compared with the popular hypercube structure, the Y graph not only contains up to 25% more nodes, but also has smaller diameters. Furthermore, close comparisons with the generalized Petersen graph reveals that they are both regular, but the Y graph is more favorable for being less restrictive in properties like number of nodes, degree, and diameter. Its structural flexibility can easily be seen from the fact that the generalized Petersen graph can be derived from the Y graph with ease. We also develop for the Y graph a shortest-path routing algorithm.

符號對照表 i
圖目錄 iii
表目錄 iv
第一章 緒論 1
1-1 簡介 1
1-1 彼得森圖形 2
1-2 彼得森圖形的擴展 3
1-4 論文內容概述 3
第二章 一般化彼得森圖形 7
2-1 一般化彼得森圖形的完整定義 7
2-2 圖形個數相關性質 11
2-3 對稱相關性質 13
2-4 距離相關性質 16
2-5 一般化彼得森圖形傳繞演算法 22
第三章 新圖形Y 28
3-1 新圖形Y的定義 28
3-2 Y的拓撲性質 30
3-3 容錯特性 33
3-4 傳繞演算法 33
3-5 歸納與比較 34
第四章 嵌入與VLSI佈局 36
4-1 嵌入 36
4-2 佈局 37
第五章 結論和未來發展 41
參考文獻 43
附錄 A：一般化彼得森圖形的繪圖程式 46

[1] G. Chen and F.C.M. Lau, “Tighter Layouts of the Cube-Connected Cycles,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 2, pp. 182-191, Feb. 2000.
[2] G. Chartrand and R.J. Wilson, “The Petersen Graph,” in Graphs and Applications, F. Harary and J.S. Maybee, eds., pp. 69-100, 1985.
[3] K. Day and A.-E. Al-Ayyoub, “The Cross Product of Inter-connection Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 2, pp. 109-118, Feb. 1997.
[4] S.K. Das and A.K. Banerjee, “Hyper Petersen network: yet another hypercube-like topology,” Frontiers of Massively Parallel Computation, Fourth Symposium on the, pp. 270-277, 1992.
[5] K. Efe and A. Fernandez, “Products for Networks with Logarithmic Diameter and Fixed Degree,” IEEE Tran. Parallel and Distributed Systems, vol. 6, no. 9, pp. 963-975, Sep. 1995.
[6] Ada W. Chee Fu and S.-C. Chau, “Cyclic-Cubes: A New Family of Interconnection Networks of Even Fixed-Degrees,” IEEE Tran. Parallel and Distributed Systems, vol. 9, no. 12, pp. 1,253-1,268, Dec. 1998.
[7] R. Feldmann and W. Unger, “The Cube-Connected Cycles Networks Is a Subgraph of the Butterfly Network,” Parallel Processing Letters, vol. 2, no. 1, pp. 13-19, 1992.
[8] M.-B. Lin and G.-E. Jan, “Routing and Broadcasting Algorithms for Root-Folded Petersen Networks,” Journal of Marine Science and Technology, vol. 6, no. 5, pp. 65-70, Jun. 1998.
[9] B. Monien and H. Sudborough, “Embedding One Interconnection Network in Another,” Computational Graph theory, pp. 257-282, Wien: Spcycleer-Verlag, 1990.
[10] S. Ohcycle and S. K. Das, “Folded Petersen Cube Networks: New Competitors for the Hypercubes,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 2, pp. 151-168, Feb. 1996.
[11] S. Ohcycle, J. Sibeyn, and O. Sykora, “Optimal VLSI-layout for the Efficient Petersen Based Interconnection Network Family,” in Proc. Sixth Int’l Conf. Parallel and Distributed Computing and Systems, pp. 121-124, Washington, D.C., Oct. 1994.
[12] F. P. Preparata and J. Vuillemin, “The Cube-Connected Cycles: A Versatile Network for Parallel Computation,” Comm. ACM, vol. 24, no. 5, pp. 300-309, May 1981.
[13] I. Stojmenovic, “Honeycomb Networks: Topological Properties and Communication Algorithms,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 10, pp. 1,036-1,042, Oct. 1997.
[14] Y. Sun, P. Y. S. Cheung, and X. Lin, “Recursive Cube of Cycles: A New Topology for Interconnection Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 3, pp. 275-286, Mar. 2000.
[15] L. Uhr, Multicomputer Architecture for Artificial Intelligence. Wiley Interscience, New York, 1987.