DEADLOCK-FREE FAULT-TOLERANT MESSAGE PASSING ROUTING IN HYPERCUBE MULTIPROCESSOR SYSTEM

Abstract

Among the commercially available multiprocessor systems, the hypercube( also known as n cube, cosmic cube-or boolean cube) stands out as one of the most attractive and versatile, with a vast rangeof applications. This work is mainly concerned with the routing problems faced in a hypercube system when one or more nodes(processing elements) are faulty. To eliminate the impact of faults some routing algorithms have been proposed. One routing algorithm "e-cube routing" has been described for the nonfaulty system. Due to the faulty nodes in the system, there may be some chances of deadlock in the routing. To make the routing paths deadlock proof some algorithms has been proposed, which can support the routing upto the certain limit of fault without the fear of deadlock occurrence. The concept of virtual channels has been studied. These virtual channels which exist on a physical channel are used in sending messages from one node to another node, so that there is no cyclic dependency between the channel dependence graph which is a necessary criteria for the deadlock occurrence. One switching technique which uses these virtual channels has been-described and implemented with some adaptive routing techniques to make routing deadlock free. The proposed routing scheme use either wormhole routing or staged routing, depending on the availability of the one or more nonfaulty n-2 cube where n-cube is the main structure.