In Proc. 6th Distributed Memory Computing Conf. (1991), IEEE, pp. 34-41.

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

Marilynn Livingston
Dept. of Computer Science, Southern Illinois University at Edwardsville

Quentin F. Stout
EECS Department, University of Michigan

Abstract: 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

Full paper (Postscript)
Full paper (PDF)
Other papers in parallel computing
Overview of work on parallel computing

Quentin's Home Copyright © 2004-2016 Quentin F. Stout