More Like this

1. 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
2. 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
3. Online Parallel Paging with Optimal Makespan

   https://doi.org/10.1145/3490148.3538577  

   Agrawal, Kunal; Bender, Michael A.; Das, Rathish; Kuszmaul, William; Peserico, Enoch; Scquizzato, Michele (July 2022, Proc. 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
4. Online Paging with Heterogeneous Cache Slots

   Chrobak, Marek; Haney, Samuel; Liaee, Mehraneh; Panigrahi, Debmalya; Rajaraman, Rajmohan; Sundaram, Ravi; Young, Neal E. (January 2023, International Symposium on Theoretical Aspects of Computer Science)
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.)