Job Scheduling Using Successive Linear Programming Approximations of a Sparse Model

Stéphane Chrétien, Jean-Marc Nicod, Laurent Philippe, Veronika Rehn-Sonigo, Lamiel TochEuro-par 2012 · DOI

TL;DR

This paper introduces a novel approach to scheduling parallel jobs on clusters by using successive linear programming (LP) approximations to solve a sparse model. This method aims to find near-optimal schedules for rigid and moldable jobs, offering a promising alternative to existing heuristics, especially for smaller problem instances.

What Problem Does This Paper Address?

The efficient scheduling of parallel jobs on shared computing resources like clusters and multiprocessor systems is a critical challenge. The goal is typically to minimize the "makespan," which is the completion time of the last job. This problem is known to be NP-Hard, meaning that finding the absolute best solution becomes computationally infeasible as the number of jobs or processors increases. While many heuristic algorithms exist, they often provide suboptimal solutions. This paper tackles the problem of scheduling both "rigid" jobs (which require a fixed number of processors) and "moldable" jobs (which can adjust their processor count at the start) by proposing a new method based on mathematical optimization techniques.

Methods

The core of the proposed method lies in formulating the job scheduling problem as an integer linear program (ILP). However, solving ILPs directly is computationally expensive. To overcome this, the authors employ a two-step approach:

  1. Sparsity Promoting Penalization: They relax the binary constraints of the ILP and introduce a non-convex objective function that minimizes the $l_p$-quasi-norm ($0 < p < 1$) of the decision variables. This technique, inspired by sparse recovery in statistics, encourages solutions where only a few variables are non-zero, aiming to recover the desired discrete job assignments. The $l_1$ norm is found to be unsuitable here because the constraints inherently lead to a constant $l_1$ norm.
  2. Successive Linear Programming (LP) Approximations: Since the $l_p$-quasi-norm is non-differentiable, they use successive LP approximations to linearize the objective function iteratively. This involves using a generalized gradient (Clarke subdifferential) and Taylor expansions to approximate the non-linear objective at each step, allowing a standard LP solver to be used.

The algorithm iteratively refines the time horizon and the LP approximation until a satisfactory schedule is found or a maximum number of iterations is reached. A hybrid approach is also introduced, where jobs that don't get a clear assignment from the LP are scheduled using the traditional Largest Task First (LTF) algorithm.

Datasets

Not discussed in the paper. The authors use synthetic workloads generated with uniform distributions for their simulations.

Key Insights and Ideas

  • Bridging Optimization and Scheduling: The paper demonstrates how advanced mathematical optimization techniques, specifically sparsity-promoting penalization and LP approximations, can be effectively applied to a complex scheduling problem.
  • The $l_p$-quasi-norm for Scheduling: The choice of the $l_p$-quasi-norm ($p < 1$) is crucial. It's a more appropriate sparsity-promoting penalty than the $l_1$ norm in this context because it can encourage more extreme solutions (closer to 0 or 1) when the $l_1$ norm is constrained to be constant.
  • Iterative Refinement is Key: The successive LP approximation scheme, combined with an iterative adjustment of the time horizon, is essential for finding feasible and near-optimal solutions.
  • Hybrid Approach for Robustness: The hybrid strategy, combining the LP approximation with LTF for "fuzzy" assignments, significantly improves the algorithm's practical performance and robustness, especially for larger problem instances.

Key Results

  • The pure successive LP approximation algorithm shows good performance for makespan minimization on smaller instances (up to dozens of jobs and PEs).
  • For larger instances, the hybrid approach (successive LP + LTF) provides significant improvements over the standard LTF algorithm, achieving up to a 20% reduction in makespan in some cases.
  • The hybrid approach offers better results than the unmodified LP approximation algorithm, especially as the number of jobs and PEs increases.
  • The standard deviation of the results from the hybrid approach is generally lower than that of the LTF algorithm, indicating more consistent performance.
  • The computational time of the LP-based methods is significantly higher than LTF, though for smaller instances (around 15 jobs), the time taken is still considered reasonable (under 1.5 minutes).

Limitations and Future Work

  • Computational Cost: The primary limitation is the high computational cost of the successive LP approximation method compared to simpler heuristics like LTF.
  • Theoretical Guarantees: The paper acknowledges the lack of theoretical guarantees for the convergence of the proposed iterative procedure.
  • Future Work: The authors plan to explore methods like the Split Bregman Method to speed up solving times. They also intend to investigate other relaxations of the linear program and develop a multi-level scheduling approach that distinguishes between small and large jobs. Applying the method to different job collections and further optimizing the computational aspects are also future directions.

Summary updated

BibTeX
@inproceedings{chretien2012job,
  author = {Stéphane Chrétien and Jean-Marc Nicod and Laurent Philippe and Veronika Rehn-Sonigo and Lamiel Toch},
  title = {{Job Scheduling Using Successive Linear Programming Approximations of a Sparse Model}},
  booktitle = {Euro-par},
  year = {2012},
  doi = {10.1007/978-3-642-32820-6\_14},
}
Figure