On Task Relocation in Two-Dimensional Meshes

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 391
  • Download : 2
In parallel computer systems with a number of processors, external fragmentation 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 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 schemesfull relocation and partial relocation schemefor 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 operationsshifting and rotating. Comprehensive computer simulation reveals that the proposed schemes are beneficial when the relocation overhead is not high, which is machine dependent.
Publisher
Elsevier
Issue Date
2000
Keywords

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

Citation

Journal of Parallel and Distributed Computing, Vol.60, pp.616-638

DOI
10.1006/jpdc.1999.1604
URI
http://hdl.handle.net/10203/20897
Appears in Collection
CS-Journal Papers(저널논문)

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0