An Efficient Submesh Allocation Scheme for Mesh-connected Multicomputer Systems

Abstract

This paper presents a new submesh allocation scheme for mesh connected multicomputer systems, called CFSL-TR(Classified Free Submesh List-Task Relocation), which reduces submesh allocation delay in two aspects, shortening submesh search time and reducing the delay caused by external fragmentation. This scheme classifies independent free submeshes by submesh types; square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh for a task only from one list corresponding to the type of the given task, which is a subset of the free submeshes. If no suitable submeshes are found it is most likely due to external fragmentation. In such a case, our scheme relocates the tasks being executed to a free submesh and unifies the new available submesh with other fragmented submeshes to form a larger one. This allows allocation of the task, otherwise being put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme is efficient and that the submesh allocation delay caused from external fragmentation has bigger impact on the task waiting time than that of submesh search time.