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

Title: Rethinking Caching: Algorithms and Bounds for Parallel Memory Systems

Abstract: 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).

Speaker Bio: 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.

This event is a special seminar affiliated with the Parallel Reading Group. Subscribe to this mailing list for announcement of regular meetings.

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