Research Of Fault-Tolerant Routing For Mesh Multicomputer

Large-scale multicomputers play a central role in high-performance computing. The processors of a multicomputer work collaboratively in solving computation -intensive problems. For this purpose, it is essential to communicate data between processors via an interconnection network. Indeed, the performance of a multicomputer heavily depends on the effectiveness of the associated interconnection network. This thesis deals with the design of unicast routing algorithm, which requires that a data be sent from a source node to a destination node.With the increasing number of processors in a multicomputer, it becomes much likely that there exist faulty nodes in the system. The so-called fault-tolerance of a multicomputer means its capability of working properly in the presence of faulty processors. The design of fault-tolerant routing algorithm is an important issue in fault-tolerant computing as well as parallel computing.Mesh is a popular network topology employed in multicomputers. A mesh has a modular and scalable connecting pattern, which makes it suitable for VLSI implementation. Indeed, some commercial multicomputers admit mesh-structured interconnection network. This thesis investigate the fault-tolerate unicast routing strategy on mesh structure.After introducing the basic knowledge on fault-tolerate routing and describing a necessary and sufficient condition for minimal routing on 2D mesh, a new fault-tolerate routing algorithm on mesh is presented. By introducing the concept of the region of minimal paths, the proposed algorithm can find a shortest route, if it exists; this is especially the case for a particular fault pattern. Then, the proposed algorithm is improved by incorporating the extended safety levels.The above mentioned necessary and sufficient condition is generalized to include 3D mesh. Then a fault-tolerant routing algorithm on 3D-mesh is advised, which is adaptive. Apart from this, this algorithm can find a shortest route from the source to the destination, if it is existent.