Some Fault-tolerant Routing Algorithms On Locally Twisted Cube Multicomputers

Multicomputers play an increasingly important role in high-performance computing. The reliability of the interconnection network employed in a multicomputer is a major concern. An interconnection network may fail to transfer information when some processors or links break down. How to improve interconnection network's reliability and assure smooth data transfer, even when the above-mentioned faults occur, that is, the establishment of a feasible fault-tolerant routing algorithm is made into a major concern in interconnection networks of multicomputers.As a newly topological structure of network, locally twisted cube is a variant of hypercube that retains many nice properties of hypercube such as connectivity, symmetry, recursive structure, Hamiltonicity, etc. Moreover it outperforms hypercube in terms of small network diameter as well as pancyclicity.This dissertation aims at the design of efficient fault-tolerant routing algorithms on locally twisted cubes. Three fault-tolerant routing algorithms are proposed, which are local information based, global information based and limited global information based, respectively. These algorithms are carefully compared.By analyzing the above fault-tolerant routing algorithms, the concepts of safety level and routing capability are introduced. We design a unicast fault-tolerant routing algorithm (algorithm A) and a broadcast fault-tolerant routing algorithm (algorithm B) in the case of node failure situation. And we design a unicast fault-tolerant routing algorithm (algorithm C) for the hybrid failure situation. Algorithms A and C utilize the recollection mechanism.Algorithm A routes messages along optimal paths by utilizing safety levels and the structure of locally twisted cube. But algorithm C routes messages by utilizing routing capability. Simulation experiments show that algorithms A and C have better fault-tolerant ability. As faulty nodes are more than half of the total number of nodes, algorithm A can still achieve a quite high percentage of successful routing. An additional advantage of the routing algorithm is that it is highly probable that the selected route be a shortest route between the associated nodes. When a lot of nodes and links break down simultaneously, algorithm C can also route messages successfully, and ensure an optimal unicasting or suboptimal unicasting. Specially, algorithm C displays better fault-tolerant routing ability when large numbers of faulty links appear. In...