Fault Tolerance of the Cyclic Buddy Subcube Location Scheme in Hypercubes (Preliminary Version)

This paper examines the problem of locating large faultfree subcubes in multiuser hypercube systems. We analyze a new location strategy, the cyclic buddy system, andcompare its performance to the buddy system, the gray-coded buddy system, and several variants of them. We show that the cyclic buddy system gives a striking improvement in expected fault tolerance over the above schemes and, since it can easily be implemented in parallel with little overhead, it provides an attractive alternative to these schemes. We also investigate the behavior of these location systems in the folded, or projective, hypercube, and find that the cyclic buddy system, which adapts naturally to this enhancement, significantly outperforms the other schemes. A combination of analytic techniques and simulation is used to examine both worst case and expected case performance. Keywords fault tolerance, subcube location, subcube allocation, hypercube computer, buddy system, graycoded system, folded hypercube.