Allocation Algorithms for Mesh-Connected and Hypercube Computers

In Proceedings 4th Conference on Hypercubes, Concurrent Computers, and Applications (1989), pp. 59-66.

Parallel Allocation Algorithms for Hypercubes and Meshes
Preliminary Version

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

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: We consider the problem of subsystem allocation in the mesh, torus, and hypercube multicomputers. Although the usual practice is to use a serial algorithm on the host processor to do the allocation, we show how the free and non-faulty processors can be used to perform the allocation in parallel. The algorithms we provide are dynamic, require very little storage, and work correctly even in the presence of faults.

For the 2-dimensional mesh and torus with n processors, we give an optimal Θ(sqrt(n)) time algorithm which identifies all rectangular subsystems that are not busy and not faulty. For the d-dimensional mesh and torus of size n=m x m x . . . x m, we show how to find all submeshes of dimensions k x k x . . . x k, for all k <= m, in optimal Θ(dn^1/d) time.

Since the number of subcubes in a hypercube of dimension d is 3^d, the current practice is to allocate only a fraction of the possible subcubes, which degrades the fault tolerance and dynamic allocation ability of the system. We consider two approaches to this problem. In one approach, we limit the dimensions of the subcubes to be allocated, and show, for fixed q, how to determine all non-faulty and non-busy subcubes of dimension d-q in a hypercube of dimension d in time Θ(d). The second approach involves allocating only a subset of the possible subcubes in all dimensions. We give optimal parallel algorithms for implementing several previously suggested allocation schemes of this type, including single and multiple versions of buddy, Gray-coded-buddy, and k-cube buddy systems. The parallel versions of these are significantly faster than the known serial allocation algorithms, and they provide a significant improvement in the fault tolerance of the system. We also introduce a new allocation system, the cyclical buddy system, which has a simple, efficient parallel implementation but which does not naturally arise as a serial allocation system.

Keywords: parallel computing, subcube allocation, buddy system, cyclic buddy system, submesh allocation, torus, parallel algorithm, resource allocation, scheduling, computer science

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