FAULT-TOLERANT MESSAGE ROUTING IN THE EXTENDED HYPERCUBE

In real-time computing applications, it is important to have parallel computing systems that not only exhibit high performance but also cont inue to perform reliably under faulty conditions. The hypercube is one of the most popular and robust network topologies used for building d istributed memory message passing multiprocessor systems. However, the hypercube does not have a constant building block and it is difficult to build hypercubes of large dimensions on account of the logarithmic degree of connectivity. The extended hypercube architecture exhibits such good properties as constant degree of node, low diameter and a co nstant basic building block. In addition it has a hierarchical; recurs ive and highly scalable structure. The extended hypercube is also robu st to link faults. However the extended hypercube suffers from poor fa ult-tolerance to node faults as it has articulation points. In this pa per we present a fault-tolerant variation of the extended hypercube, t he extended hypercube with symmetrical connections. The latter topolog y retains all the positive features of the former and in addition exhi bits improved fault-tolerant characteristics. We design efficient faul t-tolerant routing algorithms for the extended hypercube architectures and report simulation results.