Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.parco.2008.03.009
Title: Design and performance evaluation of combined first-fit task allocation and migration strategies in mesh multiprocessor systems
Authors: Goh, L.K.
Veeravalli, B. 
Keywords: First-fit task allocation
Fragmentation reduction
Mesh multiprocessors
Processor allocation
Task migration
Issue Date: Sep-2008
Source: Goh, L.K., Veeravalli, B. (2008-09). Design and performance evaluation of combined first-fit task allocation and migration strategies in mesh multiprocessor systems. Parallel Computing 34 (9) : 508-520. ScholarBank@NUS Repository. https://doi.org/10.1016/j.parco.2008.03.009
Abstract: In this paper, we consider the problem of processor allocation on mesh-based multiprocessor systems. We employ the idea of using migration to minimize fragmentation and the overall processing time of the tasks. In our schemes, we consider the use of task migration whenever required to improve the problem of fragmentation. To this end, we propose three efficient schemes to improve the performance of first-fit allocation strategies commonly used in practice. The first scheme, called the first-fit mesh-bifurcation (FFMB) scheme, attempts to start the search for a free submesh from either the bottom-left corner or the top-left corner of the mesh so as to reduce the amount of fragmentation in the mesh. The next two schemes, called the online dynamic compaction-single corner (ODC-SC) and online dynamic compaction-four corners (ODC-FC) schemes, use task migration to improve the performance of existing submesh allocation strategies. We perform rigorous simulation experiments based on practical workloads as reported in the literature to quantify all our proposed schemes and compare them against standard schemes existing in the literature. Based on the results, we make clear recommendations on the choice of the strategies. © 2008 Elsevier B.V. All rights reserved.
Source Title: Parallel Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/55553
ISSN: 01678191
DOI: 10.1016/j.parco.2008.03.009
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

22
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 17, 2017

Page view(s)

49
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.