On Task Relocation in Two-Dimensional Meshes

Journal of Parallel and Distributed Computing 60, pp. 616-638, May 2000 (SCI, IF 0.729)

Seong-Moo Yoo, Hyunseung Choo, Hee Yong Youn, Chansu Yu, and Younghee Lee


In parallel computer systems with a number of processors, external fragmentation is caused by continuous allocation and deallocation of processors to tasks which require exclusive use of several contiguous processors. With this condition, the system may not be able to find contiguous processors to be allocated to an incoming task even with a sufficient number of free processors. Relocation is an approach for alleviating this problem by reassigning the running tasks to other processors. In this paper, we examine two relocation schemes—full relocation and partial relocation scheme—for two-dimensional meshes. The full relocation scheme is desirable when the system is highly fragmented, while the partial relocation scheme is used for minimizing the number of relocated tasks. For the relocation process, we formally define and use two basic submesh movement operations—shifting and rotating. Comprehensive computer simulation reveals that the proposed schemes are beneficial when the relocation overhead is not high, which is machine dependent.



external fragmentation, full and partial relocation scheme, mesh-connected systems, task allocation and deallocation, task relocation


View Full Text