Fast Stencil Computations using Fast Fourier Transforms
Fast Stencil Computations using Fast Fourier Transforms
复制标题
DOI：
10.1145/3409964.3461803
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Zafar Ahmad;R. Chowdhury;Rathish Das;P. Ganapathi;Aaron Gregory;Yimin Zhu
中科院分区：
文献类型：
--
作者：
Zafar Ahmad;R. Chowdhury;Rathish Das;P. Ganapathi;Aaron Gregory;Yimin Zhu
模具计算被广泛用于模拟多维网格在多个时间段上的物理系统状态的变化。 - 和链球动物算法和krylov子空间方法。该域在计算上效率低下，Krylov方法需要手动劳动和数学训练。为了求解通用线性模板，执行θ（nt）工作，其中n是空间网格的大小，t是时间段的数量，我们的算法执行O（nt）工作。据我们所知，我们给出了第一个使用快速傅立叶变换来计算最终网格数据的算法，以便同时进化许多时间段的初始数据。即，计算复杂性和并行运行时）比所有其他现有的解决方案都表明，我们的算法的实现10^7个单元格的10^5时间段的数量级比定期模板问题的最先进的实现速度快，而对于周期性模板问题，则运行的数量级，1.3×至8.5倍。
Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The state-of-the-art techniques in this area fall into three groups: cache-aware tiled looping algorithms, cache-oblivious divide-and-conquer trapezoidal algorithms, and Krylov subspace methods. In this paper, we present two efficient parallel algorithms for performing linear stencil computations. Current direct solvers in this domain are computationally inefficient, and Krylov methods require manual labor and mathematical training. We solve these problems for linear stencils by using DFT preconditioning on a Krylov method to achieve a direct solver which is both fast and general. Indeed, while all currently available algorithms for solving general linear stencils perform Θ(NT) work, where N is the size of the spatial grid and T is the number of timesteps, our algorithms perform o(NT) work. To the best of our knowledge, we give the first algorithms that use fast Fourier transforms to compute final grid data by evolving the initial data for many timesteps at once. Our algorithms handle both periodic and aperiodic boundary conditions, and achieve polynomially better performance bounds (i.e., computational complexity and parallel runtime) than all other existing solutions. Initial experimental results show that implementations of our algorithms that evolve grids of roughly 10^7 cells for around 10^5 timesteps run orders of magnitude faster than state-of-the-art implementations for periodic stencil problems, and 1.3× to 8.5× faster for aperiodic stencil problems.