In this talk, I will present an algorithmic foundation of parallel paging and an overview of our recent results on performing general linear stencil computations significantly faster than state-of-the-art algorithms. 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 or maximum completion time. I will present tight upper and lower bounds of \Theta(\log p) on the competitive ratio with O(1) resource augmentation.
In the second part of my talk, I will present our recent results on linear stencil computation. A stencil computation applies a given stencil (a pattern to compute the value of a cell from values of its nearby cells at previous time steps) to the cells in a spatial grid for some given number of time steps. Such computations arise in many areas of scientific computing, including the simulation of physical systems, traffic flows, meteorology, stochastic and fractional differential equations, chemistry, modeling of erosion, fluid dynamics, quantitative finance, and even cellular automata. I will show an exciting connection from stencil computation to random walks and n-body computation. All our algorithms have asymptotically lower computational complexity than all existing algorithms for general linear stencils and are highly parallelizable.
Biography
Rathish Das is currently a lecturer (US equivalent: tenure-track assistant professor) at the University of Liverpool. Before that, he was a postdoc at the University of Waterloo. He obtained his Ph.D. in Computer Science at Stony Brook University. His research interests primarily focus on parallel and distributed algorithms for multiprocessor systems and algorithms for massive data sets (“big data”). He also designs approximation and randomized algorithms for scheduling, graph, and computational geometry problems. Notable recognition he has received for his work includes the junior researcher award from Stony Brook University and three outstanding paper awards from SPAA 2021 and SPAA 2022.