Submesh Allocation in a Multitasking Distributed Shared Memory Multiprocessor
T. Liu, Weikang Huang, Fabrizio Lombardi, Laxmi Narayan Bhuyan · 2001
This paper proposes an efficient submesh allocation strategy based on a free list and compares the performance of the proposed strategy with all the existing strategies. The novel feature of the free list in the proposed scheme is its overlapped nature, i.e. free submeshes in the list may overlap each other. The trade-offs between an overlapping and non-overlapping free list for a mesh system are discussed. Allocation and deallocation algorithms are presented in this paper, both with a low complexity in O(N F ), where N F is the number of free submeshes in the free list. Extensive simulation results show that our approach is superior to all the previous strategies, yielding a lower waiting time and a substantial improvement in allocation time.