# Priority-BF: a Task Manager for Priority-Based Scheduling

Ana Gainaru, Scott Klasky, Guillaume Pallez

► To cite this version:

Ana Gainaru, Scott Klasky, Guillaume Pallez. Priority-BF: a Task Manager for Priority-Based Scheduling. EURO-PAR 2025 - 31st International European Conference on Parallel and Distributed Computing, Aug 2025, Dresden, Germany. pp.219-232, 10.1007/978-3-031-99854-6\_15 . hal-05109295

HAL Id: hal-05109295

https://inria.hal.science/hal-05109295v1

Submitted on 12 Jun 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
# PRIORITY-BF: a Task Manager for Priority-Based Scheduling

Ana Gainaru¹, Scott Klasky¹, and Guillaume Pallez²

¹ Oak Ridge National Laboratory, TN, USA
{gainarua, klasky}@ornl.gov

² Inria Rennes, France
guillaume.pallez@inria.fr (corresponding)

**Abstract.** The increasing demand for computational resources, particularly in High-Performance Computing environments, necessitates to rethink how we handle job scheduling strategies. This work addresses the challenge of managing concurrent jobs with differing priorities on overloaded parallel systems, where strict QoS constraints are often difficult for users to define. Our solution relies on a qualitative description of priorities and pulls from two key approaches: the EASY-BF algorithm and the CONSERVATIVE Backfilling algorithms. This solution improves the response time for high-priority jobs by 50% without affecting the overall system utilization. We show its applicability in several critical scenarios such as High-Performance Computing (HPC) resource management and in-situ computing.

**Keywords:** Scheduling, HPC, Priority execution, Backfilling algorithm

## 1 Introduction

The surge in data generation and the increasing complexity of scientific simulations have placed increasing demands on computational resources. This trend is

<figure><img src="image_2.png" /><figcaption>Fig. 1: Jobs submitted to Mira and Polaris, two HPC systems, are exhibiting increasing median wait times of hours, with large jobs being more affected.</figcaption></figure>
illustrated by the exponential growth of data centers in the US [7]. Simultaneously, HPC centers consistently operate at near-peak utilization, often exceeding 95%. This high utilization, while seemingly efficient, translates to substantial wait times for users, particularly for large-scale jobs [18]. Figure 1 shows the evolution of the median wait time for different types of jobs in two HPC systems in Argonne National Laboratory: Mira and Polaris (more details on these machines are provided in Section 3.1). Yet, HPC systems need to be overloaded, indeed it is a well-known fact that users overestimate their real machine occupation, and hence if the system is to be used fully, by design the queue has to be theoretically much more loaded than what the system can manage [10].

Faced with resource limitations, it is critical to efficiently decide how to allocate finite computational resources among competing demands. Several computing domains are prompting the exploration of prioritization mechanisms. This is the case for example for “Urgent Computing” where Beckman et al. [2] discuss the idea of having “tokens” to grant certain jobs preferential access to resources, allowing them to bypass queues and execute with minimal delay. This approach acknowledges that some computations are time-sensitive and critical, demanding immediate attention.

This is also true when periodic generation of data triggers a lot of various analysis function, particularly when the runtime of these analysis functions are extremely input-dependent [9]. Example include data generated by large experimental instruments such as the Square Kilometer Array (SKA). The SKA will generate vast quantities of data that must be processed by several massive workflows within a limited timeframe before new data arrives [15]. Similarly, in in-situ computing, iterative simulations generate data that triggers a large variety of analytical functions [14]. With limited computational resources compared to the number of desired analyses, a priority-driven approach is crucial. Users may want to prioritize analyses based on the simulation’s current state, past results, or the last execution time of specific functions [14].

In this work, we study the general question of how to deal with concurrent jobs submitted on a parallel systems, when those jobs do not have the same importance to the users/admins, and when there may or may not be time to execute all the jobs. Through discussions with HPC users, we realized that users often struggle to articulate precise Quality of Service (QoS) requirements. Specifying exact response times for different job types proves difficult, especially as workload patterns fluctuate. Users often prefer qualitative constraints over rigid quantitative metrics. This necessitates a scheduling solution that can adapt to varying workloads and accommodate imprecise user preferences.

*Motivating example:* The main algorithms used for resource management in HPC centers are EASY-BF [13] and CONSERVATIVE [16], two backfilling-based algorithms that protect against starvation. In EASY-BF, at each event (end of a job, arrival of a new job), a schedule is recomputed with the constraint that the non-running job with the largest priority cannot be delayed by scheduling a later job prior to this job. In CONSERVATIVE, a job with lower priority cannot delay any job with higher priority. In these algorithms, jobs priority are often based
<figure><img src="image_3.png" /><figcaption>Fig. 2: In a scenario where we have only a limited time to perform as many jobs as possible, and if $J_4$ has a larger priority than $J_5$, we would like an algorithm that behaves like CONSERVATIVE in this case.</figcaption></figure>

on First Come First Served (FCFS) order, i.e. *release time*, but there exist other implementations of priorities in EASY-BF [20], with different cost functions.

While HPC centers tend to favor EASY-BF because it usually provides better performance than CONSERVATIVE it has limitation when jobs have different priorities and there exist QOS-like constraints.

Consider a set of jobs $\{J_1 = (1, 5, 1), J_2 = (1, 2, 1), J_3 = (3, 1, 1), J_4 = (2, 3, 1), J_5 = (1, 2, 2)\}$, where $J = (n, t, p)$ means that job $J$ uses $n$ nodes, during a time $t$ and has priority $p$. Consider a deadline of 6. The Gantt chart of both EASY-BF and CONSERVATIVE is plotted in Figure 2. In this scenario, CONSERVATIVE allows to execute more jobs of priority 1.

The core idea of the solution that we propose in the rest of the document is quite simple and uses idea from both EASY-BF and CONSERVATIVE. When there are multiple priority levels, we propose to use EASY-BF within a priority level, and CONSERVATIVE when backfilling may impact jobs with a higher priority.

*Contributions:* Our design philosophy is guided by two core principles: simplicity and robustness. Simplicity ensures that users and system administrators understand the rationale behind scheduling decisions, fostering trust and accountability. This requires an interpretable algorithm that clearly communicates its logic. Robustness allow the system to accommodate diverse workloads. Our algorithm needs to be robust to real scenarios where users do not know exactly their requirements. Hence we rely on qualitative constraints rather than rigid specifications.

To address these challenges, we propose an extension of existing backfilling algorithms: EASY-BF and CONSERVATIVE. They are well-established scheduling algorithms known for their simplicity and efficiency. Our extension introduces a mechanism for incorporating job importance, allowing users to assign priority levels at the granularity of the job. When all jobs share the same priority, our algorithm seamlessly reverts to the standard EASY-BF behavior. This ensures backward compatibility and maintains the algorithm's proven performance. The paper makes the following contributions:
- A novel priority-based job scheduling algorithm, based on the EASY-BF framework, designed to minimize response times for high-priority jobs while maintaining overall system utilization.

- Simulation evaluation of our algorithm when used for scheduling parallel jobs in an High-Performance Computing (HPC) clusters compared to classical state of the art approaches.

- Deep dive into using the algorithm for scheduling in-situ and in-transit tasks for time sensitive analysis of instrument or simulation data.

The rest of the paper is presented as follows: in Section 2 we discuss our new scheduling strategy. We then present two use-cases to motivate it: scheduling of large jobs in HPC in Section 3, then overloaded in-situ/in-transit computing in Section 4. We present some related work on priority/Quality of Service (QoS) based scheduling in Section 5 before providing concluding remarks in Section 6.

## 2 PRIORITY-BF: a Hierarchical Scheduler Design

PRIORITY-BF was designed with a will to be unfair in scheduling mechanisms. Specifically in scenarios where the scheduler will not be able to execute all jobs, and when some should be treated as first or second-class citizens. We measure the efficiency of this scheduler through a lexicographic order: for a given objective (response time, work done in a limited time frame), we first want to optimize for the jobs with the highest priority, then for those with lower priorities.

In addition to the obvious efficiency objectives, our scheduler design was led by several fundamental principles:

1. **Robustness:** it is well known that the information that one can collect is often inaccurate. The algorithm that we design has to be robust to inaccurate information.

2. **Simplicity:** the scheduler needs to be simple in terms of implementation, but also in terms of usage. Indeed, with the democratization of parallel computing, asking too much information from a user can be counter-productive. Instead we wanted simple qualitative information ("high/low" priority) when qualifying job priorities instead of quantitative information ("response time below X min").

*High-level algorithm presentation* Rather than reinventing the wheel, we chose to rely on existing and proven solutions: EASY-BF and CONSERVATIVE.

The main idea of the algorithm is to keep several queues, each queue corresponding to job priorities (by decreasing order). The global algorithm satisfies the following properties, reading from the queue by increasing index:

- Within a queue, jobs are scheduled with an EASY-BF strategy

- Between queues, jobs are scheduled conservatively: jobs from a queue with a higher index cannot delay jobs from a queue with a lower index.
Contrarily to the original EASY-BF and CONSERVATIVE (that use FCFS as priority strategy), this algorithm does not guarantee a no-starvation strategy. On the contrary, some jobs from the queue with the lowest index could very well never be executed.

In its extreme configurations, this scheduling strategy simplifies to precisely the EASY-BF algorithm when all jobs share a single priority level, and to the CONSERVATIVE algorithm when every job possesses a unique priority.

*Implementation* Our algorithm employs multiple priority queues, with each submitted job assigned a numerical priority value in ascending order, where 0 denotes the highest priority. Within each priority queue, jobs are initially considered for scheduling in the order given by EASY-BF. The first job is rigidly scheduled (meaning its start time cannot be delayed) into the earliest available time slot that accommodates its resource requirements. When considering backfilling, the algorithm prioritizes scheduling jobs that can start early within the same priority queue. Critically, however, a lower-priority job will never be allowed to delay the potential backfilling of a higher-priority job, even if the higher-priority job could only start at a later time slot.

# 3 Use Case: Application to Parallel Job Scheduling

In this first use-case we consider the general HPC job scheduling problem. Jobs submitted on HPC machines have very high wait times that continue to increase especially for large jobs (Figure 1). The consequence is that *Users are now submitting medium-sized jobs because the wait times for larger sizes tend to be longer* [18]. The question that we aim to solve is the following: can we propose a job scheduler which solves the problem of re-balancing large jobs response time without manually tuning and without trading-off on system utilization?

While EASY-BF treats all jobs in a similar manner, we use the PRIORITY-BF algorithm to standardize response times across jobs of varying sizes. In addition, HPC centers have to manually deal with mission-critical jobs (for instance Gordon Bell jobs) [18] so introducing the concept of priority at the level of individual jobs (through PRIORITY-BF) can adapt the scheduling process to different requirements.

## 3.1 Evaluation Scenarios

To be able to evaluate the possible impact of our scheduling strategy, we use execution logs [1] from three clusters at Argonne National Laboratory: 1) Mira is a 10-petaflops IBM Blue Gene/Q supercomputer with more than 5 billion computing hours allocated each year, in production between 2012 and 2019; 2) Polaris is a 34-petaflops 560 nodes system operating since 2022; and 3) Theta is an 11.7-petaflops system operating since 2017 consisting of two separate architectures: 24 racks of Intel CPU (Theta KLN) and 7 raks of Nvidia GPUs (Theta GPU). We tag jobs with three different categories for PRIORITY-BF: large jobs
<table><caption>Table 1: Log characteristics for 4 systems at ANL that was used to analyze the performance of our scheduler compared with current solutions in HPC.</caption><thead><tr><th>System</th><th>#Nodes</th><th>#Cores/Node</th><th>Start Date</th><th>End Date</th><th>#Jobs</th><th>n<sub>1</sub> nodes</th><th>n<sub>2</sub> nodes</th></tr></thead><tbody><tr><td>Mira</td><td>49,152</td><td>16</td><td>2016-01-01</td><td>2020-12-31</td><td>224,003</td><td>2k</td><td>8k</td></tr><tr><td>Polaris</td><td>560</td><td>64</td><td>2022-08-09</td><td>2024-12-31</td><td>519,296</td><td>32</td><td>128</td></tr><tr><td>Theta-KNL</td><td>4,392</td><td>64</td><td>2017-07-01</td><td>2023-12-31</td><td>540,623</td><td>256</td><td>1024</td></tr><tr><td>Theta-GPU</td><td>24</td><td>1</td><td>2020-09-22</td><td>2023-12-31</td><td>147,658</td><td>3</td><td>8</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 3: Large jobs represent the majority of node hours on an HPC center.</figcaption></figure>

have the highest priority, medium sized jobs have medium priority, and smallest jobs have low priority. We define large, medium, and small jobs similar to the study in [18]. For the Mira supercomputer the three classes are represented by jobs with more than $n_1 = 8K$ nodes, jobs with a number of nodes between $2K$ and $8K$ and jobs with less than $n_2 = 2K$ nodes respectively. For the other platforms we choose $n_1$ and $n_2$ so that, jobs requesting a number $N$ of nodes s.t. $N > n_1$ (resp. $N \le n_2$) corresponds to 10% largest (resp. 80% smallest) jobs. Table 1 presents statistics of the four logs we analyzed and the $n_1, n_2$ values for each system.

Figure 3 shows the percentage of core hours spent running jobs of different size. Even though the large jobs represent a small percentage of the total jobs, they represent the majority of the core hours spent on the systems with the exception of Theta-GPU. Moreover, the yearly trend shows a slight increase in the percentage of core hours consumed by large jobs. Theta-GPU has been designed for AI training codes and has a different profile than the other systems so we expect the results to be slightly different. We study, in the next sections, the impact of PRIORITY-BF on the utilization of the system, and on response time, compared to the standard EASY-BF strategy used in HPC centers, namely:

- EASY-BF with no priority, the default scheduler in most HPC centers that uses a FCFS strategy with backfilling choosing jobs that can start the earliest (called EASY-BF).

- an EASY-BF version that was configured to consider different priorities for the backfilling algorithm (called LJF, for Largest Job First).
## 3.2 Evaluation Methodology

To evaluate our proposed priority-based scheduling algorithm, we employed ScheduleFlow<fnref n="3" />, a lightweight simulator we developed for studying the performance of scheduling algorithms. ScheduleFlow inherently supports fundamental scheduling policies such as FCFS, Shortest Job First (SJF), and Largest Job First (LJF), coupled with CONSERVATIVE and EASY-BF backfilling strategies. We augmented ScheduleFlow to specifically accommodate and simulate job priorities by including multiple priority queues and the algorithm detailed earlier. This simulator focuses on core scheduling logic without incorporating hardware specifics, I/O operations, or network considerations, an intentional design choice as our experiments utilize execution logs containing precise runtimes, negating the need for variability modeling through proxy applications. ScheduleFlow operates by processing HPC workload logs in seven-day intervals, simulating job scheduling and backfilling under various configurations based on the recorded submission times.

*Validation:* We compared our ScheduleFlow simulations using the standard EASY-BF algorithm against the actual execution of jobs on the real-world HPC system (based on the log). While perfect accuracy is unattainable in any simulation due to unknown factors such as the initial state of waiting queues and unscheduled node downtimes, our results demonstrated a decent correlation. Overall, the simulation exhibited a marginally higher system utilization and maintained a comparable ratio in the response times across all jobs when contrasted with the real scheduler’s performance. This initial comparison provides confidence in the fidelity of our simulation environment for further evaluating our priority-based scheduling extensions.

*Evaluation:* We focus on several metrics: i) The relationship between job size and response time; ii) Overall system utilization, iii) Analysis of performance under varying workload characteristics, specifically considering priority distributions and submission volumes.

To ensure a representative assessment of system behavior under sustained load, utilization and response time are calculated for all jobs submitted between time $s$, defined as the point when the system reaches a saturation level where immediate scheduling upon submission is no longer possible, and time $e$, the timestamp of the last job submission. This approach effectively excludes the initial and final periods of the simulation where the system might not be fully utilized, thereby preventing potential distortions in the reported utilization and response time metrics [6]. For completeness we define utilization and response time, similarly to related work [3]: $U(T) = \sum_{i=0}^{N_j} c_i t_i / (P \times T)$ where utilization $U$ for a timeframe $T$ is represented by sum of the volume occupied by each job (processor cores used $c_i$ multiplied by execution time $t_i$) to the total volume of the timeframe (namely total processors $P$ multiplied by total loop time $T$),

<footnote n="3">³ Code available at https://github.com/ORNL-Inria/PriorityBF</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4: Average improvement factor of the PRIORITY-BF strategy compared to the other two solutions. PRIORITY-BF improves the response time for high-priority jobs (1.2-1.5x improvement) without impacting the system utilization.</figcaption></figure>

with $N_J$ the number of all submitted jobs; and the mean response time $R(T) = \text{median}([R(0), R(1), \dots, R(N_J)])$ with $R(i) = t_{\text{start}_i} - t_{\text{submitted}_i}$.

## 3.3 Simulation Results

Figure 4 illustrates the average system utilization across all simulated time periods alongside the median response time ratio observed with PRIORITY-BF compared to the one for EASY-BF and LJF for each priority level. The system utilization remains consistent and similar to the utilization levels of the real-world system. Furthermore, the implementation of PRIORITY-BF results in an increase in response times for low and medium-priority jobs, while significantly reducing the average response time for higher-priority jobs by 1.2-1.5x across the simulated systems.

Compared to LJF, our approach still improves the response time for high-priority jobs. This advantage stems from our conservative backfilling algorithm, which prevents higher-priority jobs from being delayed by the execution of lower-priority jobs, even if they can start sooner, something LJF does only for the first largest job of the queue. This last performance really highlights the importance
<figure><img src="image_6.png" /><figcaption>Fig. 5: The wait time across jobs of different size is more uniform when using strategies like PRIORITY-BF that prioritizes large jobs typically in disadvantage compared to smaller jobs when the classic EASY-BF strategy is used.</figcaption></figure>

of mixing both CONSERVATIVE and EASY-BF, compared to the solution of in-
cluding priorities into EASY-BF.

The observed performance variations across the simulated systems can be largely attributed to the fluctuating distribution of high-priority jobs across different time windows. For instance, the Theta-GPU system exhibits a limited number of analyzed timeframes that are predominantly characterized by large jobs. The job priorities are relatively uniformly distributed over time. This consistent submission pattern allows our scheduler to effectively improve the response time of these large, high-priority jobs without significantly impacting smaller jobs, resulting in minimal negative consequences, primarily affecting medium-sized jobs. Conversely, the Theta system demonstrates a highly imbalanced workload, with a large number of high-priority jobs concentrated within specific timeframes. During these peak periods, smaller and medium-sized jobs tend to be greatly delayed, leading to a considerably higher average response time compared to traditional scheduling approaches.

Comparing in Figure 5 the results of PRIORITY-BF to our initial observations from Figure 1 we do not observe the same patterns anymore, the median time wait for large jobs being reduced significantly while the low and medium sized jobs are seeing larger wait times, though keeping a more balanced behavior compared to the original extremely unbalanced performance.

4 Use Case: In-Situ/In-Transit Computing

In this second use case we consider a simulation job or an experiment that iter-
atively generates data overwriting previous data. At the end of each iteration,
several jobs are available to analyze this data on a dedicated cluster/resource. Ex-
ample include SKA where generated data needs to be compressed and analyzed
for discovering patterns, trends and correlations [15]; high fidelity simulations
like S3D [12] or E3SM [17] that require extensive analysis tasks in each step to
compute derived quantities [11] and identify regions of interest; correctness and
fault tolerance tasks needed to check the integrity of the results or the physics correctness [21].

If the size of the analytical cluster is not sufficient to execute all the analytical jobs, a scheduler has to decide which jobs should be executed before the next release of data (i.e. the end of the subsequent iteration). In these cases, users may decide on constraints on those analytical jobs to help with the selection, such as priority levels, or QoS constraints. They can take the form of *Ideally, this job should be executed at least every *x* units of time* [14]. For example, correctness tests can be executed every 100 simulation steps, visualization every 10 steps and quantities of interest need to be computed at every step.

We formalize this problem and we show how one can use PRIORITY-BF for this problem in Section 4.1. Finally, we evaluate its performance compared to other strategies.

## 4.1 Formalization and Methodology

The length of the *i*th simulation iteration can be represented by a random variable $X_i$. The simulation jobs are represented via a quadruplet: $J = (n, w, t, p)$, where *n* is the number of node requested, *w* is the requested walltime, *t* is the actual runtime (*t* < *w*), and *p* is the priority function. This priority can be either qualitative (e.g. [*p* = 0] high priority, [*p* = 1] medium priority, [*p* = 2] low priority), or quantitative (e.g. *J* needs to be executed at least once every *p* iterations). Other possible descriptions could also include: *J* needs to be executed *p* times per iteration with high priority.

*Dealing with Quantitative priorities:* To conduct experiments requiring QoS-like behavior, we implemented in the ScheduleFlow simulator a two-tiered priority queue system. Jobs that need execution in the subsequent simulation step are dynamically assigned to the high-priority queue, while all remaining jobs reside in the low-priority queue. This mechanism effectively translates the concept of immediate execution needs into a discrete priority value, allowing our qualitative backfilling algorithm to simulate QoS-driven scheduling decisions.

*Analysis jobs:* Given the exploratory and highly stochastic nature of analysis jobs, where execution times vary significantly based on individual studies and high-priority task lists can evolve dynamically based on intermediate results, we opted for a simulation approach grounded in real-world scenarios. Specifically, we modeled analysis tasks after medical simulations triggered by the generation of Magnetic Resonance Imaging (MRI) or Whole Slide Imaging (WSI) data. For this purpose, we selected a diverse set of 20 applications, characterized by the inherent stochasticity observed in prior work [9], to represent the unpredictable nature of these analytical workloads.

We simulate 30 loops of data generation and 20 applications with priority assigned randomly in an uniform fashion (when using two priority levels, around one third will be high-priority jobs). Each time a job is executed we assign an execution time based on the distributions observed in our previous work. Overall
<figure><img src="image_7.png" /><figcaption>Fig. 6: Utilization and average runs for experiments using value-based priorities and executing in-situ stochastic jobs with time constraints.</figcaption></figure>

we expect the total load of the analysis tasks to exceed the available resources by around 3x. We compare PRIORITY-BF to EASY-BF and CONSERVATIVE in two scenarios:

- *Value-based priorities:* jobs have values associated with their priority (e.g. for two levels, jobs will be either high, value 0, or low, value 1, priority)

- *QoS or frequency-based priorities:* each job has a step requirement associated, e.g. users would require a job to be executed at least every *X* step

In this last quantitative scenario, job priorities are determined by direct user input rather than inherent job characteristics, rendering EASY-BF incapable of incorporating these preferences. Consequently, our comparative analysis in this section focuses on contrasting our priority-aware algorithm with the standard EASY-BF and CONSERVATIVE approaches, neither of which account for job frequencies.

## 4.2 Simulation Results

In this section we operate under strict time constraints for analysis. Once data is received, the objective is to execute the maximum number of analysis tasks before the subsequent data generation phase. We explore two potential strategies for handling unfinished jobs when the allotted time expires: either terminate all incomplete tasks immediately, or allow them to complete, potentially encroaching upon the time allocated for analyzing the next batch of data.

*Value-based priorities.* Given the stochastic nature of the jobs, each experiment was repeated multiple times, and the aggregated results are presented in Figure 6. System utilization is calculated as defined in Section 3.2. The “average runs” metric indicates the average number of times a job was executed across all
<figure><img src="image_8.png" /><figcaption>Fig. 7: Average number of misses for QoS based priorities</figcaption></figure>

simulation loops, with a maximum possible value equal to the total number of simulation loops (30 in this case). Allowing unfinished jobs to complete beyond the time limit leads to increased overall utilization without negatively impacting the average number of times jobs are executed. Notably, PRIORITY-BF tends to achieve a slightly higher average number of runs when considering all jobs compared to classic EASY-BF. Furthermore, analyzing the combined data from all experiments reveals that PRIORITY-BF executes almost twice as many high-priority jobs compared to both EASY-BF and CONSERVATIVE, with high-priority jobs in average being executed in 90% of the loops.

*QoS-based priorities.* We define the frequency required for the execution of each job so that to create a total volume of execution that would require 3.5x the amount of resources to execute everything successfully. We make several experiments and compute the number of times a job was not executed when it was required (e.g. if a job needs to be executed every 2 steps and it is executed in step 1 and step 5, we record 3 misses). The total number of misses across all jobs in each experiment is reported in Figure 7a. Overall our solution has fewer misses and a lower standard deviation due to the fact that the EASY-BF strategy is not aware of the QoS restrictions and chooses jobs to better fit the space, running them across multiple steps.

Figure 7b shows the average number of misses across all experiments. In order to monitor the number of misses between our two scenarios, we converted our experiments that use value-based priorities into a QoS problem by making all priority jobs have a requirement of being executed every step and the low priority ones not having any requirement. PRIORITY-BF improves the number of misses by 30-45% in all cases.

# 5 Related Work

Batch scheduling in HPC has been an ongoing research topic. It requests users to submit an allocation value (how many resources the jobs need) and a time
limit/walltime (how long is the run is expected to last). It uses this information to take scheduling decisions often in a greedy way using the EASY-BF algorithm, where jobs are sorted according to a priority function and scheduled while allowing backfilling. Most of the existing work on priority-based scheduling in the HPC batch scheduling literature has been dedicated to improving the quality of a schedule, either by improving utilization, or other objectives such as mean bounded slowdown [3]. For example, Carastan-Santos et al. [4] have discussed replacing the FCFS priority function in EASY-BF by other functions such as Shortest Area First to improve the mean-bounded slowdown. Zrigui et al. [23] have shown that a simple classification (small or large), rather than the estimated runtime, is also enough to improve this objective.

Here, priorities are used to improve machine performance in their globality. An alternative to priority-based scheduling is Quality-Of-Service (QOS). In that case, jobs can have individual requirements (cost [19], deadline [22], energy [5]). This is a topic of particular interest in the Cloud Community where the volume of compute needed is less tight.

In HPC these solutions are presented differently when jobs have different priorities. Fan et al. [8] have discussed “time-critical” jobs: jobs whose demand is known 15-30 minutes before their release time, but that need to be executed almost instantaneously. To be able to do so, they allow the preemption and reconfiguration of some jobs to leave nodes available to the time-critical jobs. Our approach is different in the sense that we consider jobs with special needs to be no longer the exception. We consider the case of an overloaded system and we accept the fact that the total workload is higher than the capacity of the system. In this case, some jobs can be starved. Our goal is different in the sense that we want to execute all jobs with a high priority, and only execute other jobs if it impacts minimally the higher priority jobs.

# 6 Conclusions

This work introduced a new priority-aware scheduling algorithm for oversubscribed analysis clusters. Extremely simple in its description and implementation, it combines the benefits of EASY-BF and CONSERVATIVE backfilling. By allowing user-defined priorities, our solution effectively manages diverse job importance, shifting its behavior accordingly. Our results demonstrate the applicability of our solution in different scenarios. In particular this approach significantly improves the response time for high-priority jobs without impacting overall system utilization, offering a more nuanced and equitable resource allocation strategy for urgent computing within HPC environments. Finally, we have shown that this solution is quite expressive and can adapt to more quantitative approaches by updating priorities. Its simplicity makes it reliable and ready for large scale implementation which is going to be our next focus.

**Acknowledgments.** This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, for Research on Next Generation Data Management under Award Number
DE-FOA-00002725. This work has benefited from a national grant managed by the French National Research Agency (Agence Nationale de la Recherche) attributed to the Exa-DoST project of the NumPEx PEPR program, under the reference ANR-22-EXNU-0004. This research uses data that was generated from resources of the Argonne Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC02-06CH11357. It used resources from Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725.

**Disclosure of Interests.** The authors have no competing interests to declare that are relevant to the content of this article.

References

1. ALCF. ALCF Public Data. https://reports.alcf.anl.gov/data. Accessed January 2025.

2. P. H. Beckman, I. Beschastnikh, S. Nadella, and N. Trebon. Building an infrastructure for urgent computing. In *High Performance Computing Workshop*, 2006.

3. R. Boëzennec, F. Dufossé, and G. Pallez. Qualitatively analyzing optimization objectives in the design of HPC resource manager. *ACM Transactions on Modeling and Performance Evaluation of Computing Systems*, 9(4):1–28, 2024.

4. D. Carastan-Santos, R. Y. De Camargo, D. Trystram, and S. Zrigui. One Can Only Gain by Replacing EASY Backfilling: A Simple Scheduling Policies Case Study. In *IEEE/ACM CCGrid’19*. IEEE, 2019.

5. N. Cordeschi, M. Shojafar, D. Amendola, and all. Energy-efficient adaptive networked datacenters for the QoS support of real-time applications. *The Journal of Supercomputing*, 71:448–478, 2015.

6. Y. Du, L. Marchal, G. Pallez, and Y. Robert. Improving Batch Schedulers With Node Stealing for Failed Jobs. *CCPE*, 36(12):e8043, 2024.

7. J. Ejarque, R. M. Badia, L. Albertin, and all. Enabling dynamic and intelligent workflows for HPC, data analytics, and AI convergence. *Future Generation Computer Systems*, 134:414–429, Sept. 2022.

8. Y. Fan, Z. Lan, P. Rich, W. Allcock, and all. Hybrid workload scheduling on HPC systems. In *IEEE IPDPS’22*, pages 470–480, 2022.

9. A. Gainaru, B. Goglin, V. Honoré, and G. Pallez. Profiles of upcoming HPC applications and their impact on reservation strategies. *IEEE TPDS*, 32(5):1178–1190, 2021.

10. A. Gainaru, G. Pallez (Aupy), H. Sun, and P. Raghavan. Speculative scheduling for stochastic HPC applications. In *ICPP’19*, pages 1–10, 2019.

11. A. Gainaru, N. Podhorszki, L. Dulac, Q. Gong, and all. To derive or not to derive: I/O libraries take charge of derived quantities computation. In *SBAC-PAD’24*, pages 105–115, 2024.

12. H. G. Im, A. Trouvé, C. J. Rutland, and J. H. Chen. Terascale high-fidelity simulations of turbulent combustion with detailed chemistry. Technical report, University of Maryland, College Park MD, 2012.

13. D. A. Lifka. The ANL/IBM SP scheduling system. In *Workshop on Job Scheduling Strategies for Parallel Processing*, pages 295–303. Springer, 1995.

14. P. Malakar, V. Vishwanath, T. Munson, and all. Optimal scheduling of in-situ analysis for large-scale scientific simulations. In *SC’15*, pages 1–11, 2015.
15. G. Marotta, E. Lena, G. Brajnik, I. Novak, M. Colciago, E. Giani, and C. Baffa. Enhancing ska software testing through data mining strategies. In *Software and Cyberinfrastructure for Astronomy VIII*, volume 13101, pages 168–181. SPIE, 2024.

16. 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, 2002.

17. J. J. Nichol, M. G. Peterson, K. J. Peterson, and all. Machine learning feature analysis illuminates disparity between E3SM climate models and observed climate change. *Journal of Computational and Applied Mathematics*, 395:113451, 2021.

18. T. Patel, Z. Liu, R. Kettimuthu, P. Rich, and all. Job characteristics on large-scale systems: long-term analysis, quantification, and implications. In *SC20*, pages 1–17. IEEE, 2020.

19. H. R. Qavami, S. Jamali, M. K. Akbari, and B. Javadi. Dynamic resource provisioning in cloud computing: a heuristic Markovian approach. In *CloudComp'13*, pages 102–111. Springer, 2014.

20. SLURM-Workload-Manager-v24.11. Multifactor priority plugin. https://slurm.schedmd.com/priority_multifactor.html, August 2023. Accessed Jan. 2025.

21. N. Tan, K. Assogba, W. J. Ashworth, B. Bogale, and all. Towards Affordable Reproducibility Using Scalable Capture and Comparison of Intermediate Multi-Run Results. In *Middleware'24*, page 392–403, 2024.

22. C. Vecchiola, R. N. Calheiros, D. Karunamoorthy, and R. Buyya. Deadline-Driven Provisioning of Resources for Scientific Applications in Hybrid Clouds with Aneka. *Future Generation Computer Systems*, 28(1):58–65, 2012.

23. S. Zrigui, R. Y. de Camargo, A. Legrand, and D. Trystram. Improving the performance of batch schedulers using online job runtime classification. *Journal of Parallel and Distributed Computing*, 164:83–95, 2022.