SHF: AF: Small: Algorithms and a Code Generator for Faster Stencil Computations

工业和科学计算的广泛应用领域都使用模板计算，包括机械系统的模拟、交通流量、气象学、随机和分数阶微分方程、化学、侵蚀建模、流体动力学、定量金融、物理模拟，甚至是元胞自动机。模板通过组合在最近的时间步长之前的一组固定大小的相邻单元的值来定义空间网格中任何时间步长t的网格单元的值。靠近有界网格边界的单元由附加条件定义，因为它们缺乏模板使用所必需的相邻单元。模板计算是一种通过在给定数量的时间步长上重复应用模板来演化充满初始数据的网格的计算。使用嵌套循环很容易实现模板计算，并且这种实现在T个时间步长更新大小为N的网格时执行与N*T成比例的工作。在多核机器的多个处理核心上运行和/或使用缓存高效技术来减少在计算期间对慢速计算机内存（随机访问内存，RAM）的昂贵访问，可以大大缩短运行时间。但是表示总资源使用（例如，总消耗的能量或所有处理核心的总处理时间）的工作量（即计算复杂性）仍然与N*T成正比。相比之下，基于研究者研究小组最近的先前工作，该项目将改进许多这些最先进的模板算法，不仅通过对任何给定的N和T执行显着减少的工作量W(N，T)，而且还保证了更理想的性质-比率W(N，T)/(N*T)随着N*T的增加而减少。由此产生的算法不仅比现代多核计算机上现有的算法运行得更快，而且还将显著减少许多类型的模板计算的总体资源（例如时间、能源）使用。本文将实现一个代码生成器，该代码生成器可以从简单的模板计算规范中自动生成高效正确的新算法并行实现。还将构建一个自动调谐器，用于在任何目标多核机器上对这些实现进行进一步的自动性能优化。因此，这个项目将为更广泛的科学家、学生和教育工作者带来高性能的节省资源的模板计算，而不需要他们完全理解复杂的算法，也不需要他们投入时间和精力在现代计算系统上实现这些算法。这个项目的发现和研究问题将被整合到高级研究生课程中。本科生和研究生将参与研究项目。研究者的研究小组最近展示了使用快速傅里叶变换（FFT）在具有任意非周期边界条件的线性模板上使用最先进的模板算法的计算复杂度的多项式改进。将当前时间步长的网格值定义为线性（响应）的模板。从较早的时间步长得到的网格值的非线性函数称为线性函数。非线性)模板。最近，该小组还表明，在自由空间边界条件下的线性模板计算可以通过高斯近似和n体计算的新使用，在功和空间中非常有效地近似。大多数新算法的实现比现有算法的最快实现要快得多。该项目将以这些结果为基础，探索其他新颖的想法来解决以下算法设计挑战：(1)线性周期/非周期模板计算的快速近似算法，(2)特殊边界条件下线性模板计算的更快的精确算法（例如，Dirichlet, Neumann），(3)非线性模板类的快速算法，以及(4)异构模板网格的快速算法。设计具有改进计算复杂度的算法将是所有类型的模板的核心挑战和目标。进一步的改进将来自减少跨度和缓存（或输入/输出、I/O）复杂性。如果对于某些类不存在具有改进界（work、span或I/O）的算法，则目标将是证明渐近紧的下界。在许多对时间敏感的模拟（例如，天气预报）中，具有近似正确结果的快速算法比具有精确结果的慢算法更可取。因此，快速近似算法将被设计用于这种情况下的潜在用途。将建立一个名为“Saltar”的专门软件堆栈，以生成本项目中设计的算法的高效多核实现。Saltar领域特定语言（DSL）将允许用户写下他们想要解决的模板问题的简单规范，Saltar代码生成器将使用该规范生成高度优化的多线程OpenCilk/OpenMP代码。Saltar自动调谐器将用于代码生成器生成的并行递归分治实现的自动离线调谐。Saltar将在开源许可下发布（BSD 3-clause或类似的允许行业使用的许可许可）。将建立一个公共网络界面来评估项目的成功和Saltar的可用性，并将通过收集来自各种来源的模板问题来创建一个基准套件，其中可能包括来自网络用户的问题（经过许可）。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A wide range of application areas across industry and scientific computing use stencil computations, including the simulation of mechanical systems, traffic flows, meteorology, stochastic and fractional differential equations, chemistry, modeling of erosion, fluid dynamics, quantitative finance, physical simulations, and even cellular automata. A stencil defines the value of a grid cell in a spatial grid at any time step t by combining the values of a fixed constant-sized set of neighboring cells at recent time steps earlier than t. Cells near the boundary of a bounded grid are defined by additional conditions, since they lack the neighboring cells necessary for the stencil to use. A stencil computation is one in which a grid filled with initial data is evolved by repeatedly applying a stencil on the grid cells for a given number of time steps. Stencil computations are easy to implement using nested loops and such implementations perform work proportional to N*T for updating a grid of size N for T time steps. Running on multiple processing cores of a multicore machine and/or using cache-efficient techniques to reduce costly accesses to the slow computer memory (random access memory, RAM) during the computation can result in much smaller running times. But the work (a.k.a. computational complexity) which represents the total resource usage (e.g., total energy consumed or the total processing time across all processing cores) still remains proportional to N*T. In contrast, building on the recent prior work by the investigator's research group, this project will improve over many of these state-of-the-art stencil algorithms not only by performing a significantly less amount of work W(N,T) for any given N and T, but also guaranteeing a more desirable property -- the ratio W(N,T)/(N*T) decreases with the increase of N*T. The resulting algorithms will not only run faster than existing algorithms on modern multicore computers, they will significantly reduce the overall resource (e.g., time, energy) usage of many classes of stencil computations. A code generator that can automatically produce highly efficient correct parallel implementations of the new algorithms from simple specifications of stencil computations will be implemented. An autotuner for further automatic performance optimization of those implementations on any target multicore machine will also be built. Thus, this project will bring high-performing resource-saving stencil computations to a wider audience of scientists, students, and educators, without requiring them to fully understand the complicated algorithms or invest time and effort necessary to implement such algorithms on modern computing systems. Findings and research problems from this project will be integrated in the advanced graduate courses. Undergraduate and graduate students will be involved in the research project.The investigator's research group has recently shown polynomial improvements in computational complexity over state-of-the-art stencil algorithms for linear stencils with arbitrary aperiodic boundary conditions using the Fast Fourier Transform (FFT). Stencils that define grid values for the current time step as a linear (resp. nonlinear) function of grid values from earlier time steps are called linear (resp. nonlinear) stencils. Very recently the group has also shown that linear stencil computations under the freespace boundary condition can be well-approximated very efficiently in work and space through a novel use of Gaussian approximations and n-body computations. Implementations of most of these new algorithms run significantly faster than the fastest implementations of existing algorithms. This project will build on those results and explore other novel ideas to tackle the following algorithm design challenges: (1) fast approximation algorithms for linear periodic/aperiodic stencil computations, (2) faster exact algorithms for linear stencils under special boundary conditions (e.g., Dirichlet, Neumann), (3) fast algorithms for classes of nonlinear stencils, and (4) fast algorithms for heterogeneous stencil grids. Designing algorithms with improved computational complexity will be the core challenge and objective across all classes of stencils. Further improvements will come from reducing the span and cache (or input/output, I/O) complexity. If there cannot exist algorithms with improved bounds (work, span, or I/O) for certain classes, the aim will be to prove asymptotically tight lower bounds. In many time-sensitive simulations (e.g., weather forecasting) fast algorithms with approximately correct results are more desirable than slow algorithms with exact results. Hence, fast approximation algorithms will be designed for potential use in such cases. A specialized software stack named "Saltar" will be built to generate efficient multicore implementations of the algorithms to be designed in this project. The Saltar domain-specific language (DSL) will allow users to write down simple specifications of the stencil problems they would like to solve, and the Saltar code generator will take the specification to generate highly optimized multithreaded OpenCilk/OpenMP code. The Saltar autotuner will be built for automatic offline tuning of the parallel recursive divide-and-conquer implementations generated by the code generator. Saltar will be released under an open-source license (BSD 3-clause or similar permissive licensing allowing use by industry). A public web interface will be built to evaluate the success of the project and the usability of Saltar, and a benchmark suite will be created by collecting stencil problems from various sources including potentially from the web users (with permission).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.