SkipPredict: When to Invest in Predictions for Scheduling

Summary

The paper studies the effectiveness of machine-learned predictions for queuing systems, and falls into the area of learning-augmented algorithms / algorithms with predictions. In particular it studies the M/G/1 queue with poisson arrival and i.i.d. service times with the objective to minimize the average response time. This problem has previously studies with service time predictions or with single-bit predictions, indicating whether a job is 'short' or 'long' depending on a certain threshold. Moreover, previously it has been assumed that predictions are for free. In contrast to these previous works, in this paper an algorithm needs to 'pay' for receiving predictions. This payment can either be some additional cost (external cost), or an additional load to the machine (server time cost) which delays the execution of other jobs. The latter is motivated by the scenario that the prediction itself first needs to be computed. Moreover, in this paper an algorithm has access to both, (cheaper) 1bit predictions and (more expensive) service time predictions. The authors propose the algorithm 'SkipPredict' which first queries a 1bit prediction for every job that arrives, and in case that this returns 'long', also queries the service time prediction. 'Short' jobs are generally preferred and scheduled First-Come-First-Serve (FCFS). Furthermore, they study a second algorithm 'DelayPredict' which only uses service time predictions. In contrast to SkipPredict, it starts scheduling every job until it can be categorized as being 'long', and only then queries a service time prediction. The authors compare both algorithms to the baselines FCFS, 1bit (only cheap predictions) and SRPPT (only expensive predictions). They find that in theory and in empirical experiments, the benefit of SkipPredict and DelayPredict depends on the how the threshold, the system load and the costs for both prediction types relate.

Strengths

- The idea of using a two-stage prediction setup composed of a cheap but less expressive and an expensive but more expressive prediction is to the best of my knowledge new in the area of learning-augmented algorithms, and might have an impact on this field. - I really like the idea that the generation of a prediction requires processing volume itself. I think such a model could also be interesting for other scheduling problems, also in adversarial models. - The results show that the use of this two-stage prediction setup help to lower the overall cost compared to the baselines for certain instances.

Weaknesses

- I think the main weakness of this work is that the results seem not to be very surprising. In particular, I think it is clear that the benefit of such a two-stage algorithm like SkipPredict heavily depends on how the costs relate. I am somehow missing some hard statements which summarize the findings more precisely. - Moreover, the two main components of SkipPredict, 1bit and SRPPT, have been previously studied and analyzed. Thus, to me it seems that the paper does not provide many interesting techniques or analyses. Given the conceptually interesting models, I tend to rate this paper as borderline right now. However, I am not too familiar with queueing theory and, thus, cannot for sure assess the weight of the second weakness I mentioned.

Questions

Typos: - Line 114 "somewhat" - Line 224 missing whitespace

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

-

Summary

This paper studies a scheduling problem that aims to minimize the expected response time, where jobs arrive online and the algorithm needs to decide the priority of jobs. This paper proposes a new algorithm called skip-prediction. Namely, the algorithm first uses a cheap prediction to partition the whole job set into two parts: long job set and short job set. For jobs in short job set, they have the highest priority and no prediction will be made. And, the algorithm ranks these short jobs by the first-come-first-serve rule. For jobs in long job sets, an expensive prediction will be made to predict the size of these long jobs. Then, the algorithm ranks these long jobs using the shortest remaining processing time first rule. The paper considers two different models; in the first model, predictions consume some extra costs and in the second model, predictions consume server times. For each model, the total cost of the algorithm is defined as the total expected response time plus the prediction cost. The authors provide theoretical proof to compute the formula for the total cost of the proposed skip-prediction algorithm, and then run an experiment on some datasets.

Strengths

The general motivation of the paper is good. Namely, it considers the case where the prediction does not get for free. The algorithm needs to optimize the scheduling objective with the prediction cost together. On the positive side, I expect that it will have a positive impact on practice application. I also expect that one may be able to abstract some interesting theoretical models from this paper; so it’s likely to influence future work.

Weaknesses

I have to say that I am usually working on the theoretical analysis of the algorithms (e.g., approximation or online algorithms). I am not in the right position to judge the quality and novelty of the experimental paper. To me, the presentation of the paper is not clear; the authors describe an algorithm in the model section instead of defining a problem. Besides this, the authors give the formula of the total cost of skip-prediction in Table 1, but it is not clear how good the quality of these formulas is from the theoretical perspective.

Questions

N.A.

Rating

4

Confidence

2

Soundness

2

Presentation

3

Contribution

2

Limitations

N.A.

Summary

Motivated by recent prediction based scheduling of ML jobs in data centers, the paper considers the problem of prediction cost aware scheduling to optimize mean response time. It considers two cost models - external and server time. The paper proposes a novel algorithm, SkipPredict, that uses a two level hierarchical prediction with a cheap short/long prediction at the first level and an expensive total size prediction at the second level. It then uses this information to schedule short jobs as FCFS and long jobs by SRPT. The paper presents an analysis of the expected response time for both models using the SOAP framework and present a comparison against FCFS, one-level FCFS+SRPT and SRPT. Finally, it provides experimental evidence of SkipPredict’s superior performance on synthetic and real world datasets.

Strengths

- The paper is the first to consider the important aspect of cost of prediction in scheduling - The proposed algorithm, SkipPredict, elegantly utilizes an efficient hierarchical scheme and is practical to implement - Thorough and well presented analysis of SkipPredict as well as the baselines including generalisation to non-fixed costs - Baselines compared against are comprehensive

Weaknesses

- While the motivation for the problem comes from scheduling ML jobs, the algorithm and analysis are solely queueing theoretic arguments which makes me question the relevance/interest of this work to the NeurIPS community. MLSys/SIGMETRICS perhaps might be a better fit. - Further, I believe none of the experiments presented reflect the characteristics of a machine learning job. The Exponential and Weibull distributions of service considered in the synthetic data are unlike the very light tailed (almost deterministic) nature of ML jobs. The real world datasets consist of CPU computations which make them unlikely to be from ML jobs.

Questions

- While the paper analytically shows that SkipPredict does better than the baselines for any general service distribution, it would also be good to see this in the experiments with distributions/datasets representing ML jobs - (Minor) It would be nice to have a short explanation of how the SOAP framework is used in the main paper as well instead of just in the appendix.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A

Summary

The paper considers the job scheduling in the M/G/1 queueing model when the system has access to predictions regarding job lengths. The paper explicitly considers the cost incurred for obtaining the predictions in such a system. Two models are considered - (i) external cost: obtaining predictions incurs a fixed cost, but do not affect the service time of a job, and (ii) server time cost: predictions are obtained via operations that themselves need to be scheduled incurring time that delays jobs. The authors consider a setting in which there are two kinds of predictions - (i) a cheap 1-bit prediction that only classifies whether the job length is above or below a fixed threshold T, and (ii) an expensive prediction that predicts the actual job length. The authors propose a natural algorithm, called SkipPredict, that first obtains cheap predictions for all jobs to classify each job as either "short" or "long". All jobs classified as "short" are scheduled via FCFS. The algorithm then obtains expensive predictions for all long jobs which are then scheduled using the shortest predicted remaining time first rule. The authors analyze this algorithm under both cost models using the SOAP analysis framework and obtains explicit expressions for the mean response times of jobs.

Strengths

- The paper raises an interesting question. Most work on learning augmented algorithms assumes that predictions are available to the algorithm for "free" which is certainly not true in practice. Explicitly modeling prediction costs is a good area for further research. The server time cost model that models the delays due to predictions is especially interesting for scheduling problems.

Weaknesses

- The paper is missing some references to prior work. For example, (i) "Online algorithms with Costly Predictions" (Drygala et al) considers costly predictions in other learning augmented settings. (ii) "Parsimonious Learning-Augmented Caching" (Im et al) considers caching with goal of using few predictions. (iii) many papers on learning augmented scheduling.

Questions

N/A

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

N/A