In parallel computer systems with a number of processors, external fragment
ation is caused by continuous allocation and deallocation of processors to
tasks which require exclusive use of several contiguous processors. With th
is condition, the system may not be able to find contiguous processors to b
e allocated to an incoming task even with a sufficient number of free proce
ssors. Relocation is an approach for alleviating this problem by reassignin
g the running tasks to other processors. In this paper, we examine two relo
cation schemes-full relocation and partial relocation scheme-for two-dimens
ional meshes. The full relocation scheme is desirable when the system is hi
ghly fragmented, while the partial relocation scheme is used for minimizing
the number of relocated tasks. For the relocation process, we formally def
ine and use two basic submesh movement operations-shifting and rotating. Co
mprehensive computer simulation reveals that the proposed schemes are benef
icial when the relocation overhead is not high, which is machine dependent.
(C) 2000 Academic Press.