一句话：提出 Mat2Stencil 矩阵 DSL 及编译器，用多阶段编程生成无矩阵 stencil 代码并自动并行化，简化结构化网格 PDE 求解器开发。
PDE 求解器广泛用于科学与工程，但在结构化网格上利用确定性稀疏模式实现高性能常需复杂底层编程。本文提出 DSL Mat2Stencil 及其编译器，以结构化稀疏矩阵抽象模块化表达 Jacobi/Gauss-Seidel 预条件子、ILU/IC 分解及多网格等求解器。编译器通过多阶段编程生成由广义 stencil 组成的无矩阵代码，可处理准仿射空间循环携带依赖，并提出针对空间依赖循环的自动并行化：编译期确定性任务划分、自动同步计算与细粒度同步的多线程实现。评估含 4 个基准，3 个 NAS Parallel Benchmarks 伪应用代码量仅为手工实现的 6.3%，无矩阵 HPGC 为 16.4%，性能最高 1.67×、平均 1.03×。
Partial differential equation (PDE) solvers are extensively utilized across numerous scientific and engineering fields. However, achieving high performance and scalability often necessitates intricate and low-level programming, particularly when leveraging deterministic sparsity patterns in structured grids. In this paper, we propose an innovative domain-specific language (DSL), Mat2Stencil, with its compiler, for PDE solvers on structured grids. Mat2Stencil introduces a structured sparse matrix abstraction, facilitating modular, flexible, and easy-to-use expression of solvers across a broad spectrum, encompassing components such as Jacobi or Gauss-Seidel preconditioners, incomplete LU or Cholesky decompositions, and multigrid methods built upon them. Our DSL compiler subsequently generates matrix-free code consisting of generalized stencils through multi-stage programming. The code allows spatial loop-carried dependence in the form of quasi-affine loops, in addition to the Jacobi-style stencil’s embarrassingly parallel on spatial dimensions. We further propose a novel automatic parallelization technique for the spatially dependent loops, which offers a compile-time deterministic task partitioning for threading, calculates necessary inter-thread synchronization automatically, and generates an efficient multi-threaded implementation with fine-grained synchronization. Implementing 4 benchmarking programs, 3 of them being the pseudo-applications in NAS Parallel Benchmarks with 6.3% lines of code and 1 being matrix-free High Performance Conjugate Gradients with 16.4% lines of code, we achieve up to 1.67× and on average 1.03× performance compared to manual implementations.
@article{paperbot1836,
title = {Mat2Stencil: A Modular Matrix-Based DSL for Explicit and Implicit Matrix-Free PDE Solvers on Structured Grid},
author = {Huanqi Cao and Shizhi Tang and Qianchao Zhu and Bowen Yu and Wenguang Chen},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622822}
}