How Do Batch Schedulers Like Slurm Allocate Compute Nodes?

Batch job schedulers like Slurm manage shared high-performance computing clusters by matching incoming user requests to available hardware resources while maintaining equitable access over time. They achieve this through a combination of resource-aware node selection, multi-factor priority scoring, and time-decayed fair-share accounting. By balancing immediate cluster utilization with long-term usage history, these schedulers prevent individual users or groups from monopolizing the system.

Resource Allocation and Node Selection

When a user submits a batch job, they specify resource requirements such as the number of nodes, CPU cores, memory, wall-clock time, and specialized hardware like GPUs. The scheduler evaluates these constraints against the current state of the cluster, which is organized into logical groups of nodes called partitions.

To place a job, the scheduler runs a node selection algorithm that filters out unavailable, drained, or incompatible nodes. It then scores the remaining candidates based on factors such as network topology, memory locality, and fragmentation. Topology-aware scheduling, for example, prefers assigning nodes that share the same network switch or rack to minimize communication latency for parallel workloads using MPI.

Multi-Factor Priority Queuing

Because demand on large clusters often exceeds capacity, pending jobs wait in a queue ordered by priority. Rather than using a simple first-in, first-out approach, modern schedulers compute a composite priority score \(P\) for each job as a weighted sum of multiple factors:

\[P = w_{\text{age}} F_{\text{age}} + w_{\text{fairshare}} F_{\text{fairshare}} + w_{\text{size}} F_{\text{size}} + w_{\text{qos}} F_{\text{qos}} + w_{\text{partition}} F_{\text{partition}}\]

Each \(F\) term represents a normalized factor between \(0\) and \(1\), and each \(w\) represents an administrator-defined weight. The age factor increases the longer a job waits, preventing starvation. Quality of Service (QOS) and partition weights allow administrators to prioritize urgent or specialized workloads.

Enforcing Fair-Share Queues

The fair-share factor \(F_{\text{fairshare}}\) ensures that users and research groups receive their allocated share of compute time over the long term. Administrators assign each account or user a target share \(S\), representing their entitled fraction of the cluster. The scheduler tracks their actual historical usage \(U\) in resource-seconds.

To prevent past usage from permanently penalizing a user, historical usage decays exponentially over time with a configured half-life \(D\):

\[U_{\text{effective}}(t) = \sum_{i} u_i \cdot 2^{-\frac{t - t_i}{D}}\]

Here, \(u_i\) is the usage recorded at time \(t_i\), and \(t\) is the current time. The scheduler compares the effective usage to the target share. If a user has consumed more than their share, their fair-share factor drops, lowering their queue priority relative to users who have consumed less.

In hierarchical organizations, schedulers like Slurm use algorithms such as Fair-Tree to evaluate fair-share across nested accounts. Fair-Tree compares sibling accounts at each level of the organizational tree, ensuring that heavy usage by one research group does not unfairly penalize an unrelated department.

Backfill Scheduling and Utilization

Strict priority queuing can leave compute nodes idle when a high-priority job requires a large number of nodes that are not yet free. To avoid wasting cycles, schedulers use backfill scheduling.

The scheduler reserves future time slots for the highest-priority pending jobs based on the estimated end times of currently running jobs. It then scans lower-priority jobs in the queue and starts any smaller, shorter job that can finish before the reserved start time of the top-priority job. This approach keeps cluster utilization high without delaying large, high-priority workloads.