Fragmentation-efficient node allocation algorithm in 2D mesh-connected systems

Efficient utilization of processing resources in a multicomputer system depends on the fast allocation algorithms that minimize system fragmentation. A small number of jobs with large submesh allocation requirements may significantly increase external fragmentation and the queuing delay of the rest of jobs. Under such circumstances, the proposed strategy further tries to allocate L-shaped submeshes instead of signaling the allocation failure. A simple and effective algorithm to find the allocatable L-shaped submeshes is proposed, that is shown to reduce the average turnaround time by minimizing the queuing delay, even though jobs are scheduled in an FCFS to preserve fairness. The extensive simulations show that the strategy performs more efficiently in terms of the task turnaround time and the system utilization.