A Top-Down Processor Allocation Scheme for Hypercube Computers

This paper presents an efficient processor allocation policy for hypercube computers. 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 or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is not only statically optimal as 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 average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. Finally, the extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given. Index Terms—Buddy strategy, free list, gray code, hypercube, modified buddy strategy, processor allocation, processor deallocation, subcube recognition.