Predicting Dynamic Memory Requirements for Scientific Workflow Tasks

Jonathan Bader, Nils Diedrich, Lauritz Thamsen, Odej Kao

TL;DR

This paper introduces a novel "k-Segments" method that predicts the dynamic memory needs of scientific workflow tasks over time, rather than just a single peak. By dividing a task's execution into segments and learning memory usage for each, they significantly reduce resource wastage and improve cluster efficiency.

What Problem Does This Paper Address?

Modern scientific research, spanning fields like bioinformatics and physics, generates massive datasets. To process this data, scientists rely on complex scientific workflow systems that automate, parallelize, and monitor data analysis pipelines. These workflows are executed on large cluster infrastructures, managed by resource managers. A critical aspect of this management is allocating the right amount of computational resources, particularly memory, to each task.

The challenge is that users often have to manually estimate these memory requirements. Underestimating can lead to task failures, disrupting the entire workflow. To avoid this, users tend to overprovision memory, reserving far more than a task actually needs. This overprovisioning leads to significant resource wastage, increased costs, and reduced overall cluster throughput. Existing methods for predicting memory needs often focus on a single peak memory value, failing to account for the dynamic fluctuations in memory usage throughout a task's execution.

Methods

The core innovation is the k-Segments method. This approach tackles the dynamic nature of memory consumption by:

  1. Runtime Prediction: First, it predicts the task's expected runtime using a linear regression model based on the input data size. A small offset is applied to this prediction to account for potential delays.
  2. Time Series Segmentation: The predicted runtime is then divided into k equally sized segments.
  3. Segmented Memory Prediction: For each of these k segments, a separate linear regression model is trained. These models learn the peak memory usage within that specific segment, also considering the input data size.
  4. Monotonically Increasing Function: The predictions from each segment are combined to form a step function that represents the memory allocation over time. This function is designed to be monotonically increasing, ensuring that memory allocation never decreases as the task progresses.
  5. Offsetting for Robustness: To further mitigate the risk of underallocation and task failures, the predictions are offset with a buffer based on historical prediction errors.

The method operates in an online fashion, meaning the prediction models are continuously updated and refined as new workflow executions complete, making it suitable for tasks with no prior historical data.

Datasets

The authors evaluated their method using two real-world scientific workflows from the nf-core repository:

  • eager: A workflow for population history analysis.
  • sarek: A workflow for whole-genome sequencing analysis.

These workflows were run on a machine with an AMD EPYC 7282 processor and 128GB of RAM. The experiments involved gathering metrics from these workflows and then using a simulation tool to evaluate the k-Segments method against baselines. The paper also mentions making their experimental traces publicly available.

Key Insights and Ideas

  • Memory is Dynamic: The most crucial insight is that a task's memory requirement isn't static; it fluctuates significantly over its execution. Focusing on a single peak is inefficient.
  • Segmentation is Key: Dividing the task's execution into segments allows for more granular and accurate memory allocation, directly addressing the dynamic nature of resource usage.
  • Online Learning Matters: The ability to learn and adapt from ongoing workflow executions is vital, especially for new or less common tasks where historical data is scarce.
  • Trade-offs in Failure Handling: While the goal is to reduce wastage, avoiding task failures is paramount. The paper explores different retry strategies (Selective vs. Partial Retry) and highlights that the optimal strategy can depend on the specific task and workflow.
  • Parameter Tuning is Important: The number of segments (k) is a critical parameter. While a larger k can reduce wastage, it also increases the complexity and potential for prediction errors. Finding the optimal k can be challenging and might require task-specific optimization.

Key Results

The k-Segments method demonstrated significant improvements over state-of-the-art baselines:

  • Average Memory Wastage Reduction: The k-Segments Selective strategy achieved an average memory wastage reduction of 29.48% compared to the best-performing baseline (PPM Improved). The k-Segments Partial strategy also showed a substantial reduction of 22.39%.
  • Outperforming Baselines: Both k-Segments methods consistently outperformed the default workflow configurations and established baselines like PPM (Tovar et al.) and LR (Witt et al.).
  • Benefit from Training Data: The k-Segments methods showed a clear benefit from increasing amounts of training data, with consistently lower wastage and fewer retries. This is in contrast to some baselines, which showed performance degradation with more data.
  • Reduced Retries: The k-Segments methods significantly reduced the average number of task retries due to memory failures, especially when using 75% of the training data.

Limitations and Future Work

  • Parameter Selection: The selection of the parameter k (number of segments) is a limitation. While k=4 was used as a default, the paper acknowledges that k can be task-specific and finding the optimal k can be challenging, especially for tasks with complex memory usage patterns (e.g., zigzag patterns). Future work could explore reinforcement learning techniques to automatically determine the optimal k for each task.
  • Dynamic Resource Allocation: Current resource managers typically require a fixed memory estimate for the entire job duration. The paper's fine-grained, time-dependent predictions would require resource managers to support dynamic adjustments of allocated resources during runtime. Future work aims to extend existing resource manager interfaces to accommodate these dynamic claims.
  • Scheduling for Dynamic Changes: Scheduling algorithms need to account for dynamic changes in memory claims, which is an area for future research.

Summary updated

Abstract

With the increasing amount of data available to scientists in disciplines as diverse as bioinformatics, physics, and remote sensing, scientific workflow systems are becoming increasingly important for composing and executing scalable data analysis pipelines. When writing such workflows, users need to specify the resources to be reserved for tasks so that sufficient resources are allocated on the target cluster infrastructure. Crucially, underestimating a task’s memory requirements can result in task failures. Therefore, users often resort to overprovisioning, resulting in significant resource wastage and decreased throughput.In this paper, we propose a novel online method that uses monitoring time series data to predict task memory usage in order to reduce the memory wastage of scientific workflow tasks. Our method predicts a task’s runtime, divides it into k equally-sized segments, and learns the peak memory value for each segment depending on the total file input size. We evaluate the prototype implementation of our method using workflows from the publicly available nf-core repository, showing an average memory wastage reduction of 29.48% compared to the best state-of-the-art approach.
BibTeX
@inproceedings{bader2023predicting,
  author = {Jonathan Bader and Nils Diedrich and Lauritz Thamsen and Odej Kao},
  title = {{Predicting Dynamic Memory Requirements for Scientific Workflow Tasks}},
  booktitle = {IEEE Big Data},
  year = {2023},
  url = {https://openreview.net/forum?id=sdH1KnnK33},
}
Figure