Rethinking Caching: Algorithms and Bounds for Parallel Memory Systems [Zoom]

Friday, October 17, 2025 - 1:00pm to 2:00pm

Location:

32-G575

Speaker:

Rathish Das

Biography:

Rathish Das is an Assistant Professor in the Department of Computer Science at the University of Houston. Before joining UH, he held a faculty position at the University of Liverpool in the UK and was a postdoctoral fellow at the University of Waterloo. He earned his Ph.D. in Computer Science from Stony Brook University. His research focuses on leveraging approximation and randomization techniques in two key areas: (1) designing parallel and distributed algorithms for multiprocessor systems, and (2) developing algorithms for large-scale data analysis. His work has been recognized with three Outstanding Paper Awards at ACM SPAA.

Seminar group:

Parallel Reading Group

In this talk, I will introduce an algorithmic framework for analyzing paging in multi-core shared memory systems. While the classical paging problem has been extensively studied and well understood in the sequential setting for decades, its parallel counterpart has remained largely unresolved for over twenty years. In the parallel paging scenario, p processors share a limited, fast-access cache of size k, and the challenge is to dynamically allocate cache space among the processors to minimize metrics such as average or maximum completion time. I will present matching upper and lower bounds of \Theta(log p) on the competitive ratio, achievable with only constant-factor resource augmentation.

Following this, I will highlight recent theoretical progress in paging for emerging memory architectures, particularly systems equipped with high-bandwidth memory (HBM).

Location: https://mit.zoom.us/j/94523742291