Tight Bounds for Parallel Paging and Green Paging
Tight Bounds for Parallel Paging and Green Paging
复制标题
DOI：
10.1137/1.9781611976465.180
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Kunal Agrawal;M. A. Bender;Rathish Das;William Kuszmaul;E. Peserico;Michele Scquizzato
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;M. A. Bender;Rathish Das;William Kuszmaul;E. Peserico;Michele Scquizzato
在并行分页问题中，有p个处理器共享一个大小为k的缓存。目标是随着时间的推移在处理器之间对高速缓存进行分区，以便最大限度地减少它们的平均完成时间。对于这一长期未解决的问题，我们给出了资源增加O(1)时竞争比的Θ(Logp)的上下界。我们的算法和下界中的一个关键思想是将并行分页问题与看似无关的绿色分页问题联系起来。在绿色分页中，有一个能量优化的处理器，它可以临时关闭一个或多个缓存组(从而降低功耗)，从而使缓存大小在最大大小k和最小大小k/p之间变化。目标是最小化计算消耗的总能量，这与缓存大小随时间的积分成正比。我们证明了绿色寻呼的任何有效fi解都可以转化为并行寻呼的有效fi解，并且绿色寻呼的任何下界都可以转化为并行寻呼的下界，在这两种情况下都是黑箱形式的。然后，我们证明了在O(1)资源增加的情况下，确定性在线绿色寻呼的最优竞争比为Θ(Logp)，这反过来又意味着确定性在线并行寻呼的上界相同。
In the parallel paging problem, there are p processors that share a cache of size k . The goal is to partition the cache among the processors over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of Θ(log p ) on the competitive ratio with O (1) resource augmentation. A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging . In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size k and a minimum size k/p . The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time. We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with O (1) resource augmentation, the optimal competitive ratio for deterministic online green paging is Θ(log p ) , which, in turn, implies the same bounds for deterministic online parallel paging.