众核处理器上并行稠密矩阵计算关键技术研究

Manycore processors have become the basic accelerated components in high performance computing field. Its development trends are the deeper and deeper hierarchies in computation, memory and communication. Our major researches aims at the dense matrix computation optimization, which is the key in scientific computation field, including 1) Research on a new manycore parallel computational model characterizing with the complex computing, memory and communication hierarchy from the theoretical and accurate angles. It will be used as the base in the algorithm methods research and self-adaptive framework design. 2) Research on new parallel algorithm optimization methods based on the bottom parallel computational model. We will propose new algorithms and optimizations from the computation and the mathematical angles to improve the performances of our kernels exceeding the fastest ones. We will also study the optimization sequence based our parallel computational model for incorporating the optimizations in the runtime system. 3) Research on a new parallel performance model. Build a general optimization chain for the computing and data-moving patterns of the matrix computation based the on the new performance model. In this project, we will focus on the new algorithms and optimizations methods and will be doing the research in such a way that the parallel computational model, algorithm optimizations and the performance model design are studied integrally and inseparably.

众核处理器已成为高性能计算基本加速构件,其在计算、访存及通信方面的层次化发展对并行算法优化提出了更高挑战。本项目以科学计算的关键核心,稠密矩阵计算关键函数为研究对象,主要研究内容包括:1)众核架构并行计算模型研究。从理论性和正确性两个角度,对在计算、存储和通信多个方面出现层次化发展的众核架构进行建模,以指导矩阵核心函数算法设计;2)并行矩阵计算关键算法设计。基于众核计算模型,从计算和数学两个角度,在计算访存重叠、通信避免、非规则任务分解等方面提出新的适用于众核架构的新算法,提升关键函数性能达到或超过国际水平;3)并行性能模型研究。基于性能模型深入分析矩阵算法在众核架构上的优化方法，形成一族对矩阵计算具有一定通用性的优化序列，并建立其自适应参数调优方法。本项目中，底层硬件并行计算模型、上层程序并行性能模型和矩阵计算算法三位一体紧密结合。

在基金委青年项目支持下，项目执行的三年期间，开展了并行计算模型研究和科学计算核心函数算法设计和优化工作。.合作完成并出版《并行计算：模型与算法》专著一本，全书包括7章：引言、固定结构、共享存储、分布存储、存储层次几种并行计算模型以及并行程序性能模型，最后对并发和分布式算法进行了介绍。.提出了一种新的stencil计算两层密铺分块的并行算法。与以往直接对整个迭代空间进行分块的分块技术不同，我们提出了一种新的两层密铺分块的并行算法。首先，利用不同分块密铺数据空间，其次，所有分块沿时间维度的扩展能密铺迭代空间。本文提出的算法有以下优点:(1)最大化并发执行，(2)无冗余计算，(3)简洁的循环条件，(4)适应 Stencil 不同的尺寸、形状、阶数和边界条件。实验结果表明， 对于 d27p Stencil，非周期边界的性能比 Pluto 高 12%，周期边界的比 Pochoir 最高提升 40%。该并行算法的主要科学意义在于将格点局部坐标与其在不同执行步不同迭代空间分块的更新时间和更新步数联系起来。相关工作发表在CCF A类会议SC 2017上。.提出了一种支持数据持久化的软件cache方法。与Rochester大学Chen Ding等人合作，面向非易失存储NVRAM（Non-volatile main memory）与传统经典高速缓存cache的不协调性，特别是缓存行需要频繁写入内存导致性能和非易失性难以兼容这一问题，设计了一种软件cache，用于存储被替换的缓存行，然后再合适的时间点写入内存，可最大化缓存行写入性能，基于我们提出的一种线性时间计算缺失率曲线的算法。在SPLASH2 测试集的结果表示，所提方法提高缓存写回性能12倍并且比已有方法平均快2.1倍。相关论文发表在CCF B类会议IPDPS 2017上。.提出的一种新的局部性变换理论。针对时间重用和空间重用间统计变换的已有的减法形式公式，重新从一种全局观点进行解释，并进而提出等价的另外两种公式。进一步，将已有的大量局部性方法分为直方图局部性、时间尺度局部性和缓存局部性。提出了序列局部性，并证明其与原始内存序列的等价关系和变换算法，以及其与直方图局部性的变换的不可逆性。相关论文已撰写完毕正在投稿。