通讯避免的若干数学库核心算法的设计和优化

As the gap between the computation and communication abilities of computing systems is larger and larger, the communication cost in performance and energy in the overall cost of algorithm execution is becoming dominant, so the communication avoiding of algorithm is very important for both the performance improvement and energy reduction of computing systems. Kernel algorithms in math library is very important for the area of high performance computing, this project mainly focuses on several important benchmarks in high performance computing, such as Top 500, Graph500, HPCG etc, and researches on the design and optimization of communication avoiding of kernel algorithms in these benchmarks. This project aims to investigate from the following three important problems. First, to construct practical model of parallel computation and communication, to reflect the latest characteristics of computer architecture, and determine the parallel communication complexity of some kernel algorithms under the framework of constructed model. Second, to design communication avoiding algorithm to attain or approach the lower bound of the determined communication complexity. Third, on existing mainstream architectures, to implement and optimize the designed communication avoiding algorithms. Through the investigation of this project, we can provide methods on the design and optimization of communication avoiding for some kernel algorithms in math library, and enhance the efficiency of practical applications in high performance computing.

随着计算机系统的计算能力和通讯能力之间的差距越来越大，算法执行的总开销中通讯所带来的性能和能耗开销逐渐占主导地位，因此研究算法的通讯避免对于计算系统的性能提高和能耗降低都具有十分重要的意义。数学库中的核心算法对于高性能计算领域具有重要的研究意义，本项目重点针对高性能计算中几个重要的基准测试程序如Top500，Graph500，HPCG等，研究其中核心算法通讯避免的设计和优化。本项目拟从以下三个方向开展研究：1）构建实用的并行计算通讯模型，以反映最新的计算机体系结构特征，并确定在模型的框架下若干核心算法的并行通讯复杂度；2）设计通讯避免的算法，以达到或者尽量接近所确定的通讯复杂度下界；3）在现有主流的体系结构上，实现并优化所设计的通讯避免算法。通过本项目的研究，可以为数学库中的若干核心算法提供通讯避免的设计与优化方法，提高高性能计算实际应用的效率。

随着计算机系统的计算能力和通讯能力之间的差距越来越大，算法执行的总开销中通讯所带来的性能和能耗开销逐渐占主导地位，因此研究算法的通讯避免对于计算系统的性能提高和能耗降低都具有十分重要的意义。数学库中的核心算法在高性能计算领域具有重要的研究价值，本项目重点研究数学库中几个核心算法的通讯避免的设计和优化。. 针对一大类稠密线性代数中的运算，例如矩阵乘、高斯消去法求解线性方程组等，我们首先从理论上证明了这类运算在并行计算时的通讯复杂度下界。以通讯复杂度为参考，我们设计出了能达到或者接近复杂度下界的算法。为了验证所提算法的可行性和有效性，我们在实际的计算机系统上实现了算法，并做了一系列的对比实验和优化。我们针对高性能计算中广泛应用的基准测试程序HPL(High Performance Linpack)开发了初步的算法运行环境。理论预测表明我们的算法在Exaflops的规模下，仍然能取得较高的并行效率。在10000个核的实验平台上，测试结果表明，相比之前最好的并行算法，我们的方法能够将通讯开销减少75%。LUPP(LU Decomposition with Partial Pivoting)是求解稠密线性方程组最高效和稳定的算法，在科学计算中广泛应用。针对LUPP算法的并行，我们提出了一种新型的通讯避免及主元寻找方法，相比之前最好的方法兼具时间上的高效性和数值上的稳定性。我们将提出的方法集成到了LUPP在基准测试程序HPL上的实现中，实验结果表明了所提方法的可行性。理论分析和实验结果均证明了我们的方法在稠密线性代数运算的并行计算中非常高效。. 本项目在执行过程中共发表学术期刊论文5篇，国际会议论文13篇，其中包括高性能和并行计算领域的著名国际会议PPoPP (CCF A类), ICS, ICPP (CCF B类)，分布式和并行计算及应用领域的著名国际期刊TPDS (CCF A类) , IJHPCA (SCI)等。本项目共培养硕士和博士研究生8名，其中已毕业博士4名，已毕业硕士3名，在读博士生1名。本团队对数学库核心算法并行的通讯避免方向进行了系统研究，发展出一系列新型高效的并行化通讯避免方法，研究工作基本上与这一领域的国际最前沿成果保持同步。