Limit Allocation: an Eecient Processor Management Scheme for Hypercubes 1

Abstract

EEcient task management in a hypercube multiprocessor becomes diicult due to system overrow, where an incoming job cannot be allocated in spite of a suucient number of free processors. Overrow occurs either due to the inability of recognizing a free subcube or due to external fragmentation. Previous research has been devoted to enhance the subcube recognition ability, but the consequent performance improvement is not signiicant. Alternatively, task migration and diierent job scheduling disciplines like scan and lazy have been proposed to boost the hypercube performance. Despite the performance enhancement, however, they either incur tremendous overhead or violate the fairness rule. In this paper, we propose an allocation strategy that tries to scale down an incoming job size if it cannot t 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. Simulation study shows that the two adaptive schemes, greedy and average, outperforms all other schemes reported so far in literature.

Topics

0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)