On submesh allocation for mesh multicomputers: A best-fit allocation and a virtual submesh allocation for faulty meshes

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 for mesh-connected multiprocessor systems. The proposed strategy maintains and uses a free submesh list for an efficient allocation. For an allocation request, the strategy selects the best-fit submesh which causes the least amount of potential processor fragmentation. As many large free submeshes as possible are preserved for later allocations. For this purpose, we introduce a novel function quantifying the degree of potential fragmentation of submeshes. The proposed strategy has the capability of recognizing a complete submesh. We also propose an allocation strategy for faulty meshes which can maintain and allocate virtual submeshes derived from faulty submeshes. Extensive simulation is carried out to compare the proposed strategy with previous strategies. The proposed strategy has the best performance: a 6 - 50 percent improvement over the previous best strategy.