Brief Announcement: Green Paging and Parallel Paging
Brief Announcement: Green Paging and Parallel Paging
复制标题
简短公告：绿色分页和并行分页
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Michele Scquizzato
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;William Kuszmaul;Michele Scquizzato
我们研究了经典分页问题的两个基本变体：绿色分页和并行分页。在绿色分页中，可以在任意给定时刻选择使用的确切内存容量，在最大k页和最小k/p页之间;目标是在完成计算所需的时间内最小化这个数字的积分（注意，以较低的容量运行不一定更好，因为可能会不成比例地增加总完成时间）。在并行分页中，k页的内存在p个处理器之间共享，每个处理器执行单独的计算;目标是最小化各自的完成时间。我们展示了这两个不同的问题是如何严格相关的：任何有效的解决方案，绿色分页可以转换成一个有效的解决方案，并行分页，和任何下限的绿色分页可以转换成一个下限的并行分页-在这两种情况下，在一个黑盒子的方式。利用这个关系，我们提供了严格的上界和下界的竞争比O（1）的资源增加两个问题。
We study two fundamental variants of the classic paging problem: green paging and parallel paging. In green paging one can choose the exact memory capacity in use at any given instant, between a maximum of k and a minimum of k/p pages; the goal is to minimize the integral of this number over the time required to complete a computation (note that running at lower capacity is not necessarily better, since might disproportionately increase the total completion time). In parallel paging, a memory of k pages is shared between p processors, each carrying out a separate computation; the goal is to minimize the respective completion times. We show how these two different problems are strictly related: any efficient solution to green paging can be converted into an efficient solution to parallel paging, and any lower bound for green paging can be converted into a lower bound for parallel paging— in both cases in a black-box fashion. Exploiting this relation, we provide tight upper and lower bounds ofΘ(logp) on the competitive ratio with O(1) resource augmentation for both problems.
DOI：
10.1145/3350755.3400233
发表时间：
2020
期刊：
Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Das, Rathish;Agrawal, Kunal;Bender, Michael A.;Berry, Jonathan;Moseley, Benjamin;Phillips, Cynthia A.
通讯作者：
Phillips, Cynthia A.