More Like this

1. Tight Bounds for Parallel Paging and Green Paging

   https://doi.org/10.1137/1.9781611976465.180  

   Agrawal, Kunal ; Bender, Michael A. ; Das, Rathish ; Kuszmaul, William ; Peserico, Enoch ; Scquizzato, Michele ( January 2021 , Proc.\ 32th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   null (Ed.)

   In the parallel paging problem, there are $\pP$ processors that share a cache of size $k$. The goal is to partition the cache among the \procs over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of $\Theta(\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 $\Theta(\log \p)$, which, in turn, implies the same bounds for deterministic online parallel paging. 

   more » « less
2. Tight Bounds for Parallel Paging and Green Paging

   Agrawal, Kunal ; Bender, Michael ; Das, Ratish ; Kuszmaul, William ; Peserico, Enoch ; Scquizzato, Michele ( January 2021 , Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   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. 

   more » « less
3. Online Paging with Heterogeneous Cache Slots

   Chrobak, Marek ; Haney, Samuel ; Liaee, Mehraney ; Panigrahi, Debmalya ; Rajaraman, Rajmohan ; Sundaram, Ravi ; Young, Neal E ( March 2023 , 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023))
4. Paging and the Address-Translation Problem

   Bender, Michael ; Bhattacharjee, Abhishek ; Conway, Alex ; Farach-Colton, Martin ; Johnson, Rob ; Kuszmaul, William ; Porter, Don ; Tagliavini, Guido ; Vorobyeva, Janet ; West, Evan ( January 2021 , Annual ACM Symposium on Parallelism in Algorithms and Architectures)

   The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultane- ously optimize both. To mitigate the cost of address translation, all modern CPUs have translation lookaside buffers (TLBs), which are hardware caches of common address translations. What makes TLBs interesting is that a single TLB entry can potentially encode the address translation for many addresses. This is typically achieved via the use of huge pages, which translate runs of contiguous virtual addresses to runs of contiguous physical addresses. Huge pages reduce TLB misses at the cost of increasing the IOs needed to maintain contiguity in RAM. This tradeoff between TLB misses and IOs suggests that the classical paging problem does not tell the full story. This paper introduces the Address-Translation Problem, which formalizes the problem of maintaining a TLB, a page table, and RAM in order to minimize the total cost of both TLB misses and IOs. We present an algorithm that achieves the benefits of huge pages for TLB misses without the downsides of huge pages for IOs. 

   more » « less
5. Paging and the Address-Translation Problem

   https://doi.org/10.1145/3409964.3461814  

   Bender, Michael A. ; Bhattacharjee, Abhishek ; Conway, Alex ; Farach-Colton, Martín ; Johnson, Rob ; Kannan, Sudarsun ; Kuszmaul, William ; Mukherjee, Nirjhar ; Porter, Don ; Tagliavini, Guido ; et al ( January 2021 , 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))

   null (Ed.)