PERFORMANCE STUDY OF FAULT - TOLERANT WORMHOLE ROUTING - STRATEGIES IN HYPERCUBE MULTICOMPUTERS

Abstract

Hypercube multicomputers are becoming very popular due to their regular structure and low diameters, making them well suited for parallel processing. In such multicomputer systems efficient communication among the processors is critical to the performance of the system. Hence routing of messages is an important issue that needs to be addressed, especially in the presence of faulty nodes. A variety of routing strategies have been proposed in the past. In this dissertation, four fault-tolerant routing strategies have been discussed and implemented. These include Adaptive, non-adaptive, deadlock free and deadlock prone. Their performance has been evaluated in the fault-free as well as in injured Hypercubes. Non-faulty characteristics are compared with standard, oblivious E-CUBE routing. Deadlock freeness has been implemented with the use of virtual channels. For simulation, popular wormhole routing with virtual channels is considered as underlying switching technology. The fully menu-driven program, written in C language is around 3,000 lines and runs on TATA ELXI system, under IRIX operating system.