Limit allocation: An efficient processor management scheme for hypercubes

Chansu Yu, C. R. Das

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations


Efficient task management in a hypercube multi-processor becomes difficult due to system overflow, where an incoming job cannot be allocated in spite of a sufficient number of free processors. Overflow occurs either due to the inability of recognizing a free subcube or due to external fragmentation. In this paper, we propose an allocation strategy that tries to scale down an incoming job size if it cannot fit into a fragmented hypercube. We call it limit allocation. We discuss three simple schemes, Limit-k, Greedy and Average. We conduct both analysis and simulation to characterize and compare various allocation policies. An M/M/m queueing model is developed to predict the behavior of buddy, free list and limit-k policies. The simulation study shows that the two adaptive schemes, greedy and average, outperform all other schemes reported so far in the literature.

Original languageEnglish (US)
Article number5727776
Pages (from-to)II143-II150
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1994
Event23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States
Duration: Aug 15 1994Aug 19 1994

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Hardware and Architecture


Dive into the research topics of 'Limit allocation: An efficient processor management scheme for hypercubes'. Together they form a unique fingerprint.

Cite this