Parallel Allocation Algorithms For Hypercubes And Meshes

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 \Theta( p 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 \Theta m \Theta \Delta \Delta \Delta \Theta m, we show how to find all submeshes of dimensions k \Theta k \Theta \Delta \Delta \Delta \Theta k, for all k m, in optimal \Theta(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 d..