On the Performance of Job Scheduling for Noncontiguous Allocation in 2D Mesh-connected Multicomputers

The performance of non-contiguous allocation can be significantly affected by the job scheduling strategy used for determining the order in which jobs are selected for execution. In this paper, the performance of the well-known Greedy Available Busy List (GABL) non-contiguous allocation strategy for 2D mesh-connected multicomputers is re-visited considering several important job scheduling strategies. These are the First-Come-First-Served (FCFS), Out-of-Order (OO), and Window-Based job scheduling strategies. They are compared using detailed flit-level simulations. Extensive simulation results based on synthetic and real workload models indicate that the Window-Based job scheduling strategy exhibits good performance when the scheduling window size is large and heavy system loads. In particular, it is substantially superior to FCFS in terms of system utilization and average job turnaround times under medium to heavy system loads. Also, it is superior to Out-of-Order scheduling in terms of maximum job waiting delays. Window-Based job scheduling can improve both overall system performance and fairness (i.e., maximum job waiting delays) by adopting a large job scheduling window.