Parallel Advance Reservation-based Backfill Scheduling Optimization Model And Algorithm

Grid resource management plays an important role while enabling the sharing and coordinating of resources in Grid computing environments. Advance reservation is an important part of grid resource reservation mechanism. An advance reservation is a scheduling object which reserves a group of resources for a particular timeframe for access only by a specified entity or group of entities. With the development of high performance of computing, signal processor, due to the limit of computing speed, cannot meet the requirement of applications with higher computing speed. Nothing but parallel processors can provide service for applications such as large-scale computing projects and real-time required applications, which highlighted the importance of parallel scheduling.Based on the existing grid resource management and scheduling technologies, I studied scheduling algorithms, Easy backfill and Conservative backfill, which are massively used in parallel scheduling.In this paper, new backfill algorithm and backfill reservation algorithm are proposed, and an optimization model, two-dimensional packing model, is raised correspondingly.Both Easy Backfill and Conservative Backfill algorithms include backfill strategy and backfill reservation method. Existing backfill strategies only consider one job for every backfill,never considered the combination of multiple jobs, and did not consider the current available resources match with the backfill jobs.In this paper, for the inadequate of existing backfill algorithms, a newly designed backfill algorithm, JCO, is proposed. This backfill algorithm selects multiple jobs for every backfill, and selects jobs for resources based on the size of current free resource. The existing backfill reservation policy chose the earliest time to execute jobs which will fragment resources greatly and reduce system utilization rate. To change this situation, a new backfill reservation algorithm, OSTP, is proposed which take full account of backfill operation on free resources and always choose the best time to reserve resources for jobs.Experiments proved the feasibility of backfill algorithms, and show the impacts of reservation depth on resource utilization, average waiting time and average slowdown of jobs. We can compare the difference of different backfill strategies in different performance parameters.