2022年6月10日，微软新英格兰研究院（Microsoft Research New England）的高级研究员 Brendan Lucier 博士受邀于北京大学前沿计算研究中心作了题为“Scheduling and Pricing Cloud Workloads under Uncertainty”的在线报告。报告由中心助理教授孔雨晴博士主持，相关内容通过蔻享学术、Bilibili 同步直播，线上近千人观看。

Brendan Lucier 博士做在线报告

　　讲座的开始， Lucier 博士首先简单介绍了云计算服务和面对的挑战。用户希望在一个中心化的云平台上运行自己的任务并为此付费。在每个时刻，平台收到的任务的计算量一般不是恒定不变的，因此平台就可能够通过对任务适当的调度来提高计算资源的利用率，从而提高收益。

　　想要做出一个好的调度需要对用户的任务请求有充分的了解，但现实是一个 online 的环境，具有很大的不确定性。因此平台就会使用一些机器学习算法来帮助进行预测任务的分布，这个问题被称为 Workload Prediction。但是假如我们利用 Workload Prediction 来进行调度决策，那么就有可能被用户所利用。因此我们需要设计一个调度算法来兼顾 truthful 和收益。

　　Lucier 博士接下来讲述了他的问题模型。假定平台每个时刻具有 C 的计算资源，例如 CPU，我们可以认为 C 足够大。一个计算任务 j 会在时刻 a_j 到来，需要占用 c_j 的计算资源，持续 d_j 个时刻。在 t  时刻完成一个任务 j 会获得 v_j(t) 的收益，这是一个随时间递减的函数。在用户提交任务前，他可以首先汇报一个 Statement of Work（SoW），包括了他的收益函数和任务属性的分布，并且不一定要和他知道的这些私有信息一致。当每个 SoW 到来时，平台就需要提前决定在每种真实情况下的调度方式和收费方式，平台的目标就是最大化期望社会收益。

　　为了解决这一问题，Lucier 博士首先对问题做了一个放松，也就是将任务求每个时刻的期望花费，转变为一个确定的 fractional job。那么现在我们就只需要解决一个确定性的调度问题，平台的 Price Engine 的任务就是使用一些算法设计每个时刻的单位价格，之后的调度保证每个任务的运行都能够最大化 value-payment。这样就能够得到一个 truthful 的算法，也就是用户会报告真实情况。这里的算法也是动态的，会随着新 SoW 的到来而改变价格。

　　这个算法虽然能够保证每个时刻的期望计算资源消耗不超过 C，但在现实情况中仍然会超载，这时我们就需要驱除一些任务。但这种驱除会破坏算法的 truthful 性质。因此教授又引入了 Schedule Optimizer，它会驱逐那个最晚到来的任务，并且在 Price Engine 给定的价格下，保证调度最大化 (value-payment)*(1-eviction prob) 的期望。这样就使得算法仍然是 truthful 的。

　　另一个问题就随之产生，由于 Schedule Optimizer 的优化目标不同于 Price Engine，造成了不同步的问题，因此算法的收益最优性不能保证。为此教授介绍了 Adversarial Robustness 的概念，也就是说在对算法的某个任务的调度进行改变后，收益仍然不会差别太多。最后只需要利用一些集中不等式证明驱逐的概率足够小，就可以再次保证算法的收益。

　　讲座的最后，Lucier 博士对这一工作做出了总结，并和同学们就如何将这一模型和算法运用到现实平台的问题进行了讨论。