An Efficient Submesh Allocation Scheme Based on Classified Free Submesh List and Task Relocation

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 task waiting time in two aspects, shortening submesh search time and reducing the submesh allocation delay caused by external fragmentation. This scheme classifies independent free submeshes by their types: square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh only from one list depending on the type of the given task, thus saving submesh searching time. If no suitable submeshes are found, it is most likely caused by external fragmentation. In such a case, our scheme relocates the tasks being executed to free submeshes and combines the newly available submesh with other fragmented ones to form a larger submesh. This allows allocation of the task, otherwise to be put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme helps reduce task waiting time and that it is by far more effective to reduce the submesh allocation delay caused by external fragmentation rather than to reduce submesh search time for reduction of the task waiting time.