A fast and efficient strategy for submesh allocation in mesh-connected parallel computers

A new approach for dynamic submesh allocation in mesh-connected multiprocessor system, which supports a multi-user environment, is proposed. The proposed strategy effectively prunes the search space by searching for free submeshes on the corners of allocated submeshes along with the corners of the mesh system. A submesh is selected with the potential of causing the least amount of fragmentation in the system. The proposed strategy possesses complete submesh recognition capability; it is a best-fit strategy, as well. Existing strategies do not provide this combination of capabilities. The deallocation time and memory overhead is shown to be constant in that it does not grow with the size of the mesh. Simulation results indicate that the proposed strategy outperforms the existing ones in terms of parameters such as average delay in honoring a request, standard deviation of the delays, average allocation time, average deallocation time, and the amount of memory required