FAULT-TOLERANT COMMUNICATION SCHEME FOR GLOBAL OPERATIONS IN HYPERCUBE SYSTEMS

Abstract

A non-fault tolerant communication scheme was originally proposed, which was shown to be very efficient for global operations and parallel algorithms execution on data residing in the processors of a hypercube multiprocessor. A complex problem is subdivided into independent subproblems, each of which can first be solved by one of the processors. Then, this communication scheme can be invoked to merge the subresults into the final results. Any algorithm for such decomposable, complex problems can benefit from this scheme. Recently, a fault-tolerant modification to this scheme was proposed which has two phases. In the first phase, an algorithm is devised to find a communication tree with as few faulty links as possible. This is the static fault-tolerance phase. In the second run time phase, data messages are routed dynamically, according to the link-fault pattern in the communication tree. In this dissertation, both the original and fault-tolerant scheme are first implemented and their performance is monitored. Next, slight modifications are made in both phases to improve the success rate of the global operations in the face of increasing link failures. Finally node failures are also included. The implementation is done in C language on the TATA ELXSI RISC System under UNIX environment.