计算机论文哪里有？本文采用全新路线研究的星型密铺分块算法相比传统编译器生成的算法具有明显的特色。首先，本算法的代码可读性和可维护性更好，主要原因是算法揭示了 Stencil 计算的本质结构，对应的分块算法的循环结构十分简明，并且算法伪码与程序实现具有简单直接的对应关系，易于理解、修改和维护；
第一章 引言
1.3 本文组织结构
本论文的章节内容安排如下展示：
第一章介绍本文研究背景、挑战与意义和研究内容，简要介绍了 Stencil 计算的基本概念，应用场景，常用 Stencil 的优化方案，并对本文的主要研究内容进行了阐述。
第二章概述 Stencil 相关工作，对国内外针对 Stencil 计算分块技术的特点及优缺点进行了归纳和总结，介绍了常用的核内计算优化方法以及性能分析模型，近年来常用分块方法的特点及局限性。
第三章展示了对一维Stencil 分块方法的基本构造，从中提取Stencil的一般分块规律，将该分块方法可以扩展到二维和更高维度，接下来给出适用于高维 Stencil 的空间密铺分块的形式化表述。接下来介绍数据空间中对于格点更新的转化过程，提取其中的特点，给出其中格点更新的一般化规律，并与本文提出的基于 Gauss-Seidel Stencil 分块方法相互验证。提出一种基于 Gauss-Seidel Stencil 的红黑分块算法，详细阐述了算法原理和具体的实现优化方法。介绍对本文提出密铺分块方法的算法实现，详细解释了其中基于红黑 Gauss-Seidel Stencil 的中粒度化和细粒度化实现方法。与现阶段已有的经典分块方法进行性能差异的比较，并对其中的性能差异给出分析。
第四章对算法进行理论分析和实验测试，对红黑分块技术的特点进行了总结，将本文的红黑 Gauss-Seidel 分块和 Jacobi 方法进行定性对比并定量分析，并从性能方面对算法进行了实验验证。
第五章对本文主要内容进行总结，同时对未来的可以优化的 Stencil 的研究方向进行展望。
第三章 算法的实现和性能分析
3.1 数据局部性与 Gauss-Seidel 迭代
3.1.1 数据的局部性
计算机科学中的一个重要原理是局部性，它主要指计算、通信或者数据等操作会在较短的时间内重复出现的现象。此中最为重要的一种现象是数据局部性或称访存局部性。数据局部性没有大众认可的形式定义，但是存在以下定义方式和定性的分类：数据局部性一般可细划分为时间局部性和空间局部性这两种，时间局部性指的是数据会在较为接近的时间内被多次重复访问，空间局部性指的是在物理上所相邻的数据都会在较近的时间内被多次访问。从数据局部性原理的应用于软件和硬件的角度都已经开展了大量研究。在问题的层面，现有工作提出了一系列的理论模型，以及用精巧的理论复杂度证明其技巧。在算法的层面，许多高效的分块算法是能提高数据局部性的主要方法之一。在体系结构的层面，越来越多的片上资源被设计为高速缓存，以此来缓解目前数据移动的速度远远滞后于计算速度这一硬件瓶颈。
而算法的局部性是用来分析算法的重要的理论特性之一，并对算法的具体代码实现和数值调优也有重要的意义。过往的算法局部性分析的方法大多是通过考虑具体分块方法的部性，最终通过分析得到算法整体局部性的结果。但是这种算法的局部性分析方法用来解决 Stencil 问题的分析效率并不是十分优秀，并且需要同时考虑在 Stencil 数据空间和迭代空间的分块大小，尤其是通过利用多种类型分块的算法，更需要有针对性的分析每种分块，然后再通过计算不同类型的分块比例并进行最终结合。
第四章 实验结果分析
4.1 实验环境介绍
本文的测试平台是由 2 个 Intel Xeon CPU E5-2670 组成的服务器，其时钟频率是2.30GHz，单 CPU 包含 12 核，单核 L1 cache 是 32KB，L2 cache 是 256KB，12 个核共享L3 cache 的 30MB。测试使用 ICC 编译器编译程序的版本号为 19.1.1，使用的优化‘-O3 -openmp’选项。
主要实验环境如表 4-1 所示：
选取 1D-3P、2D-5P、3D-7P 三种不同维度的 Gauss-Seidel 的函数进行测试，对于每个测试用例，并行规模由单核扩展到 24 核，验证了 3.5 节的并行分块算法的可扩展性，并测试了 3.5 节数据布局和向量化优化效果，此外还测试了不同分块大小的性能。
4.2 结果分析
在单个 CPU 上。一维 Stencil 中问题规模为 210 -221 的问题规模如表 4-2 所示，性能如图 4-1 展示，时间步为 6000，由图中可以看出，红黑排序的 Gauss-Seidel 计算在 210与基础Stencil 差距较小，为 2.74 倍，但是随着问题规模的增加，红黑排序的性能较基础 Stencil 的差距逐渐明显，特别是在问题规模为 219的时候差距最大，性能差距为 10.62 倍，在此规模之后，两种方法的性能差异逐渐变小。因为对于单核 CPU，分块的片数更多，会产生更大的内存传输量。平均性能差距 5.82 倍。
第五章 工作总结与展望
5.1 工作总结
本文通过一种全新的研究思路来设计 Stencil 分块算法。Stencil 的核心问题在于数据依赖关系，传统的编译技术从 Stencil 迭代空间出发，基于多面体模型等数学工具，研究如何利用数据依赖关系划分迭代空间，从而对同一 Stencil 问题生成单一的分块类型，并且对不同的 Stencil 问题生成类似的分块，是一种自顶至下的、从空间到分块的研究路线，其中分块类型只是空间划分的副产品。而在本文提出的算法中，分块类型占据核心地位，从 Stencil原始定义出发，利用空间密铺这一数据概念，研究如何将数据依赖关系转化为一系列的数据空间和迭代空间的分块，研究两种分块之间的转化方式以及如何利用多种分块类型对数据空间和迭代空间这两种空间进行密铺，是一种全新的、自底至上的、从分块到空间的研究路线，能够对同一 Stencil 问题生成更为灵活的多种类型的分块，并针对不同 Stencil 问题的数据依赖关系生成其特有的、具有更优复杂度的分块。
采用全新路线研究的星型密铺分块算法相比传统编译器生成的算法具有明显的特色。首先，本算法的代码可读性和可维护性更好，主要原因是算法揭示了 Stencil 计算的本质结构，对应的分块算法的循环结构十分简明，并且算法伪码与程序实现具有简单直接的对应关系，易于理解、修改和维护；其次，代码支持细粒度优化，例如向量化等，这也来源于清晰的代码结构特别是简洁的循环条件；最后，由于分块参数可以直接修改，便于未来可利用自适应优化方法设计自动调优框架寻找最优分块大小。
参考文献（略）
