Slot Selection and Co-allocation for Economic Scheduling in Distributed Computing

P. 368–383.

Toporkov V. V., Toporkova A. S., Tselishev A., Yemelyanov D. M., Bobchenkov A. V.

In this paper, we present slot selection algorithms for batch scheduling in distributed computing with non-dedicated resources. Jobs are parallel applications and these applications are independent. Existing approaches towards resource co-allocation and job scheduling in economic models of distributed computing are based on search of time-slots in resource occupancy schedules. A launch of  a parallel job requires a co-allocation of a specified number of slots. The sought time-slots must match requirements of necessary span, computational resource properties, and cost. Usually such scheduling methods consider only one suited variant of time-slot set. This paper discloses a scheduling scheme that features multi-variant search. Two algorithms of linear complexity for search of alternative variants are proposed. Having several optional resource configurations for each job makes an opportunity to perform an optimization of execution of the whole batch of jobs and to increase overall efficiency of scheduling.

Keywords: планирование, задание, scheduling, job, slot, resource request, task, согласованное распределение ресурсов, слот, ресурсный запрос, задача, co-allocation, batch

In book

Proceedings of the 11th International Conference on Parallel Computing Technologies

Vol. 6873. , Berlin, Heidelberg: Springer, 2011.