A new window-based job scheduling scheme for 2D mesh multicomputers

作者：Ababneh Ismail; Bani Mohammad Saad^*

来源：Simulation Modelling Practice and Theory, 2011, 19(1): 482-493.

DOI：10.1016/j.simpat.2010.08.007

• Job scheduling
• Mesh
• Multicomputer
• Contiguous submesh allocation
• Average turnaround time
• Maximum waiting delay

Allocating submeshes to jobs in mesh-connected multicomputers in a FCFS fashion can lead to poor system performance (e g long job waiting delays) because the job at the head of the waiting queue can prevent the allocation of free submeshes to other waiting jobs with smaller submesh requirements However serving jobs aggressively out-of-order can lead to excessive waiting delays for jobs with large allocation requests In this paper we propose a scheduling scheme that uses a window of consecutive jobs from which it selects jobs for allocation and execution This window starts with the current oldest waiting job and corresponds to the lookahead of the scheduler The performance of the proposed window-based scheme has been compared to that of FCFS and other previous job scheduling schemes Extensive simulation results based on synthetic workloads and real workload traces indicate that the new scheduling strategy exhibits good performance when the scheduling window size is large In particular it is substantially superior to FCFS in terms of system utilization average job turnaround times and maximum waiting delays under medium to heavy system loads Also it is superior to aggressive out-of-order scheduling in terms of maximum job waiting delays Window

• 出版日期2011-1