Online Parallel Paging with Optimal Makespan
Online Parallel Paging with Optimal Makespan
复制标题
DOI：
10.1145/3490148.3538577
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
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
经典的分页问题可描述如下：给定一个最多能容纳k个页面（或块）的缓存以及一系列对页面的请求，我们应该如何管理缓存以最大化性能——或者换句话说，尽可能快地完成该序列请求。虽然这个顺序分页问题几十年来已被充分理解，但并行版本（其中缓存由p个处理器共享，每个处理器发出自己的页面请求序列）要困难得多。在这个问题中，我们给定p个请求序列R1、R2、…、Rp，每个序列访问一组不相交的页面，并且我们提出问题：分页算法应该如何管理缓存以优化所有序列的完成时间（即最大完工时间）。与经典的顺序问题一样，目标是设计一种在线分页算法，使用O(1)资源扩充来实现最优竞争比。
The classical paging problem can be described as follows: given a cache that can hold up to k pages (or blocks) and a sequence of requests to pages, how should we manage the cache so as to maximize performance-or, in other words, complete the sequence as quickly as possible. Whereas this sequential paging problem has been well understood for decades, the parallel version, where the cache is shared among p processors each issuing its own sequence of page requests, has been much more resistant. In this problem we are given p request sequences R1, R2, . . . , Rp , each of which accesses a disjoint set of pages, and we ask the question: how should the paging algorithm manage the cache to optimize the completion time of all sequences (i.e., the makespan). As for the classical sequential problem, the goal is to design an online paging algorithm that achieves an optimal competitive ratio, using O(1) resource augmentation.