Improving System Performance in Non-Contiguous Processor Allocation for Mesh Interconnection Networks

Contiguous allocation of parallel jobs in multicomputers usually suffers from the degrading effects of fragmentation, because it requires that the allocated processors be contiguous and have the same topology as that of the multicomputer?s interconnection network. Fragmentation can be avoided by adopting non-contiguous allocation. However, non-contiguous allocation can increase the distances among processors allocated to a job, which can increase the interference among messages of different jobs and increases message contention and delays. This paper suggests a new non-contiguous processor allocation strategy, referred to as Minimum Interference Paging (MIP), for the 2D mesh network. MIP attempts to reduce the distances among processors allocated using a paging variant that chooses a set of processors with the lowest distance between the first and last allocated processors, where the distance is the number of processors between the first allocated node and last allocated node. Using software simulation, we compared the performance of MIP against that of several well-known non-contiguous allocation strategies: Paging (0), Multiple Buddy System (MBS) and Adaptive Non-contiguous Allocation (ANCA). The comparative evaluation was conducted using First-Come-First-Served (FCFS) job scheduling, wormhole routing and six communication patterns. These are the One-to-All, All-to-All, Near Neighbour, Ring, Divide and Conquer Binomial Tree (DQBT), and Random communication patterns. The results show that MIP exhibits superior performance in terms of average turnaround time of jobs.