A novel approach for subcube allocation in hypercube multiprocessors

A novel approach for dynamic subcube allocation in hypercube multiprocessors which supports a multiuser environment is proposed. A dynamic binary tree with nodes labeled by a binary reflected gray code is used for processor allocation along with two arrays of free lists. The time complexities for both allocation and deallocation are shown to be linear-orders of magnitude improvement over the existing exponential and even superexponential algorithms. A best-fit strategy, the proposed scheme does not excessively fragment the hypercube, unlike some existing strategies. In addition, static optimality is guaranteed. The performance of the proposed scheme is compared on such parameters as average delay in honouring a request, average allocation time, and average deallocation time against some existing schemes, demonstrating its effectiveness