Design and performance evaluation of migration-based submesh allocation strategies in mesh multicomputers

Abstract

The problem of processor allocation on mesh-based multicomputer systems is considered in this thesis. Three efficient schemes are proposed 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, employ the idea of fusing migration as a part of allocation to minimize fragmentation and the overall processing time of the tasks. Rigorous simulation experiments are performed based on practical workloads as reported in the literature to quantify all the proposed strategies. Based on the results, clear recommendations are made on the choice of the strategies.