Gang Scheduling Extensions for I/O Intensive Workloads

Yanyong Zhang, Antony Yang, Anand Sivasubramaniam, José E. MoreiraJSSPP 2003 · DOI

TL;DR

This paper tackles the challenge of scheduling parallel jobs in modern supercomputing systems that are increasingly bottlenecked by I/O operations. They propose and evaluate several extensions to gang scheduling, culminating in "Migrate-IOGS," which significantly improves performance for I/O-intensive workloads by intelligently co-locating jobs with their data and using migration to further optimize resource utilization.

What Problem Does This Paper Address?

Modern scientific applications are generating and processing massive datasets, making I/O performance a critical factor in overall application speed. Traditional supercomputing systems often use dedicated I/O nodes, but this approach doesn't scale well. A "serverless" approach, where compute nodes also act as I/O nodes, offers better scalability but introduces a new challenge: job performance becomes highly dependent on whether its tasks are co-located with the file blocks they need.

Existing gang scheduling (GS) techniques, widely used in supercomputing, are designed to maximize system utilization by time-sharing processors among jobs. However, GS is oblivious to the spatial locality of data, meaning jobs might be scheduled far from their required files, leading to significant performance degradation for I/O-intensive workloads. This paper investigates how to make gang scheduling "I/O-aware" to address this performance gap.

Methods

The authors propose a series of scheduling strategies, building upon the standard gang scheduling framework:

  • I/O-Aware Gang Scheduling (IOGS): This is the first proposed extension. IOGS prioritizes scheduling jobs to the nodes where their required file partitions reside. This aims to minimize remote I/O costs, thereby shortening job execution times. However, this strict co-location can lead to matrix fragmentation.
  • Adaptive I/O-Aware Gang Scheduling (Adaptive-IOGS): To balance the benefits of IOGS (local I/O) and GS (matrix utilization), Adaptive-IOGS acts as a hybrid. It first attempts to schedule jobs to their file nodes (like IOGS). If this isn't possible, it falls back to a GS-like heuristic to maximize matrix utilization, preventing fragmentation and job starvation.
  • Migration Adaptive I/O Aware Gang Scheduling (Migrate-IOGS): This is the most advanced scheme. It builds upon Adaptive-IOGS by introducing a migration phase. After jobs leave the system, Migrate-IOGS checks if any remote jobs now have their file nodes freed. If so, it migrates these jobs to their local file nodes to further reduce execution time and fragmentation. This phase is inserted after cleaning the matrix and before compacting it.

The core scheduling framework for all these strategies involves four steps: CleanMatrix, CompactMatrix, Schedule, and FillMatrix. The novelty lies in how the Schedule and MigrateMatrix (in the case of Migrate-IOGS) phases are implemented to incorporate I/O awareness and migration.

Datasets

The paper uses synthetic workloads generated to mimic characteristics of actual workloads from the ASCI Blue-Pacific system at Lawrence Livermore National Laboratory. They define workloads based on job arrival rates, job sizes, and I/O intensity. The experiments cover a wide range of these parameters, including 81 different load combinations and 7 different I/O intensity levels, resulting in 567 distinct workloads.

Key Insights and Ideas

  • I/O Intensity is Key: The performance of scheduling strategies is highly dependent on the I/O intensity of the workload. What works well for CPU-bound jobs can be detrimental for I/O-bound ones.
  • Trade-off Between Local I/O and Matrix Utilization: IOGS excels at minimizing execution time for I/O-intensive jobs by ensuring local data access, but this can lead to significant fragmentation of the scheduling matrix. Standard GS, conversely, maximizes matrix utilization but can incur high remote I/O costs.
  • Adaptive Strategies are Necessary: A single, fixed strategy is not optimal. Adaptive-IOGS successfully bridges the gap by dynamically choosing between IOGS-like and GS-like behavior based on whether local file nodes are available.
  • Migration is a Powerful Optimization: Migrate-IOGS demonstrates that proactively moving jobs to their freed file nodes can significantly boost performance, especially for I/O-intensive workloads, by reducing both execution time and fragmentation.
  • Migration Cost is Often Negligible: The study shows that the overhead of migration is typically small compared to the performance gains, making it a viable technique.

Key Results

  • IOGS vs. GS: For high I/O intensity workloads (rIO = 0.5), IOGS consistently outperforms GS in both slowdown and wait times, often by over 100%. For low to medium I/O intensity workloads, GS performs better.
  • Adaptive-IOGS: This strategy performs best across a wide range of scenarios, offering a good balance. It is particularly effective for medium I/O workloads and high loads of I/O-intensive workloads.
  • Migrate-IOGS: This scheme consistently outperforms the other three strategies across various workloads, especially for I/O-intensive scenarios. For example, at high loads for I/O-intensive workloads, Migrate-IOGS improves performance by 100% compared to IOGS, achieving significantly more local job assignments.
  • Migration Impact: The benefits of migration are substantial, with performance improvements of at least 90% for I/O-intensive workloads when migration is enabled. The impact of migration cost is minimal, and a moderate limit on the number of migrated tasks (Q=64) captures most of the benefits.

Limitations and Future Work

  • Migration Cost and Capacity: While the paper shows migration cost is often negligible, it acknowledges that migration has an overhead (checkpoint/restart) and a system capacity limit (parameter Q). Further investigation into the optimal values for these parameters is suggested.
  • Random Choice in MigrateMatrix: When multiple rows are available for migration, Migrate-IOGS currently chooses randomly. The paper suggests exploring strategies like choosing the row with fewer free slots to better accommodate larger waiting jobs.
  • Homogeneous Workloads: The initial experiments focus on homogeneous workloads where all jobs have the same I/O intensity. The paper briefly explores mixed workloads, indicating that Migrate-IOGS remains superior. Further detailed analysis of mixed workloads could be a future direction.
  • Synthetic Workloads: While based on real system characteristics, the workloads are synthetic. Evaluating these strategies on real-world applications would provide further validation.

Summary updated

BibTeX
@inproceedings{zhang2003gang,
  author = {Yanyong Zhang and Antony Yang and Anand Sivasubramaniam and José E. Moreira},
  title = {{Gang Scheduling Extensions for I/O Intensive Workloads}},
  booktitle = {JSSPP},
  year = {2003},
  doi = {10.1007/10968987\_10},
}
Figure