PERFORMANCE STUDY OF FAULT-TOLERANT UNICASTING SCHEMES IN HYPER CUBE MULTICOMPUTERS

Abstract

Hypercube multicomputers have been one of the commonly used topological structures for distributed memory systems due to their regular structure and low diameter.. Efficient interprocessor communication is a key to the performance.. of a Hypercube system. Unicast is a one to one communication between a source and destination. As the number of processors in a Hypercube system increases, the probability of. processor failure also increases. There have been a number of fault tolerant unicasting schemes proposed in rpckst. In this . dissertation, three fault tolerant unicasting schemes RUN, RSL and MRSL have been discussed and implemented. RUN algorithm uses the concept of unsafe node and degree of unsafeness for classifying the unsafe nodes. This algorithm provides a feasible path of length no more than the Hamming distance between the source and the destination plus four as long as the number of faulty nodes in n-cube is no more than n-1. RSL and MRSL use the concept of safety , level which is an approximated measure of the number and distribution of faulty nodes in the neighborhood. These algorithms provide a feasible path of length no more than the Hamming distance between the source and the destination plus two as long as the number of faulty nodes in an n-cube is no more than n-1. These two _algorithms can also be used in disconnected Hypercubes and Hypercubes with both faulty nodes and links.