FREE DIMENSIONS - AN EFFECTIVE APPROACH TO ACHIEVING FAULT-TOLERANCE IN HYPERCUBES

Hypercube network is an attractive structure for parallel processing d ue to its symmetry and regularity, In this paper, we use the concept o f free dimensions to achieve fault tolerance in hypercubes without req uiring additional spare processing nodes; such additional redundancy r equires modification of hypercube structure. A free dimension is defin ed to be a dimension across which both end nodes are not faulty. Given an n-dimensional hypercube, (Qn), and a set of f less than or equal t o n faulty nodes, we present an efficient algorithm to find free dimen sions, and show that at least n - f + 1 free dimensions exist. Free di mensions can be used to partition (Qn) into subcubes such that each su bcube contains at most one fault. Such a partitioning helps in achievi ng fault tolerance via emulation, embedding, reconfiguration. It also helps in designing efficient routing and broadcasting algorithms in fa ulty hypercubes.