Modern supercomputer schedulers on average may leave ~10% and sometimes as much as 30% of the computational resources idle. One possible approach to increase the load is to use an additional queue of low-priority jobs small enough to fit into the schedule gaps. We propose to use this approach for non-parallel jobs with arbitrary runtime wrapped in containers to allow them to be saved and migrated to other nodes or back to the queue. As a result, all the idle nodes can be used for computations. We also estimate the increase in average load and utilization efficiency that can be achieved using this approach.
Modern supercomputers use schedulers to allocate the computational resources. Despite the
substantial effort put into developing and improving scheduler algorithms, the average load of
supercomputers is often close to 90% and can be as low as 70% [
Besides further improving the scheduling algorithms, other approaches can be used to address the problem. One example is allowing the idle nodes to be used by additional low priority jobs that can be terminated whenever the scheduler assigns the node to a regular job. The example of this approach is the opportunistic use of idle Titan-2 resources by ATLAS [3].
Numerous problems can be solved by computations without parallelization so the corresponding jobs can use any available resource slot. However, many such jobs require substantial computation time and cannot fit into smaller gaps in the schedule. This problem can be solved by an efficient mechanism of saving the current state of a computational node and continuing computations from the saved state, possibly on a different node.
A variation of such mechanism, a live container migration, is implemented in several container virtualization platforms including OpenVZ [4] and Docker [5] (in Docker, live migration is currently available in experimental mode only).
We propose to increase the load of supercomputers by using an additional queue of nonparallel jobs wrapped in containers. Containers can be started very quickly and impose little to no overhead. Using the live migration tools containers can be saved and returned to the queue or migrated directly to other nodes before the allotted time is over. Assuming the minimal scheduler time slot is sufficient to start a container, perform some computations, and save it, the proposed approach potentially allows to use all the nodes left idle by the scheduler and increase the load to 100% of the available computational nodes. We are currently developing a prototype of the job management system implementing this approach.
Our proposed system will not eliminate the need for further improvements in scheduling algorithms: first, the containerized jobs that often need to be stopped and restarted reduce the computational nodes efficiency, and second, these jobs are presumed to have lower priority than the regular jobs. Conversely, improvements of the scheduling algorithms will reduce the effect of the proposed system but will not make it useless while the load remains substantially lower than 100%.
In the following section, we further discuss scheduling algorithms and find an estimate of the potential load increase resulting from our approach.
One of the commonly used basic scheduling algorithms is FCFS (First-Come First-Served) with backfilling [6]. The algorithm schedules the jobs in order of submission until the first job that cannot be started immediately. This job is then assigned a reservation at the earliest time slot when enough computational nodes become available, and the following jobs are only allowed to use these nodes if they are expected to finish before the reserved time. A number of variations and modifications have been proposed since the algorithm first appeared, and modern schedulers such as SLURM [7] allow to tune the algorithm using various optimization parameters.
Figure 1 illustrates the problem and the backfilling approach: jobs 4-7 cannot be started
immediately so they are scheduled to further slots, in some cases changing the execution order. As
illustrated by the job 7, the nodes executing the same job do not have to be adjacent, although some
schedulers allow to take locality into account. Note that the backfilling algorithm used in Figure 1
allocates multiple reservations. A variation of the algorithm that allocates reservations to all jobs is
called conservative backfilling [
All variations of backfilling algorithm require an estimate of job runtime. Some schedulers
require the estimate to be submitted by the user along with the number of requested computational
units, the other may attempt to predict the runtime based on the previous jobs by the user [
For our load estimate we used a simulation of a simple conservative backfilling algorithm. Job
dimensions were generated randomly based on approximated 2017 data from Lomonosov-1
supercomputer (average number of CPU slots 7.5, standard deviation 16.7, maximum 512; average
runtime 255 minutes, standard deviation 1204 minutes, maximum 15 days). For user runtime
estimates, we used a simplified model with a single parameter, prediction accuracy p. The model is
based on the observation [
The simulations were run for a supercomputer with 512 CPU slots and 180 days (with a time slot corresponding to one minute). The calculated values of average load l were averaged over 10 attempts. Figure 2 shows the simulation results.
If T=1 is the duration of a time slot used by the scheduler, t<1 is the combined time of starting and saving a containerized job, and c is the performance ratio between containerized and noncontainerized jobs, then the increase of average load from 90% to 100% due to the use of our proposed system corresponds to the increase of average utilization efficiency at least by 0.1(1-t)c of the peak efficiency.
This estimate assumes that all additional containerized jobs are only allowed to run for one time slot and must be saved before it is over regardless of the existing reservations. Alternative approach is allowing these jobs to run continuously and only saving and migrating them before the reservation by a regular job comes up. The potential downside of this approach is illustrated by the Figure 3: if job 4 terminates earlier than planned, job 7 can start earlier (or another job using 4 CPU slots and 1 time slot can be fit into the gap, if the job rescheduling is not allowed). But if the additional containerized jobs a1 and a2 are not saved by the end of the third time slot, they cannot be terminated without losing some progress. Similarly, a newly submitted job may be delayed if the nodes running containerized jobs do not have enough time to save the containers.
The work was supported by the Russian Foundation for Basic Research grant #18-37-00502 “Development and research of methods for increasing the performance of supercomputers based on job migration using container virtualization”. The authors would also like to thank Sergey Zhumatiy for useful discussions.
We proposed an approach to increase the average load of supercomputers using the container virtualization mechanisms. We also estimated the potential increase in average load resulting from this approach, and the corresponding increase in utilization efficiency. [2] Antonov A.S. et al. Examination of supercomputer system jobs flow dynamic characteristics // Computational methods and programming. 2013. V. 14, no. 4. pp. 104–108 (in Russian). [3] F. Barreiro Megino et al. [ATLAS Collaboration]. Integration of Titan supercomputer at OLCF with ATLAS Production System // J. Phys.: Conf. Ser. 2017. V. 898, no. 9. P. 092002. [4] http://openvz.org/ [5] https://docker.com/ [6] Lifka D. The ANL/IBM SP scheduling system // 1st Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP). Feitelson D.G., Rudolph L. (eds.). Springer-Verlag, Apr. 1995. Lect. Notes Comput. Sci. V. 949. pp. 295–303. [7] https://slurm.schedmd.com/