CSE Visiting Faculty Seminar - Rathish Das

Name: Rathish Das, Lecturer at the university of Liverpool

Date: Tuesday, February 21, 2023 at 11:00 am

Location: Coda 230

Link: This seminar is an in-person event only. However, the seminar will be recorded and uploaded to the School of Computational Science and Engineering channel on Georgia Tech MediaSpace following the presentation.

Title: Algorithmic Foundation of Fast Stencil Computation and Parallel Paging

Abstract: In this talk, I will present two of our recent results. First, I will give an overview of our recent algorithmic development on performing general linear stencil computations significantly faster than state-of-the-art algorithms. Second, I will present an algorithmic foundation of parallel paging.

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, erosion modeling, fluid dynamics, quantitative finance, and even cellular automata.

I will show an exciting connection from stencil computation to random walks, n-body computation, and polynomial multiplication. All our algorithms have asymptotically lower computational complexity than all existing algorithms for general linear stencils and are highly parallelizable.

In the second part of my talk, I will present an algorithmic foundation of parallel paging. 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.

Bio: Rathish Das is currently a lecturer (US equivalent: tenure-track assistant professor) at the University of Liverpool, UK. 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 are primarily in the theoretical and practical aspects of high-performance computing (HPC) and big data that are strongly motivated by today’s multiprocessor systems. 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.