- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how to use dependencies among task runtimes to improve non-clairvoyant workflow scheduling. The authors use joint runtime distributions to update predictions based on observed task runtimes and apply dynamic programming to minimize the expected sum of workflow completion times. They also propose Truncated Joint Fitting (TJF) to estimate the joint distribution and provide matching upper and lower bounds on the expected excess scheduling cost. The experiments use runtime traces from Alibaba and Shell Chronos, with scheduling evaluations mainly conducted on constructed four-task workflows. Compared with independent prediction, untruncated joint prediction reduces total completion time by 13.94%, while TJF achieves a 0.54% improvement under the prescribed truncation setting.
Critical strengths
S1. The paper provides theoretical analysis of scheduling with dependent task runtimes, including matching upper and lower bounds on the expected excess scheduling cost.
Critical weaknesses
W1. Insufficient baselines. The experiments only compare against independent prediction and fixed-order scheduling, without including any existing scheduling methods from prior work.
W2. Limited empirical gains. The reported 13.94% improvement is heavily influenced by a single batch, while the proposed TJF method achieves only a 0.54% improvement under the prescribed setting.
W3. Limited scalability. Experiments are restricted to constructed four-task workflows, and the scalability of the exact dynamic programming approach is not evaluated.
Questions for authors
Q1. On the same 1,796 test batches, add a baseline that estimates each terminal task's conditional mean runtime from the two predecessor runtimes (any standard regressor or nearest-neighbour estimate) and orders by it, with the same bootstrap interval.
Q2. Report the distribution of per-batch savings for the uncapped joint prediction (for example, total savings with the top 1, 5 and 20 batches removed), and the eightfold-cap result on the 1,794 development batches, where the cap is chosen without seeing test outcomes.
Q3. Does any cap chosen from h alone, as Theorem 4 requires, give a gain beyond the five-draw spread at any history size, or on the Shell or Alibaba three-task cohorts of Figure 3(a)? If not, how should the cap be chosen under heavy-tailed runtimes?
4 comments
Author Response (2/2)
Q3
Yes. In the original four-task offline experiment, the formula in Theorem 4 gives a cap of 8 seconds when the history size is batches. Across the five draws, TJF's longest total completion time was 102,481 seconds, still 104 seconds less than the shortest time of 102,585 seconds for independent prediction with the same cap. This shows that at this history size, TJF with the formula cap can achieve a gain beyond the five-draw spread.
Choosing the cap under heavy-tailed runtimes We ran an offline experiment using Snowset's public query logs. In the holdout logs, the median query execution time was 0.95 seconds and the 99th percentile was 6.72 seconds. This is about seven times the median, so the runtime distribution in these logs shows heavy-tailed behavior. We compared several caps using only the development set and chose the one that gave TJF the shortest total completion time, breaking ties in favor of the smaller cap. This gave a 2.4-second cap, which we fixed before testing it on the holdout logs. Snowset data source
| TJF with the 2.4-second cap compared with | Total completion time saved | Paired 95% interval with refitting and cap reselection | Time still saved after removing the batch with the largest saving in each comparison |
|---|---|---|---|
| TJF with the 0.4-second formula cap | 575.834 s, 3.35% | 480.032 to 650.294 s | 572.281 s |
| Independent prediction with the same 2.4-second cap | 920.632 s, 5.25% | 780.654 to 1,025.912 s | 877.175 s |
Revision We will add the formula cap results and explain how we selected the cap on Snowset in the appendix.
W2
We added controlled JSON experiments with new test data and different training histories at a truncation level of 6.4 ms selected using only the development set, as detailed in Tables 1 and 2 of our response to Reviewer XYEW's Q1/W1. Compared with independent prediction, joint prediction saved 9.06% on new test data, 8.94% after removing the batch with the largest saving, and 8.86% to 10.61% across eight independent fits. In these supplementary experiments, the savings from joint prediction could be reproduced across different training histories with the truncation level held fixed.
W3
We added experiments on workflows from Alibaba production logs to extend the evaluation of exact dynamic programming from 4 to 15 tasks, as detailed in Table 3 in Part 1 of our response to Reviewer XYEW's Q2/W2. In the 15-task non-preemptive setting, all three runs completed exact planning, with a median total planning time of 12.160 s and a maximum peak memory of 1,235.31 MiB. State encoding and contiguous storage improved the practical scalability of exact dynamic programming, allowing it to handle more tasks within the same memory budget.
We hope the added baseline comparisons and the analyses of per-batch savings and truncation address your concerns about the experimental evidence, and we would be grateful if you would consider raising your score.
Limited gains in practice.
Thank you for your reply. The new experiments confirmed my suspicions: Join prediction achieves a 2.92% gain, compared to 0.83% for NN. Moreover, in 1796 batches, only 20 of them carry 80% of the savings. While the ideas described in the paper are interesting, I am not impressed by the savings in practice. Therefore, I will maintain my score.
Further Response
Thank you for actively engaging in the discussion and for stating your concern so clearly! Your comment shows us that our previous reply may have suggested the small and concentrated gain reflects a weakness of the method, while it comes from how rarely this dataset offers decisions where runtime feedback matters. We will explain this below.
Why 20 batches accounted for about 80% of the net savings. The concentration comes from the dataset. In most batches, the two terminal tasks ran for similar times, so their order barely mattered. Most of the savings came from 244 of the 1,796 batches, or 13.6%, where the two policies disagreed at a checkpoint on whether to continue or switch. These batches included 19 of the top 20 and accounted for 78.3% of the net savings, with joint prediction saving 6.52% within them. When such decisions are common, as in the Snowset experiment below, the savings are larger and spread across batches.
Practical settings where our work applies. Our method helps most when an early runtime tells the scheduler how long later tasks will take. We chose the Alibaba dataset to isolate this effect: both policies used the same scheduler and the same task marginals, so any difference came from using the dependence. The effect is small in this dataset because early runtimes rarely change the order, but it can be strong in a cloud data warehouse. There, a query’s compilation time can indicate how long it will execute, so observing it can change which queued query should run first. Production systems already act on runtime feedback, as Spark SQL adjusts execution plans [2] and Mantri restarts slow tasks [1]. Our Snowset experiment below tests this setting.
Supplementary Snowset experiment. If you would like to see how much time our method can save in a real setting suited to it, we ran an additional experiment using real query logs from Snowset [3].
Table 1. Time savings on the Snowset query logs
| Method | Time savings relative to independent prediction | 95% paired block bootstrap interval |
|---|---|---|
| Joint prediction | 7.24% | [6.98%, 7.47%] |
| Nearest neighbour | 0.47% | [0.12%, 0.82%] |
| Gradient boosting regression | 0.53% | [0.39%, 0.66%] |
Table 2. Time saved by joint prediction after removing the batches with the largest savings
| Batches retained | Time savings relative to independent prediction | Share of original net time savings retained |
|---|---|---|
| All 32,768 batches | 7.24% | 100.00% |
| Excluding the top 1 batch | 6.95% | 95.97% |
| Excluding the top 5 batches | 6.87% | 94.85% |
| Excluding the top 20 batches | 6.63% | 91.44% |
The concern about the baseline experiment in Q1/W1. Joint prediction saved more time than both regression baselines you suggested. Relative to independent prediction, it reduced total completion time by 2.92%, or 24,902 seconds, which is 3.52 times the saving of nearest neighbour and 6.22 times that of gradient boosting regression. A gain of a few percent matters at production scale, because the same workflows run repeatedly. The authors of Mantri note that even a few percent of efficiency improvement in a cluster of tens of thousands of nodes can save millions of dollars a year [1].
The value of our work. You found the ideas in the paper interesting, and these ideas are the main contribution of our work. We believe this paper is valuable for the learning-augmented scheduling community. To our knowledge, the following points were not known before.
- Even when every task's runtime distribution is exact, ignoring the dependence between task runtimes can raise the expected completion time. Theorem 1 shows when and by how much using this dependence helps.
- Proposition 3 bounds the excess cost of a learned scheduling policy by the error of its predicted joint distribution.
- Under arbitrary dependence, an excess cost of from histories is achievable and cannot be improved in the worst case, even for schedulers that probe and preempt.
The experiments play a supporting role and check the mechanism, the estimator and the planning algorithm behind our theory on measured runtimes. Future work can apply joint prediction to workflows where predecessor feedback often changes the order, such as query scheduling in cloud data warehouses and multi-stage data processing jobs. We see strong potential for runtime dependence to improve real schedulers, and our theory offers a principled way to use it.
Thank you again for the careful reading. We hope this addresses your concern about the practical gains, and we would be grateful if you would consider raising your score.
References
[1] G. Ananthanarayanan et al., Reining in the Outliers in Map-Reduce Clusters using Mantri, OSDI 2010.
[2] Apache Spark, Adaptive Query Execution.
[3] M. Vuppalapati et al., Snowset, NSDI 2020 companion dataset.
Author Response (1/2)
We thank the reviewer for highlighting the matching upper and lower bounds on expected excess scheduling cost. We also appreciate the concrete suggestions to add a conditional mean baseline and to examine how much of the total savings comes from the most influential batches. We respond to each point below.
Q1/W1
Original experimental setup and updates. Section 5.2 used independent prediction and fixed-order scheduling as baselines to test the benefit described in Theorem 1. Ordering by conditional mean runtimes can reduce expected total completion time when predecessor runtimes change which terminal task is expected to be shorter. To isolate this benefit, each terminal task had to run to completion once started, so the baseline comparisons focused on which initial order saved more time. To test whether feedback during execution could save time, the supplementary experiment let the joint and independent prediction schedulers continue or switch if a terminal task had run for some time without finishing.
Changes to the test batches. The original experiment used the time from start to finish for a single task instance. To evaluate stage-level scheduling, the supplementary experiment used the time from start to finish for the entire stage. The baselines estimate the runtime of each terminal stage and use those estimates to set the order. When one instance finishes, others in the same stage may still be running, so the runtime of a single instance does not tell us when the whole stage finishes.
Supplementary baseline experiment. We evaluated nearest neighbour and gradient boosting regression as additional baselines. Both use the same two predecessor runtimes to estimate each terminal task's conditional mean runtime. They then run the tasks to completion in increasing order of these estimates. All methods in the supplementary experiment used the same 1,796 test batches. We followed the original 95% paired bootstrap procedure, resampling whole batches 5,000 times.
Table 1. Baseline
Joint prediction had the shortest total completion time in Table 1. With independent prediction as the reference, the time saved by joint prediction was 3.52 times the time saved by nearest neighbour and 6.22 times the time saved by gradient boosting regression. These gains support the central idea of our work that accounting for dependence between task runtimes can help a scheduler make better decisions as it receives new feedback during execution.
Revision We will add the baseline comparisons to the appendix.
Q2
Distribution of per-batch savings. On the 1,796 test batches from the Q1 experiment, we ranked the batches by the time joint prediction saved relative to independent prediction. We removed the batches with the largest savings and recalculated each method's savings relative to independent prediction on the same remaining batches.
Table 2. the distribution of per-batch savings for the uncapped joint prediction
After we removed the 20 batches with the largest savings, joint prediction still saved 5,080 seconds. Both baselines took longer than independent prediction on the remaining batches.
Eightfold cap. We identified a set of 1,794 development batches. Before examining the test results, we selected the eightfold cap based on total completion time on these batches. Total completion time on the development batches tells us whether keeping longer runtimes helps the scheduler choose a better order for the terminal tasks. The same rule lets us choose a cap before testing for workflows with different runtime patterns. After locking the 64 s cap, we evaluated it on a separate set of 2,048 held-out test batches.
Table 3. the eightfold-cap result on the 1,794 development batches
Revision We will add the per-batch savings and the eightfold cap results to the appendix.