On the best fit submesh allocation strategy in mesh-connected multicomputers

Abstract

The submesh allocation problem is to recognize and locate a free submesh that can accommodate a request for a submesh of a specified size. An efficient submesh allocation strategy is required for achieving high performance on mesh multicomputers. In this paper, we propose a new best fit submesh allocation strategy. The proposed strategy maintains and uses a free submesh list to get global information for free submeshes. For an allocation request, the strategy tries to allocate a best fit submesh which causes the least amount of potential fragmentation so as to preserve the large free submeshes to be as many as possible and to prevent processor fragmentation for later requests. For this purpose, we introduce a novel function for quantifying the degree of potential fragmentation of submeshes. The proposed strategy has the complete submesh recognition capability. Extensive simulation is carried out to compare it with the previous strategies, and experimental results indicate that it exhibits the best performance along with an about 30% average improvement over the previous best strategy.