A Novel Prediction Setup for Online Speed-Scaling
A Novel Prediction Setup for Online Speed-Scaling
复制标题
用于在线速度缩放的新颖预测设置
DOI：
10.4230/lipics.swat.2022.9
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Golnoosh Shahkarami
中科院分区：
文献类型：
--
作者：
A. Antoniadis;Peyman Jabbarzade Ganje;Golnoosh Shahkarami
考虑到数据中心和计算系统的能源需求通常快速增长，在设计（调度）算法时考虑能源因素至关重要。机器学习在实践中可以是一种有用的方法，例如，通过基于历史数据预测系统的未来负载。然而，这种方法的有效性在很大程度上取决于预测的质量，并且当预测低于标准时，这种方法可能远远不是最佳的。另一方面，在提供最坏情况保证的同时，经典在线算法对于实践中出现的大类输入可能是悲观的。本文本着机器学习增强算法这一新领域的精神，试图为经典的、基于最后期限的在线速度缩放问题获得两全其美的结果：基于一种新的预测设置的介绍，我们开发了算法，（i）在存在足够的预测的情况下获得可证明的低能耗，（ii）对不充分的预测是鲁棒的，（iii）是平滑的，也就是说，它们的性能随着预测误差的增加而逐渐降低。
Given the rapid rise in energy demand by data centers and computing systems in general, it is fundamental to incorporate energy considerations when designing (scheduling) algorithms. Machine learning can be a useful approach in practice by predicting the future load of the system based on, for example, historical data. However, the effectiveness of such an approach highly depends on the quality of the predictions and can be quite far from optimal when predictions are sub-par. On the other hand, while providing a worst-case guarantee, classical online algorithms can be pessimistic for large classes of inputs arising in practice. This paper, in the spirit of the new area of machine learning augmented algorithms, attempts to obtain the best of both worlds for the classical, deadline based, online speed-scaling problem: Based on the introduction of a novel prediction setup, we develop algorithms that (i) obtain provably low energy-consumption in the presence of adequate predictions, and (ii) are robust against inadequate predictions, and (iii) are smooth, i.e., their performance gradually degrades as the prediction error increases.
影响因子：
22.7
作者：
M. Mitzenmacher;Sergei Vassilvitskii
通讯作者：
M. Mitzenmacher;Sergei Vassilvitskii