Processor allocation scheme for hypercube computers

Jong Kim, Chita R. Das, Woei Lin

Research output: Contribution to journalConference articlepeer-review

27 Scopus citations


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 (2k 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.

Original languageEnglish (US)
Pages (from-to)231-238
Number of pages8
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1989
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: Aug 8 1989Aug 12 1989

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this