The effect of communication on the performance of allocation request shape changes in 2D mesh-connected multicomputers

Contiguous allocation in multicomputers is useful for security and accounting reasons. In mesh-connected systems, each job is allocated an exclusive submesh of processors, and the allocated submesh has the same shape and size as that requested by the job. Because of this size and shape constraint, contiguous allocation typically suffers from high processor fragmentation. Processor fragmentation can be reduced by considering contiguous allocation to all possible request shapes, while maintaining contiguity. However, request shape modification can influence communication overhead. In this paper, we study the effect of request shape modification on communication overhead and performance in 2D mesh-connected multicomputers, where several common communication patterns are simulated in detail. The simulation results based on both synthetic and real workload models show that permitting all request shape changes can improve system performance substantially. For example, it improves the performance of first-fit allocation by up to about 60% in terms of average job turnaround time.