Parallel Allocation Algorithms for Hypercubes and Meshes
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 Θ(dn1/d) time.
Since the number of subcubes in a hypercube of dimension d is 3d, 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.
parallel computing, subcube allocation, buddy system, cyclic buddy system,
submesh allocation, torus, parallel algorithm, resource allocation,
scheduling, computer science
|Copyright © 2005-2016 Quentin F. Stout|