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

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

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.