**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

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

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

Full paper (PDF)

Other papers in parallel computing

Overview of work on parallel computing

Copyright © 2005-2016 Quentin F. Stout |