Abstract: Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. I will talk about our recent results on performing general linear stencil computations significantly faster than state-of-the-art algorithms under periodic, aperiodic, and freespace boundary conditions. Our algorithm for periodic grids is based on the Fast Fourier Transform, and our aperiodic-grid algorithm uses our periodic solver repeatedly in a recursive divide-and-conquer framework.
Our freespace algorithm, on the other hand, uses a different approach based on Gaussian approximations and n-body computations. All our algorithms have asymptotically lower computational complexity than all existing algorithms for general linear stencils and are highly parallelizable. While implementations of all our algorithms run faster than the fastest known linear stencil codes, our periodic and freespace solvers run orders of magnitude faster than the state of the art. I will also give an example of a nonlinear stencil application that can be sped up using our techniques for linear stencils.
This talk presents joint work with Zafar Ahmad, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu. Most of the work was done when all authors were affiliated with Stony Brook University. The results appeared in the proceedings of SPAA’21 and SPAA’22.
Speaker’s Bio: Rezaul Chowdhury is an Associate Professor of Computer Science at Stony Brook University and a core faculty member of the Institute for Advanced Computational Science. His research interests are in the fields of algorithm design and algorithm engineering and their intersections with other sciences. He is particularly interested in the design and theoretical/practical performance analysis of shared-memory parallel algorithms. His research interests also include computational biology and bioinformatics, particularly protein-protein docking and fast energetics computation. He received an National Science Foundation CAREER Award in 2015.
Last Updated: October 18, 2022 - 1:42 pm