Plan-based Job Scheduling for Supercomputers with Shared Burst Buffers

We start with an illustrative example of how a burst buffer reservation may impact the FCFS EASY-backfilling schedule. Suppose we are executing jobs as defined by Table 1 on a small cluster with 4 nodes (denoted by CPUs) and 10 TB of shared burst buffer storage. For simplicity, walltime of each job is equal to its runtime (perfect user runtime estimates). The BB column denotes the total amount of burst buffer requested by a job. The scheduler runs periodically at every minute. The first iteration of scheduling starts at time 0 and also includes jobs submitted at time 0. For comparison of algorithms, we present how this set of jobs would be scheduled by EASY-backfilling without (Fig. 2) and with (Fig. 2) burst buffer reservations. Filled rectangles represent started jobs; stripped represent future FCFS reservations.

Let us focus our attention on job 3. Fig. 2 shows the schedule created by the backfilling without burst buffer reservations. At the time 0 (top-left), two jobs are submitted and started immediately. After a minute (top-right), job 3 is submitted, but there are not enough available processors to start it. Concerning only CPUs, jobs 1 and 3 would be able to run in parallel after the completion of job 2. However, their summarised burst buffer requirements exceed the total capacity of 10 TB available in the cluster. As the standard EASY-backfilling does not consider burst buffers in scheduling, it would schedule job 3 just after job 2. At time 2 (middle-left), job 4 is submitted. Despite having enough free processors and burst buffers, it cannot be launched instantly as it would delay job 3, which is at the front of the waiting queue and hence received a reservation of 3 CPUs for the time period 4-5. The same situation applies to job 5, which given the resources, could be backfilled in place of job 3, but would then delay its scheduled execution. It is not the case for job 6, which can be backfilled before job 3. An unusual situation happens at time 4 (bottom-left). Job 3 does not have enough burst buffers to start the execution and prevents all other jobs from starting. It causes most of the processors in the cluster to remain idle until the completion of job 1. Indeed, job 3 behaves like a barrier in the scheduling of other jobs. The last time step presents the moment just after the completion of job 1. Job 3 is finally able to start. Additionally, job 7 is backfilled ahead of jobs 4 and 5 as it has enough processors and burst buffers to start immediately.

Fig. 2 shows how FCFS EASY-backfilling with burst buffer reservations schedules the same set of jobs. The first difference from the previous algorithm appears at time step 1. Although the newly arrived job 3 cannot start at that time, its burst buffer requirements are recognised and it is scheduled after job 1 completes. Thus, job 4 can start immediately when submitted, as it will not delay job 3. At time 4, all the new jobs 5, 6, 7, 8 can be backfilled ahead of job 3. Lastly, at time 10, there are only left jobs 3 and 7.

Although this example may seem artificial, it distils the problem we observed when simulating a larger set of jobs (see Fig. 3).

In this section, we show how to extend EASY-backfilling with burst buffer reservations. Algorithm 1 shows the pseudocode of EASY-Backfilling. Jobs in the waiting queue $Q$ are stored in the order of arrival. At the beginning, the algorithm attempts to launch jobs according to FCFS policy until the first job $J$ for which there are not enough free resources (processors or burst buffers). The reservation for processors is acquired for $J$ at the earliest possible time in the future. Next, the remaining jobs in $Q$ are backfilled ahead of $J$ under the condition that they would not delay the scheduled execution of $J$.

The standard EASY-Backfilling does not include the part presented in the square brackets (line 14). This minor change—a future reservation of burst buffers together with processors prior to the backfilling process—solves the problem presented in the example in Section 3.1.

In principle, Slurm implements conservative backfilling. However, there is an issue in Slurm implementation of burst buffer support, which could possibly lead to starvation of jobs with burst buffer requirements. Slurm allows to delay a job requesting burst buffer if it has not started a stage-in phase. In this case, the job does not receive a reservation of processors. Therefore, other jobs can be backfilled ahead of it. In our experimental workload, every job requires burst buffers, thus every job can be arbitrarily delayed. Assuming that all jobs require burst buffers and each job is executed right after the stage-in phase, as in our model (Fig. 4), Slurm backfilling works similarly to backfilling without any future reservations—procedure Backfill at line 7 (but without the reservation in line 14). There are still some differences between Slurm scheduling and the Backfill procedure. First, Slurm decouples allocation of burst buffers and allocation of processors. Slurm also has an FCFS scheduling loop running concurrently to backfilling.

In conclusion, the large empty spaces visible in Fig. 3 only happen in the theoretical EASY-backfilling without future reservations of burst buffers. The current, greedy scheduling in Slurm solves this but at the expense of potentially arbitrary delays of jobs with burst buffer requirements. A simple extension of backfilling with future simultaneous processor and burst buffer reservations eliminates both problems.

The general idea of plan-based scheduling is to create an execution plan for all jobs in the waiting queue. An execution plan is an ordered list of jobs with their scheduled start times and assigned resources. Naturally, only a few jobs could be launched immediately. Others are provided with non-overlapping reservations of resources at different points of time in future for the duration of their walltimes. The easiest way to create the execution plan is to iterate over the queue of jobs and for each job find the earliest point in time when sufficient resources are available. The quality of the obtained plan depends on the order of jobs. Therefore, it is possible to define an optimisation objective and perform a search over permutations of jobs.

We further investigate and extend the plan-based approach to scheduling with simulated annealing optimisation proposed by Zheng et al. [26]. First, we extend the reservation schema with the reservations for burst buffer requests. Second, we apply several modifications to the simulated annealing. Our plan-based scheduling is presented in Algorithm 2. The input parameters $Q$, $r$, $N$, $M$ denote the waiting queue, cooling rate, number of cooling steps and constant temperature steps respectively.

As the optimisation objective, we minimise a sum of waiting times of jobs weighted by an exponent $\alpha\in\mathbb{R}^{+}$ (definition of the waiting time is given in Fig. 4). For a permutation $P$, let $W_{j}^{P}$ denote the waiting time of the $j$-th job in $Q$ according to the execution plan created based on $P$.

We denote the sum in the above formula as a score $S$ of the execution plan of $P$. Zheng et al. observed that for small values, such as $\alpha=1$, this objective allows one job to be significantly postponed in favour of other jobs as long as the total waiting time of all jobs improves, which eventually may even lead to starvation. The higher is the value of $\alpha$, the more penalised is the objective function for delaying a job. Plan-based scheduling does not ensure as strict fairness criteria as reservations in EASY-backfilling, but increasing the value of $\alpha$ may be perceived as a soft mechanism for ensuring fair resource sharing.

We enhance the simulated annealing algorithm of [26] as follows. First, we introduce a set of candidates $I$ for the initial permutation used to generate the best and worst initial scores ($S_{\text{best}}$, $S_{\text{worst}}$), which allow us to set an optimal initial temperature $T$ according to the method proposed by [1]. We define the set of 9 initial candidates by sorting jobs according to 9 different criteria: (1) the order of submission (FCFS); (2) ascending and (3) descending by the requested number of processors, (4) ascending and (5) descending by the requested size of burst buffer per processor, (6) ascending and (7) descending by the ratio of the requested size of burst buffer per processor to the requested number of processors, (8) ascending and (9) descending by walltime.

Second, we make the search space exploration faster by (1) introducing exhaustive search over all possible permutations for small queues (up to 5 jobs); (2) faster cooling ($r=0.9$, $N=30$, $M=6$); and (3) skipping the annealing if it is unlikely to find a better permutation—when the scores of the best and the worst initial candidates are the same ($S_{\text{best}}=S_{\text{worst}}$). As a result, our algorithm finds a near-optimal permutation in only $N\cdot M+|I|=189$ iterations, compared to $\lceil 100\log_{0.9}(0.0001)\rceil=8742$ iterations by Zheng et al. The number of iterations has principal importance in online job scheduling, where the time available for scheduling is limited.

To evaluate and compare scheduling algorithms, we created a detailed supercomputer simulator. We extended Batsim [6, 21]—a simulator framework of RJMS based on SimGrid [4], which is capable of simulating I/O contention and I/O congestion effects. We used Pybatsim scheduler to implement our algorithms and manage I/O side effects.

We evaluate and compare the following scheduling policies:

fcfs

FCFS without backfilling;

fcfs-easy

FCFS EASY-backfilling without reservations for burst buffers;

filler

Perform the backfill procedure from Algorithm 1 but without reserving resources for queued jobs in future (without line 14);

fcfs-bb

FCFS EASY-backfilling with simultaneous reservations for processors and burst buffers;

sjf-bb

SJF EASY-backfilling with simultaneous reservations for processors and burst buffers;

plan-$\alpha$

burst-buffer–aware plan-based scheduling; the number in the policy name (e.g., plan-2) is a value of the parameter $\alpha$ from Eq. 1.

Fig. 6 and Fig. 6 show the first surprising result: excluding the baseline fcfs, fcfs-easy has two orders of magnitude higher mean waiting time and bounded slowdown than other policies. The simple extension of the FCFS-backfilling to explicitly reserve burst buffers (fcfs-bb) results in significant improvements. When the scheduler is additionally able to change the ordering of the jobs (sjf-bb), the gains are even higher. fcfs-easy shows better distribution than fcfs for the majority of jobs. However, it changes for the last 32-quantile. The explanation for this observation is visible in the tail distribution plot Fig. 10, which for each policy presents individual values for 3000 jobs with the highest waiting times. We see there an extremely significant dispersion of waiting times of fcfs-easy, which also affects the bounded slowdown (Fig. 10). Overall, fcfs-easy on average achieves better results than fcfs, but it can considerably delay numerous jobs. These results quantitatively confirm the example from Section 3.1.

The simple filler shows good distribution of waiting times and bounded slowdown, also in the quantile plots (Fig. 8 and Fig. 8 are boxenplots, also called letter-value plots [14], with a logarithmic scale). However, the tail distribution plots (Fig. 10 and Fig. 10) show that filler is likely to disproportionately delay some jobs—pointing to their near-starvation, which we hinted at in Section 3.2.

Our proposed plan-based scheduling algorithm, plan-2, outperforms all other policies. As opposed to queue-based scheduling, plan-based scheduling may leave a cluster underutilised at a given moment to enable earlier execution of jobs in the future. Although this behaviour can result in a higher median waiting time, it should improve higher-order quantiles as seen in Fig. 8. However, as plan-1 has much flexibility in reordering jobs, it is likely to fully utilise the cluster by taking jobs from any position in the queue for instant execution. This flexibility comes at the cost of significant delay of selected jobs, as shown in Fig. 10.

For a more robust comparison between the algorithms, we split the workload into 16 three-week-long parts. We compute the average for each part and each policy, and then normalise it by the corresponding average from the sjf-bb policy. We chose sjf-bb as the reference policy, because on the whole workload, its mean waiting time is smaller by 4.5% than fcfs-bb. Boxplots in Fig. 12 and Fig. 12 show statistics. Moreover, the 16 dots on each box correspond to the 16 averages, one for each three-week-long part. These results might be interpreted in the following way: the lower the boxplot, the better the scheduling efficiency. This analysis confirms our results on the whole trace: in most cases, filler has a higher mean than non-starving, burst-buffer–aware policies; and plan-based scheduling outperform greedy list scheduling. Additionally, in the shorter workloads, plan-1 outperforms plan-2 because of the limited capability of delaying jobs.