PROCESSOR ALLOCATION IN HYPERCUBE MULTICOMPUTERS - FAST AND EFFICIENTSTRATEGIES FOR CUBIC AND NONCUBIC ALLOCATION

A new approach for dynamic processor allocation in hypercube multicomp uters which supports a multi-user environment is proposed. A dynamic b inary tree is used for processor allocation along with an array of fre e lists. Two algorithms are proposed based on this approach, capable o f efficiently handling cubic as well as noncubic allocation. Time comp lexities for both allocation and deallocation are shown to be polynomi al, a significant improvement over the existing exponential and even s uper-exponential algorithms. Unlike existing schemes, the proposed str ategies are best-fit strategies within their search space. Simulation results indicate that the proposed strategies outperform the existing ones in terms of parameters such as average delay in honoring a reques t, average allocation time, average deallocation time, and memory over head.