ON THE BEST FIT SUBMESH ALLOCATION STRATEGY IN MESH-CONNECTED MULTICOMPUTERS

The submesh allocation problem is to recognize and locate a free subme sh that can accommodate a request for a submesh of a specified size. A n efficient submesh allocation strategy is required for achieving high performance on mesh multicomputers. In this paper, we propose a new b est fit submesh allocation strategy. The proposed strategy maintains a nd uses a free submesh list to get global information for free submesh es. For an allocation request, the strategy tries to allocate a best f it 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 purpo se, we introduce a novel function for quantifying the degree of potent ial fragmentation of submeshes. The proposed strategy has the complete submesh recognition capability. Extensive simulation is carried out t o compare it with the previous strategies, and experimental results in dicate that it exhibits the best performance along with an about 30% a verage improvement over the previous best strategy.