Algorithmic foundations of parallel paging
Friday, September 24, 2021, 1:00-2:00 pm 
Abstract
Every modern computer---be it a desktop or a supercomputer---uses hierarchical memory. One of the crucial characteristics of any memory hierarchy is that there is a small, fast memory, followed by a large, slow memory (possibly followed by more levels). Data is served to the processor from the small, fast memory. The small, fast memory is a scarce resource, and efficiently managing it is crucial to high performance.
Sharing the small and fast memory among multiple processors gives rise to many challenges. In this talk, I will give an overview of these challenges and of the recent progress that has been made in addressing them.
Classical problems such as paging have been very well understood in the sequential setting for decades. However, the paging problem has remained wide open for more than two decades in the parallel setting. In the parallel paging problem, p processors share a cache (small, fast memory) of size k. The goal is to partition the cache among the processors over time to minimize their average completion time. I will present tight upper and lower bounds of \Theta(\log p) on the competitive ratio with O(1) resource augmentation. I will then extend the theory of parallel paging to a new kind of multilevel-memory system, called high-bandwidth memory, which is common in new supercomputers.
Bio
Rathish Das is currently a postdoctoral fellow at the University of Waterloo. He obtained his Ph.D. in Computer Science from Stony Brook University. His research interests focus on systems algorithms that are strongly motivated by today's computer systems. He has received junior researcher award from Stony Brook University and his work received two outstanding paper awards from SPAA 2021.
This talk is organized by sharmila