一种新型Stencil并行算法研究与优化实现

Stencil是科学工程计算及其他应用中一个重要的计算问题，是十三个伯克利核心计算模式之一，几十年来高性能计算和编译技术等社区已提出了大量高效算法，但仍未清晰揭示Stencil问题的本质数学结构。本项目采取一种全新的技术路线，从研究能够描述Stencil最为核心的数据依赖关系的分块类型和相关方法出发，沿着算法即分块堆砌这一视角，利用空间密铺等数学工具，提出一种新Stencil并行分块算法，能清晰揭示Stencil问题的数学结构；在算法局部性分析方面，提出一种全新的、更为简洁的Stencil分块算法缓存复杂度分析方法，证明本项目所提新算法具有更优的缓存复杂度；在程序局部性优化方面，针对程序热点数据采用申请人提出新模型开展分析，进一步指导程序局部性优化实现并适应多存储层次；利用向量化、计算重用优化、数据高效布局以及自适应调优等技术实现一个高性能Stencil软件包，性能达到国际领先水平。

Stencil computations represent a very common class of computational problem in scientific, engineering and other applications. It is identified as one of the thirteen Berkeley motifs. The high performance and compiler communities have exhaustively studied stencils and proposed a large number of algorithms. However, none of them reveals the fundamental mathematical structure of the Stencil problem. This project adopts a whole new approach. We study the basic blocks and related methods that capture the critical data dependences of the Stencil definition. From the view that a Stencil algorithm is a stacking of blocks, we utilize the space tessellation technique to derive a new algorithm, which clearly exhibits the mathematical structure of the Stencil problem. We then propose a new method of cache complexity for stencil algorithms and prove that our new algorithm achieves a better theoretical result compared with existing algorithms. We use the new proposed Footmark model to guide the program optimization of better locality and implementation on multi-level caches by focusing on the hot data set of the program. With vectorization, computational reuse, efficient data layout, auto-tuning and other implementation techniques, we finally implement a high performance software package and beat state-of-the-art counterparts.