Please use this identifier to cite or link to this item:
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
Citation: 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.
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
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.


checked on Feb 13, 2019


checked on Feb 4, 2019

Page view(s)

checked on Feb 2, 2019

Google ScholarTM



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