本研究係建議一套在二維環形曲面中可容許隨機錯誤的廣播演算法並提供該演算法的時間複雜度分析。吾人利用環形曲面的對稱特性與錯誤節點叢集模型以設計本演算法。本演算法主要分成兩部分：錯誤區塊外與錯誤區塊內的訊息傳輸。在錯誤區塊外，先將訊息傳輸到部分特定節點（稱為Diagonal Dominating Nodes；DDNs）。這些節點再將訊息傳送到對角線上全部沒有錯誤發生的節點。最後，研究再利用自行設計的傳輸樣式來傳輸訊息。在錯誤區塊內，根據研究分析結果，可推論在錯誤區塊中找到一個最有效率的訊息廣播傳輸路徑是屬於NP-hard問題。鑑於此，本研究提出一個啟發式的演算法以解決錯誤區塊的訊息傳輸問題。

In this thesis, we develop a fault-tolerant broadcasting algorithm on 2D torus network with arbitrary faults and investigate the algorithm’s upper bound in terms of the total time steps. In our approach, we achieve fault tolerance by taking the advan-tages of topological properties of 2D torus. Besides, the fault block model is used based on which all faulty nodes in a network are confined in a set of disjoint blocks. The broadcast process is carried out in two phases: outside fault block region and in-side fault block region. In the outside fault block region phase, the broadcast message is sent from a given source node to some specific nodes, called Diagonal Dominating Nodes (DDNs). Then, DDNs send the broadcast message to all non-faulty nodes on the diagonal line. Finally, specific message transfer patterns are applied. Furthermore, for the inside fault block region phase we develop a heuristic broadcasting algorithm because to resolve the NP-hard inside-fault-block broadcasting problem.

Contents
中文摘要…………………………………………………………………………… I
AbstractII………………………………………………………………………… II
誌謝 ………………………………………………………………………………… III
Content ……………………………………………………………………………… IV
List of Figures …………………………………………………………………… V
List of Tables …………………………………………………………………… VI
Chapter 1 Introduction…………………………………………………………………………… 1
1.1 Background and Motivation…………………………………………………………………………… 1
1.2 Outline of the Thesis…………………………………………………………………………… 3
Chapter 2 Preliminaries…………………………………………………………………………… 4
2.1 Mesh/Torus Topology Properties…………………………………………………………………………… 4
2.2 Routing/Broadcasting…………………………………………………………………………… 7
2.2.1 Wormhole Routing vs. Store-and-Forward…………………………………………………………………………… 9
2.3 Computation Component Model…………………………………………………………………………… 13
2.4 Fault Tolerance…………………………………………………………………………… 14
Chapter 3 Related Work…………………………………………………………………………… 16
Chapter 4 Problem Formulation…………………………………………………………………………… 19
Chapter 5 Fault-tolerant Broadcasting Algorithms…………………………………………………………………………… 22
5.1 Near optimal Broadcasting Algorithms in 2D Torus…………………………………………………………………………… 25
5.2 Fault-tolerant Broadcasting Algorithm in 2D Torus up to 6 Faults…………………………………………………………………………… 33
5.3 Fault-Tolerant Broadcasting Algorithm in 2D Torus with Arbitrary Faults…………………………………………………………………………… 50
Chapter 6 Conclusion…………………………………………………………………………… 72
Bibliography……………………………………………………………… 74

Bibliography
[1] Avizienis Algirdas, “Fault Tolerant Computing-an overview,” IEEE Transactions on Computers, Vol. 4, pp. 5-8, 1971.
[2] B.F.A. AlMohammad and Bella Bose, “Fault-Tolerant Communication Algo-rithms in Toroidal Networks,” IEEE Transaction on Parallel and Distributed Systems, Vol. 10, No. 10, October 1999.
[3] Mike Barnett, David G. Payne, Robert A. Van de Geijn, and Jerrell Watts, “Broadcasting on Meshes with Wormhole Routing,” The Journal of parallel and Distributed Computing, Vol. 35, pp. 111-122, February 1996.
[4] Gary Chartrand and Ortrud R. Oellermann, Applied and Algorithmic Graph The-ory, McGraw-Hill, 2000.
[5] Yuh-Shyan Chen, Che-Yi Chen and Yu-Chee Tseng, “Multi-Node Broadcasting in a Wormhole-Routed 2-D Torus Using an Aggregation-then-Distribution Strat-egy,” Proceedings of the 1999 ICPP Workshops on Group Communication (IWGC ‘99), Aizu, Japan, pp. 50-55, September 1999.
[6] Cray T3D System Architecture Overview Manual, Cray Research Inc., 1993.
[7] William J. Dally and Charles L. Seitz, “Deadlock-Free Message Routing in Multiprocessor Interconnection Networks,” IEEE Transactions on Computers, Vol. C-36, No. 5, May 1987.
[8] S. Dobrev and I.VRTO, “Optimal Broadcasting in Tori with Dynamic Faults,” Parallel Processing Letters, Vol. 12, No. 1, pp.17-22, February 2002.
[9] Jose Duato, Sudhakar Yalmanchili and Lionel Ni, Interconnection Networks – An Engineering Approach, IEEE Computer Society Press, 1997.
[10] Yomin Hou, Efficient Algorithms for Some Collective Communications on Wormhole-Routed Mesh-Like Networks, Dissertation in Electrical Engineering and Computer Science of Nation Chiao Tung University at Hsinchu, Taiwan, January 2001.
[11] Yomin Hou, Chien-Min Wang, Ming-Jer Tasi and Lih-Hsing Hsu, “Broadcasting on Wormhole-Routed 2D Tori with Arbitrary Size,” Proceesings of the 1998 In-ternational Conference on Parallel and Distributed Systems, pp. 334-341, Tainan, Taiwan, December 1998.
[12] Zhen Jiang and Jie Wu, “Fault-Tolerant Broadcasting in 2-D Wormhole-Routed Meshes,” The Journal of Supercomputing, Vol. 25, No. 3, pp. 255-275, July 2003
[13] R.C.T. Lee, R.C. Chang, S.S. Tseng and Y.T. Tsai, Introduction to the Design and Analysis of Algorithms, Taipei: FLAG, 2002.
[14] Nai-Wei Lo, Fault Tolerant Broadcasting Algorithms for Interconnection Net-works, Doctor Dissertation, Electrical Engineering, State University of New York at Stony Brook, December 1998.
[15] Lionel M. Ni and Philip K. Mckinley, “A Survey of Wormhole Routing Tech-niques in Direct Networks,” IEEE Computer, Vol. 26, No. 2, pp. 62-76, February 1993.
[16] Presant Mohapatra, “Wormhole Routing Techniques for Directly Connected Multicomputer Systems,” ACM Computing Surveys, Vol. 30, No. 3, September 1998.
[17] W. Oed, “Massively Parallel Processor System Cray T3D,” technical report, Cray Research, November 1993.
[18] Seungjin Park, Steven Seidel and Jong-Hoon Youn, “Fault-tolerant Broadcasting in Wormhole-Routed Torus Networks,” Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), April 2002.
[19] Joseph G. Peters and Michel Syska, “Circuit-Switched Broadcasting in Torus Netwroks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 3, March 1996.
[20] S. Scott and G. Thorson, “The Cray T3E Network: Adaptive Routing in High Performance 3D Torus,” Proc. HOT Interconnects IV, Stanford University, Au-gust 1991.
[21] Yih-jia Tsai, and Philip K. Mckinley, “A Broacast Algorithm for All-port Wormhole-Routed Torus Networks,” IEEE Transactions on Parallel Distributed Systems, Vol. 7, No. 8, pp. 876-885, August 1996.
[22] Jyh-Jong Tsay and Wen-Tsong Wang, “Nearly Optimal Algorithms for Broad-cast on d-Dimensional All-Port and Wormhole-Routed Torus,” IPPS/SPDP, 1998.
[23] Yu-Chee Tseng, “A Dilated-Diagonal-Based Scheme for Broadcast in a Worm-hole-Routed 2D Torus,” IEEE Transactions on Computers, Vol. 46, No. 8, August 1997.
[24] Yu-Chee Tseng, San-Tung Wang and Chin-Wen Ho, “Efficient Broadcasting in Wormhole-Routed Multicomputers: A Network-Partitioning Approach,” IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 1, January 1999.
[25] Nen-Chung Wang, Efficient Multicasting Strategies on Wormhole-Routed Star Graph and Irregular Networks, Doctor Dissertation, Computer Science and In-formation Engineering, National Cheng Kung University, Tainan, Taiwan, June 2002.
[26] San-Yung Wang and Yu-Chee Tseng, “Algebraic Foundations and Broadcasting Algorithms for Wormhole-Routed All-Port Tori,” IEEE Transaction on Com-puters, Vol. 49, No. 3, March 2000.
[27] Jie Wu, “A Distributed Formation of Orthogonal Convex Polygons in-Mesh-Connected Multicomputers,” Proceedings of International Parallel and Distributed Systems, April 2001.
[28] Jie Wu, “On Constructing the Minimum Orthogonal Convex Polygon in 2-D Faulty Meshes,” the 18th International Parallel and Distributed Processing Symposium (IPDPS), 2004.
[29] Junming Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic, 2001.
[30] Xiaotong Zhuang and Vincenzo Liberatore, “A Recursion-based Broadcast Paradigm in Wormhole Routed Mesh/Torus Netwroks,” Proceedings of the In-ternational Parallel and Disbuted Processing Symposium (IPDPS), 2002.