Effects of Allocation Request Shape Changes on Performance in 2D Mesh-Connected Multicomputers

Contiguous allocation in multicomputers is useful for security and accounting reasons. In mesh-connected systems, it allocates each job 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 two-dimensional mesh-connected multicomputers, where several common communication patterns are simulated in detail. The simulation results 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 46% in terms of average job turnaround time.