# On the Optimization of Resources Usage in HPC with a Deadline-Driven Jobs Scheduling Algorithm

Djobolo Tchimou, Tchimou N’takpé, Djédjé Sylvain Zézé, Gokou Hervé

Fabrice Diédié

► To cite this version:

Djobolo Tchimou, Tchimou N’takpé, Djédjé Sylvain Zézé, Gokou Hervé Fabrice Diédié. On the Optimization of Resources Usage in HPC with a Deadline-Driven Jobs Scheduling Algorithm. Lecture Notes in Networks and Systems, 2025, Lecture Notes in Networks and Systems, 1511, pp.97-108. 10.1007/978-981-96-8796-1_9. hal-04961016v4

HAL Id: hal-04961016

https://inria.hal.science/hal-04961016v4

Submitted on 20 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Optimization of Resources Usage in HPC with a Deadline-Driven Jobs Scheduling Algorithm

Djobolo Tchimou¹, Tchimou N’takpé², Djédjé Sylvain Zézé³, and Gokou Hervé Fabrice Diédié⁴

¹ Laboratory of Mathematics and Computer Science, Nanguy ABROGOUA
University, Abidjan, Côte d’Ivoire, jtchimou@gmail.com

² Laboratory of Mathematics and Computer Science, Nanguy ABROGOUA
University, Abidjan, Côte d’Ivoire, tchimou.ntakpe@gmail.com

³ Laboratory of Mathematics and Computer Science, Nanguy ABROGOUA
University, Abidjan, Côte d’Ivoire, s.zeze@xerya.fr

⁴ Laboratory of Mathematics and Computer Science, Peleforo Gon Coulibaly
university, Korogho, Côte d’Ivoire, herve.diedie@upgc.edu.ci

**Abstract.** In this paper we propose algorithms, inspired by bin packing algorithms, that take into account jobs submitted with deadlines in order to improve the resource utilization of HPC clusters by reducing jobs waiting times. These algorithms have the same advantages as Conservative Backfilling i.e. predictability and non-starvation guarantee. We compared the performance of our more efficient algorithm (Deadline-driven First Fit Backfilling algorithm a.k.a DFFBF) to the popular Conservative Backfilling and EASY algorithms and to the more aggressive modification of EASY that is Fattened Backfilling algorithm. Our evaluation results on 4 different real workloads showed that DFFBF always outperforms these 3 algorithms and the waiting time improvements are up to 57%. We also measured the execution times of our algorithm and proved that DFFBF is fast enough to be used on production platforms. So we recommend using the approach of deadline-driven jobs to manage HPC clusters.

**Keywords:** Job Scheduling, Deadline, HPC, Resource Management System, Backfilling, First Fit

## 1 Introduction

High Performance Computing (HPC) clusters [1,21,18] are essential infrastructures designed to execute a wide variety of jobs submitted by multiple users. To manage resource allocation and job scheduling, these computing Systems rely on a Resource and Job management System (RJMS), also known as batch schedulers such as OAR [1], SLURM [21] and Torque [18] which incorporate scheduling algorithms. These algorithms aim to satisfy users while optimizing resource utilization. Two popular scheduling algorithms used in production HPC
are Conservative Backfilling [6,13] and Argonne Extensible Scheduling System (EASY) [12]. Many studies [19,16,17,20,11,8,14] tried to improve EASY or Conservative Backfilling algorithms. This is also the scope of this article where we propose algorithms that take into account deadline-driven jobs and leverage the flexibility offered by these jobs to optimize ressource utilization. Our algorithms are also inspired by the most popular bin packing algorithms such as First Fit [4] and First Fit Decreasing [3].

Deadline-driven jobs scheduling in HPC clusters has been proposed first in [14]. The algorithm in this article is a modification of Conservative Backfilling that takes into account the fact that a proportion of jobs are non-priority and submitted with a deadline. These jobs can be postponed as long as their deadlines are not violated. The evaluation results showed that introducing jobs with deadlines improves platform utilization, reducing waiting times. However, this algorithm is equivalent to Conservative Backfilling when all jobs of the workload are either non-priority or priority. In this study, we propose algorithms that take into account 100% of jobs submitted with a deadline.

Our scheduling problem is close to the strip packing problem. Strip packing consists of arranging rectangular objects within a strip of fixed width and infinite height, without allowing rotations. One key difference between our problem and traditional strip packing problems studied in the literature is that, at each scheduling round of our problem, the strip is already partially filled with running jobs. Another difference is that the height of each item used to fill the strip is updated at the end of its execution, since the estimated execution times differs from the actual execution times when jobs are scheduled in HPC clusters. In [9], it is shown that bin packing algorithms can be used for strip packing while maintaining the asymptotic worst-case ratio. Thus our algorithms draw inspiration from some of the best bin packing algorithms.

The remainder of the paper is organized as follows. Section 2 presents the related work. Section 3 describes our proposed algorithms, detailing their principles and motivations. Section 4 is dedicated to the complexity analysis, while Section 5 outlines the simulation conditions and the analysis of the obtained results. Finally, Section 6 concludes the study.

## 2 Related Works

The most popular algorithms used in RMJS are EASY [12] and Conservative Backfilling [6,13]. Easy guarantees non starvation by avoiding pushing back the job at the head of the waiting list. But with EASY there is no predictability because a job can be postponed indefinitely before it become the head of the waiting list. Conservative Backfilling guarantees predictability and therefore also non starvation by making a reservation for each submitted job. Since jobs often finish their execution before their estimated end date, Conservative Backfilling reschedules each job on the waiting list at the end of the execution of a job. Note that the paper presenting Conservative Backfilling does not specify how rescheduling is to be carried out. However, it is possible either to cancel all the
reservations and do the rescheduling by submission date, or do the rescheduling one job after another in order of their estimated start times. Our experiments have shown that the second option gives better results, and it is obvious to prove that it is the only one of the two approaches that guarantees predictability (each job will finish its execution at latest at the estimated finish time obtained at the job submission).

Many studies [19,16,17,20,11,8,14] tried to improve EASY or Conservative Backfilling algorithms. One of the most recent of these algorithms is Fattened backfilling algorithm [8], a more aggressive modification of the EASY backfilling algorithm where the job at the head of the waiting list can be postponed. During each backfilling attempt, it is only ensured that the job at the head of the waiting list is not delayed beyond a certain threshold. However, this approach lead to a risk of starvation. DBF [14] is a low-complexity algorithm that introduced non-priority deadline-driven jobs. This approach reserves resources for priority jobs while allowing non-priority jobs to be postponed, provided their deadlines are respected. Analysis reveals that when all jobs are non-priority, the algorithm is equivalent to Conservative Backfilling. In this work, we propose algorithms that can take into account workloads with 100% deadline-driven jobs, since the submission of non-priority deadline-driven jobs to HPC offers greater flexibility to RJMS to optimise ressource utilization.

## 3 Deadline-driven Backfilling Algorithms

**Algorithm 1** schedule a new job $J_i$ (DFFBF and DFFDBF)

**Input:** New job $J_i$, List of waiting jobs $W$ and list of running jobs $R$
**Output:** $W$ and $R$ Updated
1: Schedule $J_i$
2: if $start_i = current_time$ then
3:     Execute $J_i$
4:     else
5:         if $requested_nodes_i > nb_free_nodes$ then
6:             Compute Deadline of $J_i$
7:             $W \leftarrow W \cup \{J_i\}$
8:         else
9:             if $TryToExecute(J_i) = false$ then
10:             Compute Deadline of $J_i$
11:         $W \leftarrow W \cup \{J_i\}$
12:     end if
13:     end if
14: end if

Our algorithms draws inspiration from the most effective bin packing algorithms, namely First Fit [4] and First Fit Decreasing [3]. Since the predictability
<caption>**Algorithm 2 Reschedule waiting jobs (DFFBF)**</caption>

**Input:** List of waiting jobs $W$ and list of running jobs $R$
**Output:** $W$ and $R$ Updated
1: Update the first item of the Usage profile
   // Comment: Reschedule all waiting jobs
2: **for all** $J_i \in W$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;ReSchedule $J_i$
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $start_i = current_time$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Execute $J_i$
6: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
7: **end for**
   // Comment: Try to execute some waiting jobs
8: $i \leftarrow 1$
9: **while** $nb_free_nodes > 0$ **and** $i \le length(W)$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp; $J_i \leftarrow W[i]$
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** $requested_nodes_i \le nb_free_nodes$ **and** TryToExecute($J_i$) = false **then**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $i \leftarrow i + 1$
13: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
14: **end while**

of the algorithms is ensured by the fact that each job must finish its execution before its deadline, we make reservation for each job similar to the conservative backfilling approach. The core principle of our algorithms is to use either First Fit, First Fit Decreasing, First Fit Decreasing Height, or First Fit Decreasing Width, while carefully respecting the deadlines of the waiting jobs. As the resources are homogeneous, we use a simple structure called usage profile to manage reservations. The usage profile is a doubly linked list, where each item contains a date and the number of free resources available from that date until the next item's date. This structure allows us to track the number of available resources for each time interval. It takes into account the start times of running jobs, the estimated start times of waiting jobs, and the estimated finish times of running jobs and waiting jobs. A resource reservation for a job $J_i$ involves modifying the usage profile and setting its estimated start time ($start_i$), and thus its estimated finish time. The allocation of resources for each job will be made just before its execution. The algorithms respond to two events: the arrival of a new job and the completion of a job's execution.

When a new job $J_i$ is submitted, all of our algorithms use algorithm 1. Algorithm 1 first checks whether this job can be executed without violating the deadlines of waiting jobs. To do this, it first schedules the job without canceling the reservations of waiting jobs (line 1 of algorithm 1) and check if $start_i$ is equal to the current time ($current_time$). If this is true, the job is executed (lines 2-3 of algorithm 1). If $start_i$ is not equal to $current_time$ and the number of available resources ($nb_free_nodes$) at $current_time$ is less than the number of requested nodes of $J_i$ ($nb_req_nodes_i$), then it is not necessary to try to execute the job. The deadline $d_i$ of the job $J_i$ is computed and then $J_i$ is inserted in the waiting
<caption>**Algorithm 3 Reschedule waiting jobs (DFFDBF)**</caption>

**Input:** List of waiting jobs $W$ and list of running jobs $R$
**Output:** $W$ and $R$ Updated
1: Update the first item of the Usage profile
   // Comment: Execute any job which can start immediately
2: **for all** $J_i \in W$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**if** $start_i = current_time$ **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Execute $J_i$
5: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
6: **end for**
   // Comment: Try to execute some jobs
7: **backfilled** $\leftarrow$ false
8: $i \leftarrow 1$
9: **while** $nb_free_nodes > 0$ **and** $i \le$ length($W$) **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;$J_i \leftarrow W[i]$
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** $requested_nodes_i \le$ $nb_free_nodes$ **and** TryToExecute($J_i$) = false **then**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$
13: &nbsp;&nbsp;&nbsp;&nbsp;**else**
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $requested_nodes_i \le$ $nb_free_nodes$ **and** TryToExecute($J_i$) = true **then**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;backfilled $\leftarrow$ true
16: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
17: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
18: **end while**
   // Comment: ReSchedule waiting jobs if no job is executed
19: **if** backfilled = false **then**
20: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $J_i \in W$ **do**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ReSchedule $J_i$
22: &nbsp;&nbsp;&nbsp;&nbsp;**if** $start_i = current_time$ **then**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Execute $J_i$
24: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
25: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
26: **end if**

list $W$ (lines 5-7 of algorithm 1). If $start_i$ is not equal to $current_time$ but the number of available resources ($nb_free_nodes$) at $current_time$ is sufficient to execute the job, algorithm 1 calls TryToExecute algorithm 4 (line 9 of algorithm 1) which try to execute $J_i$. Algorithm 4 first cancels the reservations of waiting jobs, reschedule the new job $J_i$, and then reschedule the waiting jobs (lines 2-14 of algorithm 4). If no deadline is violated, $J_i$ is executed and any waiting job $J_k$ such that $start_k$ is equal to $current_time$ is executed, as the reschedule may changes their start times (lines 15-22 of algorithm 4). If $J_i$ cannot be executed at $current_time$, i.e the TryToExecute operation return false, the reservations of waiting jobs are restored, $J_i$ is rescheduled (lines 23-28 of algorithm4), its deadline is computed (cf our choice of deadlines in section 5) and then it is inserted into the waiting list $W$ (lines 10-11 of algorithm 1).

At the end of a job's execution, the First Fit version uses algorithms 2, while the different First Fit Decreasing variants use algorithms 3. In all cases, during
**Algorithm 4** Try To Execute $J_i$

**Input:** Job $J_i$, List of waiting jobs $W$ and list of running jobs $R$
**Output:** Boolean executed and $W$ and $R$ Updated
1: executed ← false
2: Cancel reservation of $J_i$
3: **for all** $J_k \in W | k \neq i$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;Cancel Reservation of $J_k$
5: **end for**
6: Schedule $J_i$
7: violationOccur ← false
8: **for all** $J_k \in W | k \neq i$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;Schedule $J_k$
10: &nbsp;&nbsp;&nbsp;&nbsp;**if** estimated_finished_time$_k$ > $d_k$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;violationOccur ← true
12: &nbsp;&nbsp;&nbsp;&nbsp;**Break**
13: **end if**
14: **end for**
15: **if** violationOccur = false **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;Execute $J_i$
17: executed ← true
18: **for all** $J_k \in W | k \neq i$ **do**
19: &nbsp;&nbsp;&nbsp;&nbsp;**if** start$_k$ = current_time **then**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Execute $J_k$
21: **end if**
22: **end for**
23: **else**
24: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $J_k \in W | k \neq i$ **do**
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Restore Schedule of $J_k$
26: **end for**
27: Restore Schedule of $J_i$
28: **end if**
29: **return** executed

any rescheduling operation, jobs are sorted based on their estimated start times to ensure that deadlines are met.

In First Fit Version (Deadline-driven First Fit Backfilling algorithm), when a job complete its execution, the algorithm takes advantage of the fact that jobs often finish earlier than the estimated finish time because the users overestimate the execution times of their jobs submitted to the HPC cluster. It reschedule each waiting job to advance start$_i$. After this rescheduling, any job $J_i$ such that start$_i$ is equal to current_time is executed (lines 2-7 of algorithm 2). If there are still free resources available, all jobs that can be executed without violating the deadlines of other waiting jobs are executed following their estimated start times in increasing order (lines 8-14 of algorithm 2). Since each success of Try-ToExecute operation causes effective rescheduling of waiting jobs, which may change their start times, the algorithm execute all waiting jobs that can start after each successful TryToExecute operation (lines 15-22 of algorithm 4).
For the First Fit Decreasing variants (Deadline-driven First Fit Decreasing Backfilling algorithm), when a job complete its execution, any waiting job $J_i$ such that $start_i$ is equal to current_time is executed first (lines 2-6 of algorithm 3). After this step, if there are still free resources available, all jobs that can be executed without violating the deadlines of other waiting jobs are executed. These jobs are taken in decreasing order either by area ($resquested\ time \times resquested\ resource$), or by their height ($resquested\ time$), or by their width ($resquested\ resource$) (lines 7-18 of algorithm 3). As in First Fit, all waiting jobs that can start after each successful TryToExecute operation are executed (lines 15-22 of algorithm 4). If TryToExecute return false, the algorithms reschedule each waiting job to advance $start_i$. After this rescheduling, any job $J_i$ such that $start_i$ is equal to current_time is executed (lines 19-26 of algorithm 3).

# 4 Complexity Analysis

In this section, we compute the worst case complexity of the proposed algorithms. The more complex part of the algorithms is when a job finishes its execution (algorithm 2 or algorithm 3). Let $N$ the sum of the number of running jobs and the number of waiting jobs. The usage profile contain at most $2N$ entries. Schedule a job or cancel its schedule are two operations that manipulate the Usage Profile by allowing either the addition or modification of an item within it. The complexity of each of these operations is $O(N)$. In TryToExecute algorithm4, the rescheduling of all the waiting jobs (lines 1-14) has a complexity of $2 \times N \times O(N) = O(N^2)$ and the attempt to execute some jobs or restoring all scheduling (line 15-28) has complexity in worse case of $O(N^2)$. Thus the overall complexity of TryToExecute algorithm4 in worse case is therefore $O(N^2)$. So, the overall worst case complexity of algorithm 1 is $O(N^2)$ whereas the worst case complexity of both algorithms 2 and 3 is $O(N^3)$.

# 5 Experimental Evaluation

## 5.1 Simulation Platform

Several tools such as Alea [10] and Batsim [5] are employed in the literature to simulate execution of jobs in HPC clusters and evaluate RJMS scheduling algorithms. For our experiments we used Batsim, a platform based on SimGrid [2] which provide a flexible environment for resource simulation and scheduling studies. Batsim offers a simple messaging interface that connects the simulation engine to scheduling algorithms, which can be implemented in various programming languages. We implemented the evaluated algorithms in Python across Pybatsim [15], the python plugin of Batsim.

## 5.2 Evaluation Metrics

The first metric considered is the **average waiting time**. The waiting time of a job $J_i$ ($wait_i$) is the difference between its submission time ($submit_i$) and its
start time (*start*<sub>*i*</sub>). If the average waiting time is small, this means that the HPC
cluster is efficiently used. This is an opportunity for the cluster to execute more
jobs. The second metric is the **average scheduling time**, which measures the
time required by the scheduling algorithm to make decisions for each job. The
scheduling time of a job include the time to compute schedules when the job is
submitted and time to compute schedules at the end of the execution of the job.
As users are only interested with meeting their deadlines, we do not take into
account metrics such as slowdown which measures fairness.

5.3 Proposed deadlines

Let $d_i$ be the deadline of a job $J_i$, $predict_i$ the first estimated finish time of $J_i$, and $request_i$ the estimated execution time of $J_i$. For our simulations we propose three different deadlines. The first deadline, $d_i = predict_i$ called *0H deadline*, is based on the observation that jobs generally finish earlier than expected, providing an exploitable flexibility. The second deadline (*24H deadline*), $d_i = \max(submit_i + 24H, 2 \times request_i, predict_i)$ introduces a greater margin of flexibility compared to the first. Finally, the third deadline (*72H deadline*), $d_i = \max(submit_i + 72H, 2 \times request_i, predict_i)$ offers even more flexibility. The last two deadlines take into account the estimated execution time of $J_i$ to prevent users from excessively overestimating their job execution times. We choose 24 hours because it is a deadline that may satisfy many users. 72 hours is also a deadline that may satisfy many users, especially users who submit jobs just before the weekend and hope to obtain results at the beginning of the following week.

5.4 Experimental Data

To evaluates our algorithms, we used four real workloads from the *Parallel Workload Archive* [7] The **ANL-Intrepid** workload includes 68,936 job submissions recorded between January and September 2009 on the IBM Blue Gene/P Intrepid system at the Argonne Leadership Computing Facility. The **SDSC-BLUE** workload contains job submissions from April 2000 to January 2003 on the IBM SP Blue Horizon at the San Diego Supercomputer Center. Similarly, the **SDSC-DS** workload spans March 2004 to March 2005, capturing the workload of the DataStar cluster at the San Diego Supercomputer Center. Finally, the **HPC2N** workload reflects three and a half years of activity, from July 2002 to January 2006, and pertains to the Seth Cluster at the High-Performance Computing Center North in Sweden.

5.5 Results

Figure 1 shows the average waiting times of our algorithms on workloads ANL, HPC2N, SDSC-BLUE, and SDSC-DS, respectively. The algorithms are DFFBF (Deadline-diven First Fit Backfilling), DFFDBF_1 (inspired from first fit de-creasing heigh, i.e decreasing by resquested time), DFFDBF_2 (inspired from
<figure><img src="image_2.png" /><figcaption>Fig. 1: Comparison of the average waiting times of our four algorithms</figcaption></figure>

first fit decreasing width, i.e decreasing by requested resource), DFFDBF_3 (in-
spired from first fit decreasing by (*resquested time*) × (*resquested resource*)).
Overall, DFFBF is the most efficient algorithm. The improvement is particularly
significant when the deadline is at least 72 hours. Sorting jobs does not provide
any noticeable benefit compared to a simple first fit strategy in our schedul-
ing problem, where estimated execution times are higher than actual execution
times. We recommend DFFBF, not only for its overall performance but also for
its faster execution time.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Comparison of the average waiting times of DFFBF with EASY, CBF and Fattened Backfilling</figcaption></figure>
Figure 2 compares the average waiting times of our algorithm DFFBF, runed with different deadlines, with those of Conservative Backfilling algorithm, EASY backfilling algorithm, and Fattened Backfilling algorithm referred to as CBF, EASY and Fattened in the figures. We observe that the fattened backfilling algorithm, a more aggressive version of the EASY backfilling algorithm, achieves better performance than EASY and Conservative Backfilling. However, our algorithm consistently outperforms the fattened backfilling algorithm, with the performance gap widening as the deadline increases. In fact, the deadlines provide more flexibility to reduce holes in the schedule. Moreover, our analyses have shown that the fattened backfilling algorithm carries a risk of starvation, unlike our algorithm, which not only ensures fairness but also provides better predictability.

Table 1 presents the mean scheduling times for DFFBF on the four workloads and for different deadlines. We run the simulations on a processor Intel Core i5-4310U with a maximum frequency 3.00 GHz. We can see that the mean scheduling times are consistently low across all workloads and deadlines, ranging from a few milliseconds to a maximum of 0.1 seconds. This means that on all the four HPC clusters which we have used the workloads for the simulations, DFFBF can schedule more than one job per second (more than 3600 jobs per hour). We can conclude that DFFBF is fast enough to execute real workloads.

<table><caption>Table 1: Mean scheduling times of DFFBF (in second)</caption><thead><tr><td>Workload</td><td>0H deadline</td><td>24H deadline</td><td>72H deadline</td></tr></thead><tbody><tr><td>ANL</td><td>0.02</td><td>0.02</td><td>0.01</td></tr><tr><td>SDSC-BLUE</td><td>0.02</td><td>0.02</td><td>0.02</td></tr><tr><td>SDSC-DS</td><td>0.01</td><td>0.01</td><td>0.01</td></tr><tr><td>HPC2N</td><td>0.10</td><td>0.09</td><td>0.06</td></tr></tbody></table>

## 6 Conclusion

This study showed that submitting deadline-driven jobs to RJMS is a good approach to optimize ressource utilization. When the deadline is set equal to the first estimated finish time (after the first schedule of the job), our algorithms have the same predictability than Conservative Backfilling, this mean that the job will finish its execution at latest at the first estimated finish time. With this tight deadline, our more efficient algorithm DFFBF based on first fit not only outperforms Conservative Backfilling but EASY and Fattened backfilling. But EASY and Fattened Backfilling do not guarantee predictability. Another issue of Fattened Backfilling is that some jobs can suffer from starvation. Furthermore the measured execution times showed that DFFBF is fast enough. Thus DFFBF is a good candidate to replace these algorithms in production HPC clusters.
So we recommend using the approach of deadline-driven jobs to manage HPC clusters.

Our experiments also show that when we increase the deadlines we improve significantly the average waiting times of the submitted jobs. So we recommend to use relaxed deadlines in HPC clusters. It is important to note that our algorithm DFFBF may be use when the jobs of a workload are submitted with different deadlines. In future work, we will do more evaluations of DFFBF and study deeply the impact of deadlines.

Our source codes and the data of our experiments are available online at sources and data.

## Acknowledgments

We express our gratitude to Batsim [5] and PyBatsim [15] teams, and Frédéric Suter. Their tools and contributions have significantly facilitated this study.

## References

1. N. Capit, G. Da Costa, Y. Georgiou, G. Huard, C. Martin, G. Mounie, P. Neyron, and O. Richard. A batch scheduler with high level components. In *CCGrid 2005. IEEE International Symposium on Cluster Computing and the Grid, 2005.*, volume 2, pages 776–783 Vol. 2, 2005.

2. Henri Casanova, Arnaud Giersch, Arnaud Legrand, Martin Quinson, and Frédéric Suter. Versatile, scalable, and accurate simulation of distributed applications and platforms. *Journal of Parallel and Distributed Computing*, 74(10):2899–2917, 2014.

3. György Dósa, Rongheng Li, Xin Han, and Zsolt Tuza. *Theoretical Computer Science*, 510:13–61, 2013.

4. György Dósa and Jiri Sgall. First Fit bin packing: A tight analysis. In Natacha Portier and Thomas Wilke, editors, *30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)*, volume 20 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 538–549, Dagstuhl, Germany, 2013. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

5. Pierre-François Dutot, Michael Mercier, Millian Poquet, and Olivier Richard. Batsim: A realistic language-independent resources and jobs management systems simulator. In Narayan Desai and Walfredo Cirne, editors, *Job Scheduling Strategies for Parallel Processing*, pages 178–197, Cham, 2017. Springer International Publishing.

6. D.G. Feitelson and A.M. Weil. Utilization and predictability in scheduling the ibm sp2 with backfilling. In *Proceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing*, pages 542–546, 1998.

7. Dror G. Feitelson, Dan Tsafrir, and David Krakov. Experience with using the parallel workloads archive. *Journal of Parallel and Distributed Computing*, 74(10):2967–2982, 2014.

8. César Gómez-Martín, Miguel A. Vega-Rodríguez, and Jósé-Luis González-Sánchez. Fattened backfilling: An improved strategy for job scheduling in parallel systems. *Journal of Parallel and Distributed Computing*, 97:69–77, 2016.
9. Xin Han, Kazuo Iwama, Deshi Ye, and Guochuan Zhang. Strip packing vs. bin packing. In Ming-Yang Kao and Xiang-Yang Li, editors, *Algorithmic Aspects in Information and Management*, pages 358–367, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

10. Dalibor Klusáček and Hana Rudová. Alea 2 - job scheduling simulator. In *Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques (SIMUTools 2010)*, Malaga, Spain, 2010.

11. Dalibor Klusáček and Hana Rudová. Performance and fairness for users in parallel job scheduling. In Walfredo Cirne, Narayan Desai, Eitan Frachtenberg, and Uwe Schwiegelshohn, editors, *Job Scheduling Strategies for Parallel Processing*, pages 235–252, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

12. David A. Lifka. The anl/ibm sp scheduling system. In Dror G. Feitelson and Larry Rudolph, editors, *Job Scheduling Strategies for Parallel Processing*, pages 295–303, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.

13. A.W. Mu'alem and D.G. Feitelson. Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling. *IEEE Transactions on Parallel and Distributed Systems*, 12(6):529–543, 2001.

14. Tchimou N'takpé and Frédéric Suter. Don't hurry be happy: A deadline-based backfilling approach. In Dalibor Klusáček, Walfredo Cirne, and Narayan Desai, editors, *Job Scheduling Strategies for Parallel Processing*, pages 62–82, Cham, 2018. Springer International Publishing.

15. PyBatsim. Pybatsim: Python api and schedulers for batsim. https://gitlab.inria.fr/batsim/pybatsim, 2017. Accessed: 2025-02-08.

16. Edi Shmueli and Dror G. Feitelson. Backfilling with lookahead to optimize the packing of parallel jobs. *Journal of Parallel and Distributed Computing*, 65(9):1090–1107, 2005.

17. Srividya Srinivasan, Rajkumar Kettimuthu, Vijay Subramani, and Ponnuswamy Sadayappan. Selective reservation strategies for backfill job scheduling. In Dror G. Feitelson, Larry Rudolph, and Uwe Schwiegelshohn, editors, *Job Scheduling Strategies for Parallel Processing*, pages 55–71, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

18. G. Staples. Torque - torque resource manager. In *Proceedings of the ACM/IEEE SC2006 Conference on High Performance Networking and Computing*, page 8, Tampa, FL, November 2006.

19. D. Talby and D.G. Feitelson. Supporting priorities and improving utilization of the ibm sp scheduler using slack-based backfilling. In *Proceedings 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing. IPPS/SPDP 1999*, pages 513–517, 1999.

20. William A. Ward, Carrie L. Mahood, and John E. West. Scheduling jobs on parallel systems using a relaxed backfill strategy. In Dror G. Feitelson, Larry Rudolph, and Uwe Schwiegelshohn, editors, *Job Scheduling Strategies for Parallel Processing*, pages 88–102, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.

21. Andy B. Yoo, Morris A. Jette, and Mark Grondona. Slurm: Simple linux utility for resource management. In Dror Feitelson, Larry Rudolph, and Uwe Schwiegelshohn, editors, *Job Scheduling Strategies for Parallel Processing*, pages 44–60, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.