TL;DR
This paper tackles the challenge of efficiently executing multiple parallel applications on a shared computing platform. Instead of running them sequentially, the authors propose "co-scheduling" where applications are grouped into "packs" to run concurrently, significantly reducing overall execution time and energy consumption. They develop and evaluate several heuristics that achieve substantial performance gains over traditional scheduling methods.
What Problem Does This Paper Address?
Modern high-performance computing (HPC) platforms are equipped with a vast number of processors, enabling individual applications to achieve impressive speedups. However, dedicating all resources to a single application often leads to diminishing returns due to overheads like communication and load imbalance. This inefficient resource utilization not only wastes energy but also prolongs the completion time of other waiting applications. The paper addresses this by exploring "co-scheduling," a strategy where multiple applications are run concurrently in groups (packs). The core problem is to determine the optimal way to partition applications into packs and assign processors to each application within a pack to minimize the total execution time (makespan) of the entire workload. This is particularly relevant in the context of rising energy costs and the need for higher system throughput.
Methods
The paper introduces a formal model for co-scheduling, defining "packs" of tasks and the objective of minimizing the sum of pack execution times. They analyze the computational complexity of this problem, proving that it's NP-complete for packs of size 3 or more, but polynomial for packs of size 1 or 2. To tackle the NP-complete general case, they propose several algorithmic approaches:
- Optimal Pack Scheduling: For a given pack of tasks, they present an algorithm (Algorithm 1) to optimally assign processors to minimize the pack's execution time. This algorithm is greedy and runs in $O(p \log k)$ time, where $p$ is the number of processors and $k$ is the pack size.
- Integer Linear Programming (ILP): They formulate the general co-scheduling problem as an ILP, which can find optimal solutions but is computationally expensive.
- Approximation Algorithm (PACK-APPROX): A 3-approximation algorithm is presented for the general $p$-IN-$p$-COSCHEDULE problem. This algorithm iteratively refines a schedule by adding processors to tasks.
- Heuristics: Several practical heuristics are developed and evaluated:
- RANDOM-PACK/RANDOM-PROC: These heuristics randomly generate packs or processor assignments, relying on the optimal pack scheduling algorithm.
- PACK-BY-PACK: This heuristic aims to create "well-balanced" packs by considering tasks with execution times close to the maximum within a pack. It uses a parameter $\epsilon$ to control pack formation.
- PACK-APPROX: This heuristic is adapted from the approximation algorithm for pack sizes up to $k$.
Datasets
The paper evaluates their heuristics on three types of workloads:
- Workload-I: Composed of 10 real-world parallel scientific applications (VASP, ABAQUS, LAMMPS, Petsc).
- Workload-II: A synthetic benchmark suite designed to model a larger set of scientific applications with varying characteristics, including different sequential execution times and overheads.
- Workload-III: A large synthetic workload with 260 tasks, used to study scalability.
The speedup profiles of these applications were modified to satisfy the non-increasing execution time and non-decreasing work conditions, which are standard assumptions for parallel task models.
Key Insights and Ideas
- Co-scheduling is a win-win: The core insight is that co-scheduling, by grouping applications, can simultaneously improve system throughput (more work done in less time) and reduce energy consumption, without necessarily increasing individual application execution times significantly.
- NP-completeness is a hurdle, but heuristics shine: While the general co-scheduling problem is NP-complete, the paper demonstrates that well-designed heuristics can achieve near-optimal performance in practice.
- Pack formation matters: The way applications are grouped into packs significantly impacts the overall performance. Heuristics that focus on creating balanced packs (like PACK-BY-PACK) tend to outperform random approaches.
- Trade-offs are manageable: The paper shows that even with a slight increase in individual task execution times due to fewer processors, the overall workload completion time and energy usage can be drastically reduced.
Key Results
- Significant Cost Reduction: Co-scheduling, particularly with heuristics like PACK-BY-PACK and PACK-APPROX, can reduce the total execution time (cost) by over 35% for Workload-I and over 80% for Workload-II compared to a 1-pack schedule (running each task with maximum parallelism).
- High Packing Ratios: The proposed heuristics achieve packing ratios close to 1, indicating efficient utilization of processors with minimal idle time.
- Improved Response Times: Co-scheduling leads to substantial reductions in average response times, making it attractive for users. Gains of over 80% were observed for Workload-II.
- Scalability: The heuristics demonstrate good scalability on larger workloads (Workload-III), maintaining significant cost and response time reductions.
- Heuristic Performance: PACK-BY-PACK and PACK-APPROX consistently outperformed random heuristics, with PACK-BY-PACK-9 being identified as the heuristic of choice due to its balance of performance and computational cost.
- Running Times: The heuristics are computationally efficient, running within milliseconds even for large workloads.
Limitations and Future Work
- NP-Completeness: The inherent NP-completeness of the problem means that finding a guaranteed optimal solution for large instances is computationally infeasible.
- Heuristic Performance: While the proposed heuristics perform well, they are not guaranteed to be optimal. The paper notes that further improvements from running heuristics with more parameter values (e.g., $\epsilon$ for PACK-BY-PACK) yielded diminishing returns.
- Future Work: The authors suggest exploring hybrid approaches that combine co-scheduling with dynamic voltage and frequency scaling (DVFS) for further energy savings. They also plan to extend their work towards deployment in university-scale computing facilities where workload attributes might be more stable over time. Investigating more sophisticated pack formation strategies beyond the greedy approach is also a potential avenue.
Summary updated