Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Ahead of the Curve: Leveraging Periodicity to Improve Job Placement in Data Centers
To improve data center efficiency, job schedulers often overcommit computing resources such that the sum of the maximum resource requirements across running jobs on a server exceeds its resource capacity while relying on statistical multiplexing of workloads at runtime to reduce the likelihood of saturating capacity and violating applications’ service level objectives. The challenge with overcommitting resources is that future job resource demand varies widely over time. As a result, jobs’ collective resource usage may exceed resource capacity if their periods of high demand align. Our key insight is that many jobs often exhibit some periodicity in their resource usage, which schedulers can leverage to improve resource usage predictions and job placement decisions. To leverage this insight, we show how to model jobs as simple periodic functions and then develop a period-aware placement policy that increases resource utilization while mitigating performance degradation due to jobs’ collective resource usage exceeding resource capacity. We evaluate our approach on a publicly-available job trace from a major cloud platform, and show that it yields low (<30%) error for a large fraction (∼80%) of periodic jobs. We then evaluate our period-aware placement policy on small problem instances, and show that it is much closer to the NP-hard optimal policy than current state-of-theart policies. Finally, we evaluate our approach on an industry job trace, and show that combining our periodic models and periodaware placement policy results in the best of both worlds: higher average server utilization and lower performance degradation by more than 2× compared to the existing state-of-the-art.  more » « less
Award ID(s):
2325956 2211888 2213636
PAR ID:
10682062
Author(s) / Creator(s):
 ;  ;  ;  
Publisher / Repository:
IEEE
Date Published:
ISBN:
979-8-3315-3465-3
Page Range / eLocation ID:
225 to 235
Format(s):
Medium: X
Location:
Rennes, France
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, IEEE Transactions on Parallel and Distributed Systems)
    null (Ed.)
    While cloud platforms enable users to rent computing resources on demand to execute their jobs, buying fixed resources is still much cheaper than renting if their utilization is high. Thus, optimizing cloud costs requires users to determine how many fixed resources to buy versus rent based on their workload. In this paper, we introduce the concept of a waiting policy for cloud-enabled schedulers, which is the dual of a scheduling policy, and show that the optimal cost depends on it. We define multiple waiting policies and develop simple analytical models to reveal their tradeoff between fixed resource provisioning, cost, and job waiting time. We evaluate the impact of these waiting policies on a year-long production batch workload consisting of 14M jobs run on a 14.3k-core cluster, and show that a compound waiting policy decreases the cost (by 5%) and mean job waiting time (by 7x) compared to a fixed cluster of the current size. 
    more » « less
  2. ; ; ; (, SC20: International Conference for High Performance Computing, Networking, Storage and Analysis)
    null (Ed.)
    While cloud platforms enable users to rent computing resources on demand to execute their jobs, buying fixed resources is still much cheaper than renting if their utilization is high. Thus, optimizing cloud costs requires users to determine how many fixed resources to buy versus rent based on their workload. In this paper, we introduce the concept of a waiting policy for cloud-enabled schedulers, which is the dual of a scheduling policy, and show that the optimal cost depends on it. We define multiple waiting policies and develop simple analytical models to reveal their tradeoff between fixed resource provisioning, cost, and job waiting time. We evaluate the impact of these waiting policies on a year-long production batch workload consisting of 14Mjobs run on a 14.3k-core cluster, and show that a compound waiting policy decreases the cost (by 5%) and mean job waiting time (by 7×) compared to a fixed cluster of the current size. 
    more » « less
  3. ; ; (, Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    In modern computing systems, jobs' resource requirements often vary over time. Accounting for this temporal variability during job scheduling is essential for meeting performance goals. However, theoretical understanding on how to schedule jobs with time-varying resource requirements is limited. Motivated by this gap, we propose a new setting of the stochastic bin-packing problem in service systems that allows for time-varying job resource requirements, also referred to as 'item sizes' in traditional bin-packing terms. In this setting, a job or 'item' must be dispatched to a server or 'bin' upon arrival. Its resource requirement may vary over time while in service, following a Markovian assumption. Once the job's service is complete, it departs from the system. Our goal is to minimize the expected number of active servers, or 'non-empty bins', in steady state. Under our problem formulation, we develop a job dispatch policy, named Join-Reqesting-Server (JRS). Broadly, JRS lets each server independently evaluate its current job configuration and decide whether to accept additional jobs, balancing the competing objectives of maximizing throughput and minimizing the risk of resource capacity overruns. The JRS dispatcher then utilizes these individual evaluations to decide which server to dispatch each arriving job to. The theoretical performance guarantee of JRS is in the asymptotic regime where the job arrival rate scales large linearly with respect to a scaling factor r. We show that JRS achieves an additive optimality gap of O(√r) in the objective value, where the optimal objective value is Θ(r). When specialized to constant job resource requirements, our result improves upon the state-of-the-art o(r) optimality gap. Our technical approach highlights a novel policy conversion framework that reduces the policy design problem into a single-server problem. 
    more » « less
  4. ; ; ; ; ; ; (, Performance Evaluation)
    Modern data center workloads are composed of multiserver jobs, computational jobs that require multiple servers in order to run. A data center can run many multiserver jobs in parallel, as long as it has sufficient resources to meet their individual demands. Multiserver jobs are generally stateful, meaning that job preemptions incur significant overhead from saving and reloading the state associated with running jobs. Hence, most systems try to avoid these costly job preemptions altogether. Given these constraints, a scheduling policy must determine what set of jobs to run in parallel at each moment in time to minimize the mean response time across a stream of arriving jobs. Unfortunately, simple non-preemptive policies such as First-Come First-Served (FCFS) may leave many servers idle, resulting in high mean response times or even system instability. Our goal is to design and analyze non-preemptive scheduling policies for multiserver jobs that maintain high system utilization to achieve low mean response time. One well-known non-preemptive scheduling policy, Most Servers First (MSF), prioritizes jobs with higher server needs and is known for achieving high resource utilization. However, MSF causes extreme variability in job waiting times, and can perform significantly worse than FCFS in practice. To address this issue, we propose and analyze a class of scheduling policies called Most Servers First with Quickswap (MSFQ) that performs well in a wide variety of cases. MSFQ reduces the variability of job waiting times by periodically granting priority to other jobs in the system. We provide both stability results and an analysis of mean response time under MSFQ to prove that our policy dramatically outperforms MSF in the case where jobs either request one server or all the servers. In more complex cases, we evaluate MSFQ in simulation. We show that, with some additional optimization, variants of the MSFQ policy can greatly outperform MSF and FCFS on real-world multiserver job workloads. 
    more » « less
  5. ; ; (, Proceedings of the 29th Workshop on Job Scheduling Strategies for Parallel Processing)
    The proliferation of AI/ML demands democratizing access to GPU clusters. An inefficient way is to provide exclusive access to an entire GPU node for training jobs. This results in severe cluster underutilization when training jobs do not require the GPU at full capacity. The problem exacerbates in the cloud, where multi-tenant jobs wait for resources to be available, affecting the overall makespan. While modern cluster schedulers allow parallel execution of tenants’ jobs, they use a reservation-based policy, which causes memory fragmentation. Evidence from real-world training clusters shows a huge volume of GPU memory left stranded. In this paper, we propose GOA (GPU-oversubscription-aware), an execution framework that embraces memory-safe oversubscription for ML training workloads. GOA abandons the existing reservation model and schedules jobs as they arrive. To avoid out-of-memory crashes, on each GPU node, GOA dynamically regulates active jobs such that the col lective memory usage is always under the GPU memory capacity while maximizing memory utilization. The local efficiencies will scale seamlessly, delivering an increase in cluster utilization and cost efficiency. We evaluated GOA as a proof-of-concept in a GPU cluster simulator, focusing on the impact of makespan and memory utilization. The result shows that GOA reduces the overall makespan by up to 82%, with 68% on average, and improves GPU utilization by 11% compared to standard policies adopted by existing cluster schedulers. The promising results encourage future work on improving cluster efficiency for ML training. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email