臺灣博碩士論文加值系統

獨立擴張樹之尋找應用於分散式計算網路(distributed computing networks)失誤容認協定(fault-tolerant protocols)，例如，網路上的廣播(broadcasting)就是在網路上某個節點傳送訊息到其他的節點，因此我們能以獨立擴張樹為基礎設計失誤容忍機制，藉由以獨立擴張樹(independent spanning tree)的根為訊息的源點，在k棵獨立擴張上傳送著k個被複製的訊息以達成失誤容忍，假如源點沒損壞這個機制將容忍至k-1個失誤點，二維的的環形曲面圖由於他的結構簡單易於發展演算法(algorithm)，因此在研究價值上是有用的，我們將應用二維環形曲面圖(torus)於獨立擴張樹上以解決失誤容忍。
Obokata 等已提到n維環形曲面圖是個2n通道圖而且以任何的節點為根有2n棵獨立擴張樹，他們將二維環形曲面圖視為Cr和Cc環形圖的乘積圖而且從Cr和Cc的獨立擴張樹建造R(r,c)四棵獨立擴張，事實上他們的演算法很巧妙但很難去理解，我們將提出簡易的演算去建造出二維環形曲面圖的獨立擴張樹。

The study on independent spanning trees finds applications in fault-tolerant protocols for distributed computing networks. For example, the broadcasting in a network is sending a message from a given node to all other nodes in the network. We can design a fault-tolerant broadcasting scheme based on independent spanning trees [2] [8]. The fault-tolerance can be achieved by sending k copies of the message along k independent spanning trees rooted at the source node. If the source node is faultless, this scheme can tolerate up to k-1 faulty nodes. Two-dimension tori (or torus networks) are important due to its simple structure and suitability for developing algorithms. We are going to apply two-dimension tori in independent spanning tree for fault-torlerance-scheme.
Obokata et al. have mentioned that an n-dimension torus is a 2n-channel graph and has 2n independent spanning trees rooted at any vertex. They view a 2-dimension torus R(r,c) as the product graph of cycles Cr and Cc , and construct four independent spanning trees of R(r,c) from independent spanning trees (paths) of Cr and Cc . Actually, their algorithm is a “cure-all”, and hence very hard to figure out. In this paper, we shall propose a simpler algorithm to construct four independent spanning trees on a two-dimension torus.

中文摘要 ……………………………………………………………………Ⅰ
英文摘要 ……………………………………………………………………Ⅱ
致謝 ………………………………………………………………………..Ⅲ
目錄 ………………………………………………………………………….V
圖表索引 ……………………………………………………………………Ⅵ
第一章 緒論 …………………………………………………………………1
1.1 研究動機和背景介……………………………………………………1
1.2 點相離(vertex disjoint) ………………………………………..1
1.3 獨立擴張樹(independent spanning trees) ……………………2
1.4 Torus介紹 ……………………………………………………………5
1.5 論文架構………………………………………………………………7
第二章 相關研究………………………………………………………………8
2.1 Cartesian product G1 G2之操作法……………………….……….8
2.1 obokata建造獨立擴張樹的方法…………………………..………..9
2.2.1 n-通道圖(n-cannel graph) …………………………….………9
2.2.2 obokata建造獨立擴張樹演算法 ………….……………..….…10
2.3最佳獨立擴張樹…………..……………………………….…………13
2.3.1想法 …………………………………………………………………19
2.3.2 最佳獨立擴張樹作法..……………………………………………19
2.3.3 最佳獨立擴張樹調整………………………………………………22
第三章 環形曲面圖的獨立擴張樹建造…………………………………...26
3.1 環形曲面圖獨立擴張樹之建造步驟一……………………………..26
3.2 環形曲面圖獨立擴張樹之建造步驟二..……………………………27
3.3 環形曲面圖獨立擴張樹之建造步驟三………………………………28
3.4 環形曲面圖獨立擴張樹之建造步驟四..………………………………29
3.5 環形曲面圖獨立擴張樹之建造步驟五………………………………30
3.6 環形曲面圖獨立擴張樹之建造步驟六………………………………31
第四章 環形曲面圖獨立擴張樹正確性之驗証…………………………….35
第五章 結論 ………………………………………………………………..41
5.1結果與分析 ……………………………………………………………41
5.2 未來工作 ……………………………………………………………41
參考文獻 …………………………………………………………………….42

[1]A. Chandra and R. Melhem, “Reconfiguration in 3D Meshes,” Proc.1994 Int’1 Workshop Defect and Fault Tolerance in VLSI Systems, pp. 194-202, 1994.
[2]A. Huck, “Disproof of A Conjecture about Independent SpanningTrees in K-Connected Directed Graphs,” Journal of Graph Theory,Vol. 20, No. 2, 1995, pp.235-239.
[3]A. Huck, “Independent Trees in Planar Graphs,” Graphs and Combinatorics 15, 1999, pp.29-77.
[4]A. Itai, M. Rodeh, “The Multi-tree Approach to Reliability inDistributed Networks,” Information and Computation 79, 1988,pp.43-59.
[5]A. Zehavi, A. Itai, “Three Tree-Paths,” Journal of Graph Theory,Vol. 13, No. 2, 1989, pp.175-188.
[6]Dehne, F.; Gotz, S.,”Practical Parallel Algorithms for Minimum Spanning Trees,’ Reliable Distributed Systems, pp.366 -371,1988
[7]D.Lenoski, J. Laudon, T. Joe, D. Nakahira, L. Stevens, A. Gupta, and J. Hennessy, “The DASH Prototype: Implementation andPerformance,: Proc. 19th Anmual Int’I Symp. Computer Architecture, pp. 92-103, May 1992.
[8]F. Bao, Y. Igarashi, S.R. Öhring, “Reliable Rroadcasting in Product Networks ,” IEICE Technical Report COMP 95(18), 1995, pp.57-66.
[9] F. Petrini, “Total-Exchange on Wormhole k-kary n-cubes with Adaptive Routing,” Proc. Of the First Merged IEEE International Parallel Processing Symposium and Symposium on parallel and Distributed Processing. PP. 267-271, March 1998.
[10] Feng Bao; Funyu, Y.”Reliable Broadcasting and Secure Distributing in Channel Networks” Parallel Architectures,pp. 472 -478,1997
[11] F. Qzguner and C. Aykanat, “A reconfiguration Algorithm for Fault Tolerance in a Hypercube Multiprocessor,”Information Processing Letters, vol. 29, pp. 247-254, Nov. 1998
[12] Intel Corporationl Paragon XP/S Product Overview, 1991.
[13] J. Bruck, R. Cypher, and C,-T. Ho, “Efficient Fault-Tolerant Mesh and Hypercube Architectures,: Proc.22nd Int’l Symp. Fault-Tolerant Computing, pp. 162-169,July 1992
[14] J. Cheriyan, S. N. Maheshwari, “Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs,” Journal of Algorithms 9, 1988, pp.507-537.
[15] J.-C. Bermond, F. Comellas, and D. F. Hsu, “Distributed Loop Computer Networks: A Survey,” Journal of Parallel and Distributed Computing, 24, 2-10(1995).
[16] J. H. kim and P. k. Rhee, “The Rule-Based Approach to Reconfiguration of 2-D Processor Arrays,” IEEE Trans. Computers, vol. 42, no.11, pp. 1403-1408, Nov. 1993.
[17] J. Fabrega and M. Zaragoza., “Fault tolerant routings in double networks,” Ars Combin, Vol.25A, 1988,pp.187-198.
[18] K. Obokata, Y. Iwasaki, F. Bao and Y. Igarashi, “Independent Spanning Trees of Product Graphs,” Lecture Notes in Computer Science 1197, 1996, pp.338-351.
[19] L. Narayanan and J. Opatrny, “Compact Routing on Chordal Rings of Degree 4,” Algorithmica, (1999) 23: 72-96.
[20]Lai, T.H.; Ming-Jye Shen.’Constructing Euclidean minimum Spanning Trees and All Nearest Neighbors on Reconfigurable Meshes”Parallel and Distributed Systems, IEEE Trans. Parallel and Distributed Systems, Vol 7 pp.806 -817. , Aug. 1996
[21] M.A. Sridar and C.S. Raghavendra, “On Finding Maximal Subcubes in Residual Hypercubes,” Proc. Second IEEE Symp. Parallel and Distributed Processing,pp. 870-873. Dec. 1990.
[22] M.D. Noakes, D.A. Wallach, and W.J. Dally, “The J-Machine Multicomputer: An Architectural Evaluation, “Proc. 20th Annual Int’I Symp. Computer Architecture. Pp.224-235, May 1993.
[23] Mukhopadhyaya Krishnendu and Sinha Bhabani P., “Optimal design and routing of distributed loop networks,” Proc. IEEE Int’l Symp. Circuits and Systems, pp, 1021-1024, Aug. 11-14, 1991.
[24] Mukhopadhyaya Krishnendu and Sinha Bhabani P., “Fault-tolerant routing in distributed loop networks,” IEEE Transactions on Computers, Vol. 44, No. 12, December. 1995, pp. 1452-1456.
[25] M. Soch and Pavel Tvrdik, “Time-Otimal Gossip of Large Packets in Noncombining 2D Tori and Meshes,” IEEE Trans. Parallel and Distributed Systems., Vol. 10. no. 12, pp. 1252-1261, Dec. 1999.
[26] N.-F. Tzeng and G. Lin, “Maximum Reconfiguration of 2-D Mesh Sytems with Faults,” Proc. 25th Int’l Conf. Parallel Processing, pp. I-77-I84, Aug. 1996.
[27] R. W. Whitty, “Vertex-Disjoint Branchings in Directed Graphs,” Journal of Graph Theory, Vol. 11, No. 3, 1987, pp.349-358.
[28] Samir Khuller, Baruch Schieber, “On Independent Spanning Trees”, Information Processing Letters 42, 1992, pp.321-323.
[29] R.E. Kessler and J.L. Schwarzmeier, “CRAY T3D: A New Dimension for Cray Research, “ Proc. 1993 Compcon Spring, pp. 176-182, 1993.
[30] S. Latifi, “Distributed Subcube Identification Algorithms for Reliable Hypercubes,” Information Processing Letters, vol. 38, pp. 315-321, June 1991.
[31] T. Hasunuma and H. Nagamochi, “Independent Spanning Trees with Small Depths in Tterated Line Digraphs,” Discrete Applied Mathematics 110, 2001, pp.189-211.
[32] W.J. Dally, “Performance Anlysis of k-ary n-cube Interconnection Networks,”IEEE Trans. Computers, vol. 39, no. 6, pp. 775-785, June 1992.
[33] Y.J. Suh and S. Yalamanchili, “All-to-AllCommunication with Minimum Start-up Costs in 2D/3D Tori and Meshes,” IEEE Trans. Parallel and Distributed Systems. Vol.9,no.5,pp.442-458,May 1998
[34] Young-Joo Suh; Shin, K.G. “All-to-All Personalized Communication in Multidimensional Torus and Mesh Networks,” IEEE Trans. Parallel and Distributed Systems, pp38-59
[35] Yulu Yang; Funahashi, A,” Recursive diagonal torus: an interconnection network for massively parallel computers” IEEE Trans. Parallel and Distributed Systems , pp701 -715 2001.
[36]Yu-Chee Tseng; San-Yuan WangEfficient Broadcasting in Wormhole-Routed Multicomputers: A Network-Partitioning Approach Parallel and Distributed Systems, IEEE Trans. Parallel and Distributed Systems , Vol. 10 pp44-61 1999