On Task Relocation in Two-Dimensional Meshes

Abstract

In parallel computer systems with a number of processors, externalfragmentation is caused by continuous allocation and deallocation of proces-sors to tasks which require exclusive use of several contiguous processors.With this condition, the system may not be able to find contiguous proces-sors to be allocated to an incoming task even with a sufficient number of freeprocessors. Relocation is an approach for alleviating this problem byreassigning the running tasks to other processors. In this paper, we examinetwo relocation schemesfull relocation and partial relocation schemefortwo-dimensional meshes. The full relocation scheme is desirable when thesystem is highly fragmented, while the partial relocation scheme is usedfor minimizing the number of relocated tasks. For the relocation process, weformally define and use two basic submesh movement operationsshiftingand rotating. Comprehensive computer simulation reveals that the proposedschemes are beneficial when the relocation overhead is not high, which ismachine dependent.