Free submesh list strategy: A best fit submesh allocation 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. 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 proposed strategy tries to allocate a best-fit submesh which causes the least amount of potential processor fragmentation so as to reserve the large free submeshes as many as possible 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 the proposed strategy with the previous strategies and it is shown that the proposed strategy exhibits the best performance. © World Scientific Publishing Company.