Resource Availability-Aware Advance Reservation for Parallel Jobs with Deadlines

Bo Li, Yijian Pei, Bin Shen, Hao Wu, Min He, Jundong Yang

Abstract Advance reservation (AR) is crucial for guaranteeing Quality of Service (QoS) by providing exclusive access to resources over defined intervals. However, efficiently organizing and allocating resources for parallel AR jobs with deadline constraints remains a significant challenge. This paper introduces a slot-based data structure to manage multiprocessor availability and proposes a suite of scheduling policies for dynamic AR requests. Through simulations using various job sizes, durations, and system loads, we investigate performance metrics. Our results reveal that while job characteristics and system load impact performance, the PE-Worst-Fit algorithm achieves the highest acceptance rate, whereas the First-Fit algorithm minimizes average slowdown. This framework provides a robust solution for resource allocation in large-scale computing systems.

Introduction

In high-performance computing environments like Grids and clusters, Advance Reservation (AR) is essential for users who require guaranteed resource availability at specific times. Traditional schedulers often handle "immediate deadlines," where a job must start exactly at its ready time. However, real-world requirements are frequently more flexible. A user might specify a "general deadline"—for instance, requiring 32 processors for two hours to be completed by a specific end time. This flexibility, while beneficial for users, complicates scheduling as the system must identify optimal "holes" in the resource schedule to minimize fragmentation and maximize throughput.

The Scheduling Problem: General Deadlines

The core challenge lies in managing the "general deadline" window. Unlike rigid start times, a general deadline allows the scheduler to shift a job's execution within a window defined by its ready time and its final deadline.

Figure 1: Scheduling an Advance Reservation (AR) job within a flexible window defined by ready time and deadline.

As shown in Figure 1, the scheduler must evaluate multiple potential slots (represented as availability rectangles, AR n) to place a new job without overlapping with existing tasks (job1, job2, job3). Efficiently tracking these available "rectangles" of time and processing elements (PEs) is critical for system performance.

Methodology

To address this, the authors propose a linked-list-based data structure called AvailRectList, paired with a sorted TimeSet. The AvailRectList records the state of PEs as rectangles of availability, updating whenever the set of busy PEs changes. This allows for efficient search operations that identify "maximum availability rectangles"—the largest contiguous blocks of time and processors available.

The study evaluates several scheduling policies:

  • First Fit (FF): Selects the earliest possible start time.
  • Best Fit (PE, Duration, or both): Chooses the slot that leaves the minimum leftover resource in a given availability rectangle.
  • Worst Fit (PE, Duration, or both): Chooses the slot that leaves the maximum leftover resource.

Performance was tested using a hybrid dataset combining real-world traces from the LANL-CM5 supercomputer and synthetic workloads generated by the Feitelson-Lublin Model.

Key Insights and Results

The research highlights a significant trade-off between system efficiency and user experience.

  • The "Worst Fit" Paradox: Contrary to many optimization problems where "Best Fit" is preferred, the PE-Worst-Fit (PE_W) algorithm—which selects rectangles with the most free processors—yielded the highest job acceptance rate. By avoiding the "shaving off" of small resource slivers from tight spots, it preserves larger contiguous blocks for future large-scale jobs.
  • Efficiency vs. Experience: Policies that maximize the Acceptance Rate (benefiting the provider) often increase the Average Slowdown (detrimental to the user). For instance, First Fit (FF) consistently resulted in the lowest average slowdown because it schedules jobs as early as possible, minimizing wait times.
  • The Impact of Flexibility: Increasing the deadline window (scheduling flexibility) improves acceptance rates across all algorithms but tends to increase average slowdown as the scheduler delays jobs to optimize resource packing.

Conclusion

The proposed slot-based data structure and scheduling policies offer a scalable solution for managing parallel AR jobs in large-scale systems. While PE-Worst-Fit is the superior choice for maximizing accepted requests, First-Fit remains the best option for minimizing user wait times. Future work will explore heterogeneous resources (varying RAM/GPU capabilities), malleable jobs that can adjust resource usage, and the impact of job preemption on scheduling dynamics.

Summary updated

Abstract

Advance reservation is important to guarantee the quality of services of jobs by allowing exclusive access to resources over a defined time interval on resources. It is a challenge for the scheduler to organize available resources efficiently and to allocate them for parallel AR jobs with deadline constraint appropriately. This paper provides a slot-based data structure to organize available resources of multiprocessor systems in a way that enables efficient search and update operations, and formulates a suite of scheduling policies to allocate resources for dynamically arriving AR requests. The performance of the scheduling algorithms were investigated by simulations with different job sizes and durations, system loads and scheduling flexibilities. Simulation results show that job sizes and durations, system load and the flexibility of scheduling will impact the performance metrics of all the scheduling algorithms, and the PE-Worst-Fit algorithm becomes the best algorithm for the scheduler with the highest acceptance rate of AR requests, and the jobs with the First-Fit algorithm experience the lowest average slowdown. The data structure and scheduling policies can be used to organize and allocate resources for parallel AR jobs with deadline constraint in large-scale computing systems.
BibTeX
@misc{li2012resource,
  author = {Bo Li and Yijian Pei and Bin Shen and Hao Wu and Min He and Jundong Yang},
  title = {{Resource Availability-Aware Advance Reservation for Parallel Jobs with Deadlines}},
  year = {2012},
  eprint = {1203.0740},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.0740},
}
Figure