TL;DR
This paper introduces Lotaru, a novel online system for accurately predicting the runtime of scientific workflow tasks on heterogeneous clusters. By combining local microbenchmarking, reduced-data workflow execution, and Bayesian regression, Lotaru significantly outperforms existing methods, making efficient scheduling in complex environments more feasible.
What Problem Does This Paper Address?
Efficiently scheduling scientific workflows on large, distributed computing clusters is crucial for maximizing resource utilization and minimizing execution time. A key bottleneck for schedulers is the need to accurately predict how long each task will run on each available node. This becomes particularly challenging in heterogeneous clusters, where nodes have varying hardware (CPU, memory, I/O), leading to different task runtimes even for the same task.
Traditional approaches often rely on historical data, which is frequently unavailable, outdated, or difficult to maintain. Online methods, which predict runtimes during execution, struggle with the "cold start" problem – having little data at the beginning of a workflow. Lotaru aims to bridge this gap by providing accurate, a priori runtime estimates for every task-node pair in a heterogeneous cluster, without relying on historical logs.
Methods
Lotaru employs a four-phase approach:
- Infrastructure Profiling: Lotaru first profiles the local developer machine and all target cluster nodes using short, parallelizable microbenchmarks (e.g., sysbench, LINPACK, fio). This captures dynamic performance characteristics like CPU speed, memory, and I/O.
- Data Sampling and Local Workflow Execution: The system selects one input file from the workflow and downsamples it into several smaller partitions. The workflow is then executed locally on the developer's machine using these partitions. To identify CPU-bound tasks, the workflow is run a second time with a reduced CPU frequency.
- Local Prediction Model Training: A Bayesian linear regression model is trained for each task. This model predicts a task's runtime based on the uncompressed input data size. The Bayesian approach is chosen for its ability to work with limited training data and provide uncertainty estimates.
- Model Adjustment for Target Infrastructure: The local runtime predictions are then adjusted for each specific target node in the cluster. This adjustment uses the microbenchmark results from the profiling phase and the observed differences in task execution between the normal and reduced-CPU local runs. A weighting factor is calculated to account for CPU and I/O differences.
Datasets
The evaluation used five real-world bioinformatics workflows from the popular nf-core repository: Eager, Methylseq, Chipseq, Atacseq, and Bacass. These workflows were run with different input datasets. The paper does not introduce new benchmark datasets but utilizes existing scientific workflows and their associated data.
Key Insights and Ideas
- The Power of Local Profiling: Lotaru's success hinges on its ability to gather detailed, albeit local, performance characteristics of the infrastructure before the main workflow execution. This allows for a more nuanced understanding of node capabilities than relying solely on abstract hardware specs.
- Bayesian Regression for Robustness: The choice of Bayesian linear regression is key. It allows Lotaru to build predictive models with relatively few data points (from the local runs) and, crucially, provides uncertainty estimates alongside predictions. This is invaluable for schedulers that can then make more informed decisions by considering the confidence in a prediction.
- Implicit Hardware Characterization: Instead of trying to directly correlate explicit hardware features (like core count or clock speed) with runtime, Lotaru uses microbenchmarks and observed task behavior under varying conditions (e.g., reduced CPU) to implicitly capture these relationships.
- Downsampling is Crucial but Nuanced: The paper highlights that downsampling input data is essential for fast local execution. However, the cumulative size of these downsampled partitions, rather than just the number of partitions, is a more critical factor for prediction accuracy.
Key Results
Lotaru significantly outperforms baseline methods (Naive, Online-M, Online-P) in terms of prediction error across various scenarios:
- Homogeneous Clusters: Lotaru achieved a median prediction error (MPE) of 5.70% across all workflows, compared to 10.34% for the best baseline (Online-P).
- Heterogeneous Clusters: Lotaru achieved a median prediction error of 15.99% compared to 30.90% for the best competitor, representing a 48.25% reduction in prediction error.
- The model adjustment strategy for heterogeneous clusters was shown to accurately reflect hardware differences, with median differences between estimated and actual adjustment factors as low as 0.03 for some nodes.
Limitations and Future Work
- Workflow Structure Assumption: Lotaru assumes workflows consist of multiple input files that can be at least partly processed separately and downsampled. For workflows where downsampling is not possible, Lotaru could still be used but might require a longer training phase by using different subsets of input files.
- Linear Input-Runtime Relation: The method assumes a linear relationship between input size and task runtime, which is common for many big data analysis tasks but might not hold for all.
- Future Work: The authors plan to extend Lotaru to different domains (beyond bioinformatics) and integrate its predictions, including confidence and uncertainty values, into existing schedulers.
Summary updated