Online Parallel Paging and Green Paging

Explore the intricacies of parallel paging and green paging in this 45-minute conference talk by Michael A. Bender from Stony Brook University. Delve into the challenges of efficiently sharing a cache among multiple parallel processors and discover optimal multi-core paging algorithms for optimizing both makespan and average completion time. Examine the fundamental connection between parallel paging and green paging, and learn about the O(log p)-competitive algorithms for online parallel paging. Investigate the green paging dilemma, reductions between green paging and parallel paging, and competitive ratios. Gain insights into the optimist versus pessimist approach in this comprehensive exploration of advanced paging concepts presented by the Society for Industrial and Applied Mathematics.

Intro
Classical Sequential Paging
Classical (Offline) Sequential Paging
Classical Online Sequential Paging
The Parallel Paging Problem
Challenge 1: how to partition the cache among the threads?
Challenge 2: how to interleave/schedule the individual threads?
Non-Challenge: What Eviction Policy Should Each Processor Use?
Summary of parallel-paging challenges
Online parallel paging was open for 25 years
This Talk: O(log p)-competitive algs for parallel paging
The Green Paging Problem
Green paging dilemma
Online green paging → Online parallel paging
Reductions Green Paging Parallel Paging
Bounds for Green Paging and Parallel Paging
Green-paging competitive ratio: O(log p)-competitive universal alg
Optimist versus pessimist.
Summery Slide