On task relocation in two-dimensional meshes

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.