Processor allocation scheme for hypercube computers

A processor allocation policy for hypercube computers is presented. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2^k nodes) is allocated by finding a free subcube of dimension k. The free list policy is different from other hypercube allocation schemes in that it uses a top-down allocation rule in contrast to the bottom-up approach used by all other allocations. This new policy is compared with the buddy, the gray code, and the modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is statically optimal, as are the other policies, but it gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as the time complexity, average delay, and system utilization, is compared with those of the other schemes, demonstrating its effectiveness.