This paper examines the problem of locating large fault-free subcubes in
multiuser hypercube systems.
We analyze a new location strategy, the cyclic buddy system,
and compare 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, gray-coding,
folded hypercube, projective hypercube, scheduling, graph theory,
discrete mathematics, computer science
