FAULT-TOLERANT WORMHOLE ROUTING IN TWO DIMENSIONAL MESHES

Abstract

Direct networks have been a popular means to construct parallel computers.A direct network has channels directly connecting each node to only a few of its neighbors. Four switching techniques have been used in direct networks: store-and-forward, circuit switching ,v irtual cut-through and wormhole routing.In wormhole routing a packet is divided into a number of flits for transmission. The header flit of a packet governs the route.As the header advances along the specified route, the remaining flits follow in a pipeline fashion.If the header flit encounters a channel already in use, it is blocked until the channel becomes available. Most techniques for making wormhole routed meshes fault tolerant, have been based on adding virtual channels to the networks. The negative first routing algorithm is known for producing systems that are dead-lock free, very adaptive, minimal or non-minimal for direct networks. In this dissertation, the negative first routing algorithm, for 2-dimensional meshes without virtual channels, is modified to make it one-fault tolerant. The performance of the one-fault tolera :. _nt algorithm is compared with the performance of the negative-first routing algorithm in a 8x8 mesh network. The programe is written in C and is 3900 lines long. It runs on UNIX system.