Fault-tolerant ring- and toroidal mesh-connected processor arrays able to enhance emulation of hypercubes

An advanced spare-connection scheme for K-out-of-N redundancy is proposed f or constructing fault-tolerant ring- or toroidal mesh-connected processing- node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring o r 32-node toroidal mesh, can be constructed by using bypass links with a se gmented bus structure to selectively connect the primary nodes to a spare n ode in parallel. These bypass links are allocated to the primary nodes by g raph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain stro ng fault tolerance for reconfiguring the base array with the primary networ k topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by usi ng external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-conne ctions of sub-hypercubes whose diameter is smaller than that of the regular hypercube.