论文标题
可变处理器杯游戏的最佳时光倒数折衷
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
论文作者
论文摘要
\ emph {$ p $ - 处理器杯游戏}是一个经典且经过广泛研究的调度问题，可以捕获$ p $ - 处理器机器必须随时间推移为处理器分配任务的设置，以确保没有个人任务落在太远的落后。这个问题被正式化为多轮游戏，其中两个玩家，一个填充者（将作品分配给任务）和一个空位（安排任务）竞争。空虚的目标是最大程度地减少积压，这是任何任务的最大未偿还工作量。 最近，Kuszmaul和Westover（ITCS，2021）提出了\ emph {可变处理器杯游戏}，它考虑了相同的问题，只是在游戏回合之间可用的资源（即处理器的数量$ p $）波动。他们表明，这种看似很小的修改从根本上改变了游戏的动态：而固定$ p $ - 处理器游戏中的最佳积压为$θ（\ log n）$，独立于$ p $，而可变处理器游戏中的最佳积压为$θ（n）$。后一个结果仅适用于\ emph {指数式的许多}回合的游戏，但它仍然是一个悬而未决的问题。 本文在可变处理器杯游戏中的时间和积压之间建立了紧密的权衡曲线。重要的是，我们证明，对于由$ t $ rounds组成的游戏，最佳积压为$θ（n）$，并且仅当$ t \geΩ（n^3）$。我们的技术还允许我们解决有关可变处理器杯游戏在超越案例分析环境中的表现的其他几个开放问题。
The \emph{$ p$-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a $p$-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The problem is formalized as a multi-round game in which two players, a filler (who assigns work to tasks) and an emptier (who schedules tasks) compete. The emptier's goal is to minimize backlog, which is the maximum amount of outstanding work for any task. Recently, Kuszmaul and Westover (ITCS, 2021) proposed the \emph{variable-processor cup game}, which considers the same problem, except that the amount of resources available to the players (i.e., the number $p$ of processors) fluctuates between rounds of the game. They showed that this seemingly small modification fundamentally changes the dynamics of the game: whereas the optimal backlog in the fixed $p$-processor game is $Θ(\log n)$, independent of $p$, the optimal backlog in the variable-processor game is $Θ(n)$. The latter result was only known to apply to games with \emph{exponentially many} rounds, however, and it has remained an open question what the optimal tradeoff between time and backlog is for shorter games. This paper establishes a tight trade-off curve between time and backlog in the variable-processor cup game. Importantly, we prove that for a game consisting of $t$ rounds, the optimal backlog is $Θ(n)$ if and only if $t \ge Ω(n^3)$. Our techniques also allow for us to resolve several other open questions concerning how the variable-processor cup game behaves in beyond-worst-case-analysis settings.
