Adaptive Routing Techniques for High Reliability in Multiprocessor Interconnection Networks

Abstract

Massively parallel distributed memory multiprocessors (multicomputers) are increasingly being used in applications which demand high performance. These include real time applications in defence, robotics. Since massively parallel computers are also inherently less reliable due to the large number of components involved, it becomes essential to ensure reliable communication between nodes through fault tolerant routing algorithms. Conventionally, routing algorithms for multicomputers have concentrated on achieving minimality ie routing the message through a shortest path between the source and destination. In a safety-critical application, routing algorithms must be deadlock-free, be tolerant to node faults and link faults, and be capable of handling congestion resulting from non-uniform traffic. In this paper, we have made a survey of the adaptive routing techniques on direct interconnection networks.